subtitle.srt

22
00:01:21,274 --> 00:01:23,174
هر زمان که همچین سوالی از ما پرسیده میشه

23
00:01:23,174 --> 00:01:25,674
شروع با واضح ترین راه حل می تونه مفید باشه

24
00:01:25,876 --> 00:01:31,974
در این نمونه اگر بخوایم بدونیم چند راه برای انداختن ۱۰ تاس با مجموع ۲۸ وجود داره

25
00:01:31,965 --> 00:01:34,965
می‌تونیم همه حالات پرتاب  ۱۰ تاس رو لیست کنیم

00:01:31,965 --> 00:01:34,965
می‌تونیم همه حالات پرتاب  ۱۰ تاس رو لیست کنیم

26
00:01:34,965 --> 00:01:38,566
و فقط بشماریم که حاصل جمع چند تای اونا ۲۸ میشه

27
00:01:38,709 --> 00:01:41,909
این یک راه حل درست برای مسئله هست

28
00:01:42,117 --> 00:01:44,117
اما احساس بدی به این راه پیدا می‌کنید

29
00:01:44,212 --> 00:01:48,513
وقتی که می شنوید راه حل بهینه ای نیست

30
00:01:48,515 --> 00:01:51,515
این راه خوبیه، اگر که با دو تاس کار کنیم

31
00:01:52,006 --> 00:01:55,006
چون که فقط ۳۶ حالت ممکن برای پرتاب وجود داره

32
00:01:55,093 --> 00:01:56,593
در اینجا عدد ۳۶ به وجود آمده از

33
00:01:56,593 --> 00:01:59,093
از ۶ که تعداد پرتاب های ممکن هست
34
00:01:59,093 --> 00:02:02,593
که به توان ۲ رسیده که تعداد تاس هاست

35
00:02:02,980 --> 00:02:04,480
اما با ۱۰ تاس

36
00:02:04,513 --> 00:02:09,013
تعداد کل پرتاب های ممکن ۶ به توان ۱۰ است

37
00:02:09,014 --> 00:02:12,014
که حاصل بیش از ۶۰ میلیون میشه

38
00:02:12,014 --> 00:02:16,014
که بعیده ی انسان تا آخر عمرش هم بتونه انقد تاس پرتاب کنه

39
00:02:16,745 --> 00:02:18,145
در حالیکه یک کامپیوتر مدرن

40
00:02:18,145 --> 00:02:22,044
بتونه همه این حالات رو زیر ۱ دقیقه انجام بده

41
00:02:22,044 --> 00:02:26,044
اما اگر از ما سوالهای راجع به پرتاب ۲۰ یا ۳۰ تاس بپرسن

42
00:02:26,048 --> 00:02:28,548
حتی برای یک کامپیوتر هم خیلی زیاد میشه

43
00:02:28,661 --> 00:02:31,461
پس باید راه بهتری پیدا کنیم

44
00:02:32,294 --> 00:02:35,294
یک راه رایج دیگه برای طراحی الگوریتم

45
00:02:35,324 --> 00:02:37,925
فکر کردن به الگوریتم  به صورت بازگشتی هست
46
00:02:37,955 --> 00:02:43,355
که میشه گفت روش حل کردن مسئله بزرگتر با شکستن اون به مسئله های مشابه کوچکتر هست

47
00:02:43,770 --> 00:02:46,073
به خاطر داشته باشید که ما داریم تلاش می‌کنیم که متوجه بشیم

48
00:02:46,104 --> 00:02:48,604
به چند روش می تونیم از n تاس استفاده کنیم

49
00:02:48,604 --> 00:02:50,604
تا حاصل جمع پرتاب ها ‌m بشه

50
00:02:50,973 --> 00:02:53,973
پس بیایید با آسون‌ترین مسئله از این نوع شروع کنیم

51
00:02:54,401 --> 00:02:56,401
در حالتی که n با یک برابره
52
00:02:56,435 --> 00:02:58,935
یعنی ما فقط یک تاس پرتاب می‌کنیم

53
00:02:59,026 --> 00:03:01,324
توی این حالت مسئله خیلی آسونه

54
00:03:01,372 --> 00:03:03,072
به ازای همه مقادیر m

55
00:03:03,104 --> 00:03:07,104
از ۱ تا ۶ دقیقا یک راه برای پرتاب آن مقدار وجود داره

56
00:03:07,794 --> 00:03:10,697
به ازای همه مقادیر دیگه m، جواب 0 هست

57
00:03:11,062 --> 00:03:12,562
هیچ راهی وجود نداره که با یک تاس
58
00:03:12,566 --> 00:03:16,566
مجموع دیگه ای غیر از ۱ تا ۶ بگیریم

59
00:03:17,324 --> 00:03:20,824
حالا بیایید مسئله کمی بزرگتر رو حل کنیم

60
00:03:21,436 --> 00:03:26,936
چند راه وجود داره تا با استفاده از ۲ تاس مثلا ۸ بیاریم؟

61
00:03:26,901 --> 00:03:28,901
خب حاصل جمع دو پرتاب رو

62
00:03:29,068 --> 00:03:31,467
میشه به عنوان نتیجه یک بار پرتاب

63
00:03:31,502 --> 00:03:34,300
و پرتاب بار دوم که باهاش جمع میشه، در نظر گرفت

64
00:03:34,360 --> 00:03:38,860
واون پرتاب دوم باید ۱ ، ۲، ۳ ، ۴ ، ۵ یا ۶ باشه

65
00:03:38,929 --> 00:03:42,429
پس برای اینکه تعداد کل حاصل جمع ها ۸ باشه

66
00:03:42,467 --> 00:03:48,967
پرتاب اول باید به ترتیب ۷ ، ۶ ، ۵ ، ۴ ، ۳ یا ۲ باشه

67
00:03:49,211 --> 00:03:51,913
چند راه وجود داره برای اینکه این اتفاق بیفته؟

68
00:03:52,080 --> 00:03:55,377
خب میدونیم که برای یک تاس عدد ۷ غیر ممکنه

69
00:03:55,567 --> 00:03:56,567
و همچنین میدونیم که

70
00:03:56,598 --> 00:03:59,098
دقیقا یک راه برای یک تاس وجود داره
71
00:03:59,098 --> 00:04:02,598
که ۶ ، ۵ ، ۴ ، ۳ یا ۲ بیفته

72
00:04:02,781 --> 00:04:05,781
پس مجموع همه این حالت ها ۵ هست

73
00:04:06,014 --> 00:04:10,114
که تعداد روش هایه که ما میتونیم با دوتاس ۸  بیاریم

74
00:04:10,193 --> 00:04:11,693
شاید بنظر برسه که

75
00:04:11,729 --> 00:04:14,429
ما بیش از حد داریم یک مسئله ساده رو پیچیده می‌کنیم

76
00:04:14,461 --> 00:04:17,461
و خب درسته، حداقل برای این حالت های ساده حق با شماست

77
00:04:17,463 --> 00:04:21,963
اما گاهی اوقات توضیح دادن راه حل با مسئله ساده تر

78
00:04:21,778 --> 00:04:25,478
کمک می‌کنه تا طرح یک راه حل کلی تر رو بریزیم

79
00:04:25,463 --> 00:04:30,463
توی این حالت میتونیم تعمیم بدیم و بگیم که برای n تاس که جمعش m باشه

80
00:04:30,543 --> 00:04:33,843
اولین n-1 تاس باید

81
00:04:34,043 --> 00:04:36,543
حاصل جمع های m-1

82
00:04:36,545 --> 00:04:37,845
و m-2

83
00:04:37,846 --> 00:04:39,545
و  m-3

84
00:04:39,612 --> 00:04:40,812
و m-4

85
00:04:41,045 --> 00:04:42,245
و m-5

86
00:04:42,278 --> 00:04:43,778
و یا m-6 داشته باشن

87
00:04:44,540 --> 00:04:48,939
جمع همه این ۶ مقدار، درنهایت به ما جوابی که می خوایم رو میده

88
00:04:49,937 --> 00:04:54,538
این به ما یک الگوریتم بازگشتی برای به دست اوردن جواب مسئله میده

89
00:04:54,687 --> 00:04:58,187
برای پرتاب حاصل مجموع ۲۸ با ۱۰ تاس

90
00:04:58,220 --> 00:05:06,220
حاصل مجموع ۹ تاس اول باید ۲۷ ، ۲۶، ۲۵، ۲۴، ۲۳ یا ۲۲ باشه

91
00:05:06,420 --> 00:05:08,021
و چطوری میتونیم اونا رو حساب کنیم؟

92
00:05:08,021 --> 00:05:12,521
مثلا چند روش برای پرتاب مجموع ۲۷ با ۹ تاس وجود داره؟

93
00:05:12,954 --> 00:05:15,954
خب این همون مجموع تعداد روشهای استفاده از ۸ تاس

94
00:05:16,021 --> 00:05:20,5

برای پرتاب حاصل مجموع ۲۶ ، ۲۵، ۲۴، ۲۳، ۲۲ یا ۲۱ هست

95
00:05:21,160 --> 00:05:23,459
و این فرایند رو انقد تکرار میکنیم

96
00:05:23,675 --> 00:05:26,276
تا زمانی که به چیزی برسیم که بهش میگیم "وضعیت پایه" ا

97
00:05:26,447 --> 00:05:29,447
یک تاس، که می دونیم جواب چیه

98
00:05:30,536 --> 00:05:34,637
اما ی نگاه بندازید به تعداد دفعاتی که ما این فرایند رو تکرار کردیم

99
00:05:34,637 --> 00:05:38,237
نظر میرسه که این روش هم خیلی نامناسبه

100
00:05:38,271 --> 00:05:43,271
در واقع این الگوریتم بازگشتی خیلی بهتر از راه حل قبلی‌مون نیست

101
00:05:43,271 --> 00:05:45,971
که همه حالت های ممکن پرتاب رو لیست می کردیم

102
00:05:46,391 --> 00:05:49,091
هنوز هم همه پرتاب های ممکن رو در نظر می‌گیریم

103
00:05:49,158 --> 00:05:53,658
هرچقدر تعداد تاس ها بیشتر بشه، تعداد کار های ما به صورت تابع نمایی رشد میکنه

104
00:05:54,156 --> 00:05:55,855
اما اگر با دقت به فرآیند نگاه کنید

105
00:05:55,958 --> 00:05:59,958
برای انجام دادن این محاسبات، متوجه چیزهای جالبی میشید

106
00:06:00,095 --> 00:06:03,095
اینجا کلی عملیات تکراری وجود داره

107
00:06:03,293 --> 00:06:07,793
اینجا باید محاسبه کنیم چطوری با ۸ تاس ۲۴ بیاریم

108
00:06:08,062 --> 00:06:10,062
و اینجا هم  همون رو محاسبه کردیم

109
00:06:10,163 --> 00:06:13,163
اینحا هم دوباره همونو

110
00:06:13,694 --> 00:06:16,194
بعد از اینکه نتیجه رو یکبار محاسبه کردیم

111
00:06:16,196 --> 00:06:19,196
هیچ دلیلی برای انجام دوباره و دوباره اون نیست

112
00:06:19,262 --> 00:06:23,362
اگر نتیجه محاسبه اول رو ذخیره کنیم

113
00:06:23,362 --> 00:06:25,562
و در جای مشخصی قرارش بدیم

114
00:06:25,596 --> 00:06:27,596
جایی به راحتی بعدا بهش دسترسی پیدا کنیم

115
00:06:27,947 --> 00:06:31,947
اینطوری هرموقع که دوباره نیازش داشتیم میتونیم از نتیجه محاسبه استفاده کنیم

116
00:06:32,098 --> 00:06:36,098
و اینجا جاییه که کارایی بالا به دست میاد

117
00:06:36,185 --> 00:06:38,685
ما فقط به یکمی حافظه نیاز داریم تا این نتیجه ها رو در ذخیره کنیم

118
00:06:38,752 --> 00:06:40,151
تا بتونیم ازشون دوباره استفاده کنیم

119
00:06:40,187 --> 00:06:41,687
ما میتونیم از یه میز بزرگ استفاده کنیم

120
00:06:41,708 --> 00:06:43,908
که اغلب اوقات بهش میگن lookup table

121
00:06:43,961 --> 00:06:46,461
جایی که ما نتیجه هر محاسبه رو ذخیره میکنیم

122
00:06:46,461 --> 00:06:50,262
این میز برای هر عدد تاس، یک ردیف داره

123
00:06:50,288 --> 00:06:52,487
از ۱ تا هدف ما که ۱۰ هست

124
00:06:52,521 --> 00:06:55,521
و یک ستون برای هر جمع محتمل

125
00:06:55,521 --> 00:06:58,822
از ۱ تا هدف ما که ۲۸ هست

126
00:06:58,944 --> 00:07:02,444
ما میتونیم با پر کردن ردیف اول این میز شروع کنیم

127
00:07:02,576 --> 00:07:07,778
که همه جمع های احتمالی یک بار تاس انداختن رو نشون میده

128
00:07:07,944 --> 00:07:12,345
میدونیم که برای جمع ۱ تا ۶ دقیقا ۱ راه برای انجامش وجود داره

129
00:07:12,346 --> 00:07:16,545
و برای بقیه مقادیر 0 راه برای انجامش هست

130
00:07:16,747 --> 00:07:18,747
حالا ردیف بعدی رو پر میکنیم

131
00:07:19,047 --> 00:07:22,047
که نشون دهنده تمام جمع های احتمالی با دو تاس هست

132
00:07:22,079 --> 00:07:27,579
برای محاسبه هر از کدوم اینا فقط نیاز داریم که ۶ مقدار از  ردیف قبلی اضافه کنیم

133
00:07:27,879 --> 00:07:31,079
و برای ردیف سوم، تمام جمع های احتمالی با سه تاس

134
00:07:31,146 --> 00:07:35,047
هر مقدار از جمع ۶ مقدار از ردیف دوم به دست میاد

135
00:07:35,247 --> 00:07:38,447
به عنوان مثال تعداد حالاتی که از سه تاس استفاده کنیم

136
00:07:38,512 --> 00:07:40,512
و مقدار ۱۰ به دست بیاریم

137
00:07:40,579 --> 00:07:43,579
مساوی این هست که از ۲ تاس استفاده کنیم

138
00:07:43,812 --> 00:07:48,312
و مقادیر ۹ و ۸ و ۷ و ۶ و ۵ و ۴ به دست بیاریم

139
00:07:48,379 --> 00:07:51,379
به همین روش برای دست آوردن ۴ توسط ۳ تاس

140
00:07:51,379 --> 00:07:58,879
نیاز داریم جمع های ۳ و ۲و ۱ و ۰ و ۱- یا ۲- رو با ۲ تاس بدست بیاریم

141
00:07:59,081 --> 00:08:03,581
البته به دست آوردن هر جمعی که 0 یا منفی هست غیرممکنه

142
00:08:03,781 --> 00:08:09,281
پس قاعدتا میتونیم اون احتمالات رو دور بریزیم و فقط به بقیه توجه کنیم

143
00:08:09,490 --> 00:08:13,990
اگه ما به انجام این فرآیند ادامه بدیم و هر ردیف رو به ترتیب پر کنیم

144
00:08:14,103 --> 00:08:16,204
در نهایت آخرین ردیف رو پر میکنیم

145
00:08:16,370 --> 00:08:22,370
و میفهمیم چند حالت برای به دست آوردن جمع ۲۸ با ۱۰ تاس وجود داره

146
00:08:22,538 --> 00:08:28,538
و ما این کار رو با انجام یه محاسبه برای هر سلول روی این میز انجام دادیم

147
00:08:28,802 --> 00:08:30,004
ممکنه به نظر خیلی زیاد بیاد

148
00:08:30,071 --> 00:08:35,071
اما این خیلی خیلی کمتر از ۶۰ میلیون حالت تاس هست

149
00:08:35,138 --> 00:08:37,138
که ممکن بود در اون صورت بهش بر بخوریم

150
00:08:37,625 --> 00:08:41,225
این اصل پشت پرده چیزی هست که به اون dynamic programming میگیم

151
00:08:41,293 --> 00:08:43,793
با فرمول بندی یک مسئله به صورت بازگشتی

152
00:08:43,860 --> 00:08:48,860
یا به عبارتی تعریف یک مسئله بر اساس مسئله های کوچیک تر از همون مسئله

153
00:08:49,080 --> 00:08:51,278
و سپس استفاده از یک lookup table

154
00:08:51,278 --> 00:08:54,181
با ذخیره نتیجه محاسباتی که ما تا حالا انجام دادیم

155
00:08:54,182 --> 00:08:57,182
میتونیم اکثر مواقع به طور چشمگیری سرعت این الگوریتم ها رو افزایش بدیم

156
00:08:57,692 --> 00:09:00,692
و این نمونه از تکنیک ها به طور گستره قالب اجرا هستند

157
00:09:01,061 --> 00:09:03,061
این فقط در مورد تاس انداختن نیست

158
00:09:03,062 --> 00:09:06,562
این در مورد اینکه بفهمیم ما میتونیم همزمان مسائل جدید حل کنیم

159
00:09:06,562 --> 00:09:08,961
و جواب قبلی ها رو یا به یاد داشته باشیم

160
00:09:08,995 --> 00:09:12,495
و بفهمیم که با یادآوری کاری که تا الان انجام دادیم

161
00:09:12,629 --> 00:09:15,629
خودمون رو قادر میکنیم که ساده تر و با کارایی بالاتر

162
00:09:15,629 --> 00:09:19,629
مسائل بزرگتر و چالش برانگیز تر رو حل کنیم