در این مطلب، ویدئو الگوریتم جستجوی پرش در پایتون – یک راهنمای مفید با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:46:49
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:01,040 –> 00:00:03,520
سلام متفکران امروز شاهد
2
00:00:03,520 –> 00:00:05,680
الگوریتم بسیار جالبی خواهیم بود که بر
3
00:00:05,680 –> 00:00:08,639
اساس الگوریتم جستجوی ستاره ساخته شده است، یعنی
4
00:00:08,639 –> 00:00:10,880
5
00:00:10,880 –> 00:00:12,799
الگوریتم جستجوی نقطه پرش، الگوریتم جستجوی نقطه پرش
6
00:00:12,799 –> 00:00:15,599
برای یافتن مسیر بر روی نقشه های شبکه
7
00:00:15,599 –> 00:00:17,920
مانند این الگوریتم روی تصویر
8
00:00:17,920 –> 00:00:20,880
به عنوان مثال در بازی های رایانه ای استفاده می شود، بهینه شده است.
9
00:00:20,880 –> 00:00:23,279
از خاصیتی به نام تقارن مسیر استفاده
10
00:00:23,279 –> 00:00:25,920
می کند که به این معنی است که یک
11
00:00:25,920 –> 00:00:28,640
مسیر یا بخش های مسیری وجود دارد که شروع یکسانی دارند
12
00:00:28,640 –> 00:00:31,439
و راس هدف دارای
13
00:00:31,439 –> 00:00:34,719
طول یکسان هستند و در غیر این صورت یکسان هستند اما از
14
00:00:34,719 –> 00:00:36,960
نظر ترتیب اسکن متفاوت هستند.
15
00:00:36,960 –> 00:00:39,440
الگوریتم سریع بهینه است و
16
00:00:39,440 –> 00:00:42,559
نیازی به شناسایی سربار حافظه ندارد
17
00:00:42,559 –> 00:00:45,120
و به طور انتخابی
18
00:00:45,120 –> 00:00:47,520
فقط رئوس مورد علاقه را که به
19
00:00:47,520 –> 00:00:49,440
آنها نقاط پرش می گویند گسترش می دهد، به
20
00:00:49,440 –> 00:00:52,239
این معنی که رئوس بین هر دو
21
00:00:52,239 –> 00:00:55,280
نقطه پرش منبسط نمی شوند یا به
22
00:00:55,280 –> 00:00:58,640
تعبیر آشنای ما ناشناخته می مانند،
23
00:00:58,640 –> 00:01:00,719
این خاصیتی است که
24
00:01:00,719 –> 00:01:03,280
با کاهش تعداد رئوس عملکرد الگوریتم بسیار سریعتر را امکان پذیر
25
00:01:03,280 –> 00:01:05,119
می کند.
26
00:01:05,119 –> 00:01:07,920
باید
27
00:01:07,920 –> 00:01:10,000
یک مثال را با اعمال
28
00:01:10,000 –> 00:01:12,560
الگوریتم a-star اصلی
29
00:01:12,560 –> 00:01:13,840
در c ما پردازش کنیم از آنجایی که
30
00:01:13,840 –> 00:01:17,040
این نقشه شبکه دارای لبه هایی بین هر
31
00:01:17,040 –> 00:01:18,479
دو رأس است،
32
00:01:18,479 –> 00:01:19,520
اما
33
00:01:19,520 –> 00:01:22,240
من آنها را از تصویر حذف کرده
34
00:01:22,240 –> 00:01:25,040
ام تا واضح تر
35
00:01:25,040 –> 00:01:26,560
در سمت راست
36
00:01:26,560 –> 00:01:29,600
باشد، چند علامت وجود دارد که برخی از
37
00:01:29,600 –> 00:01:32,560
آنها قبلاً از بلوک های قبلی شناخته شده اند
38
00:01:32,560 –> 00:01:35,520
و برخی از آنها جدید هستند. بنابراین سعی می کنم
39
00:01:35,520 –> 00:01:37,840
آنها را
40
00:01:37,840 –> 00:01:39,520
برای شما توضیح دهم تا
41
00:01:39,520 –> 00:01:43,280
بتوانید بقیه مطالب این وبلاگ را دنبال کنید.
42
00:01:43,280 –> 00:01:47,119
نماد اول یک مسیر کم است
43
00:01:47,119 –> 00:01:49,920
به این معنی که نشان می
44
00:01:49,920 –> 00:01:52,560
دهد اسکن در الگوریتم تا کجا
45
00:01:52,560 –> 00:01:54,640
پیش رفته است مسیر بازدید شده
46
00:01:54,640 –> 00:01:58,479
بخشی از مسیری است که نشان می دهد. به
47
00:01:58,479 –> 00:01:59,600
48
00:01:59,600 –> 00:02:01,280
نقطه پرش بعدی
49
00:02:01,280 –> 00:02:03,119
نماد راس شروع
50
00:02:03,119 –> 00:02:04,320
51
00:02:04,320 –> 00:02:05,600
به طور معمول
52
00:02:05,600 –> 00:02:09,038
نشان دهنده یک راس است که ما از آن به عنوان
53
00:02:09,038 –> 00:02:12,319
نقطه شروع الگوریتم خود استفاده می کنیم.
54
00:02:12,319 –> 00:02:15,440
55
00:02:15,440 –> 00:02:16,720
56
00:02:16,720 –> 00:02:19,360
57
00:02:19,360 –> 00:02:20,640
58
00:02:20,640 –> 00:02:22,879
59
00:02:22,879 –> 00:02:25,280
60
00:02:25,280 –> 00:02:27,360
نماد
61
00:02:27,360 –> 00:02:29,520
به این معنی است که
62
00:02:29,520 –> 00:02:32,239
در واقع یک راس معمولی است که میتوانیم
63
00:02:32,239 –> 00:02:33,440
64
00:02:33,440 –> 00:02:36,800
از آن بازدید و کاوش کنیم و
65
00:02:36,800 –> 00:02:39,200
در یک روند عادی یک
66
00:02:39,200 –> 00:02:41,840
عملیات الگوریتم از آن استفاده کنیم
67
00:02:41,840 –> 00:02:44,239
، همین امر در مورد نقطه پرش بازدید شده و
68
00:02:44,239 –> 00:02:46,160
نقطه پرش کاوش
69
00:02:46,160 –> 00:02:48,640
و در نهایت نقطه هدف صدق میکند. مثلاً
70
00:02:48,640 –> 00:02:51,920
اینجا در پایان یا اینجا در نقشه شبکه ما
71
00:02:51,920 –> 00:02:55,680
که نشان دهنده راس نهایی است
72
00:02:55,680 –> 00:02:57,680
که وقتی با آن مواجه
73
00:02:57,680 –> 00:03:00,159
می
74
00:03:00,159 –> 00:03:03,440
شویم باعث خاتمه الگوریتم ما
75
00:03:03,760 –> 00:03:05,280
در اسلاید بعدی
76
00:03:05,280 –> 00:03:08,800
می شود، یک مورد ساده داریم، یک شبکه کوچکتر،
77
00:03:08,800 –> 00:03:11,200
78
00:03:11,200 –> 00:03:13,680
یک مورد پیچیده تر کمی
79
00:03:13,680 –> 00:03:14,560
دیرتر وجود خواهد داشت،
80
00:03:14,560 –> 00:03:16,480
اما درست است. حالا
81
00:03:16,480 –> 00:03:18,800
بیایید با یک شبکه کوچکتر شروع کنیم و من به
82
00:03:18,800 –> 00:03:22,000
شما نشان خواهم داد که الگوریتم جستجو چگونه کار
83
00:03:22,000 –> 00:03:26,080
می کند ما از این راس 1 1 شروع می
84
00:03:26,080 –> 00:03:28,799
کنیم و سعی می
85
00:03:28,799 –> 00:03:31,440
کنیم راس 1 5 را
86
00:03:31,440 –> 00:03:34,799
بین آنها پیدا کنیم آیا این راس یک چهار
87
00:03:34,799 –> 00:03:37,840
نشان دهنده یک مانع یک دیوار است. اگر
88
00:03:37,840 –> 00:03:40,000
دوست دارید
89
00:03:40,000 –> 00:03:41,120
در
90
00:03:41,120 –> 00:03:44,000
یک مورد واقعی دلیلی است
91
00:03:44,000 –> 00:03:47,760
برای اینکه چرا ما نمی توانیم برویم
92
00:03:47,760 –> 00:03:50,159
چرا نمی توانیم این مسیر مستقیم را
93
00:03:50,159 –> 00:03:53,120
بین راس شروع و راس هدفمان دنبال کنیم
94
00:03:53,120 –> 00:03:55,599
95
00:03:55,599 –> 00:03:58,959
، اولین قدم این است که از رأس شروع خود به این صورت بازدید کنید
96
00:03:58,959 –> 00:04:00,879
97
00:04:00,879 –> 00:04:02,239
98
00:04:02,239 –> 00:04:03,760
و طبق معمول
99
00:04:03,760 –> 00:04:07,040
آن را اولویت بندی کرده ایم یا cued آن را
100
00:04:07,040 –> 00:04:09,840
در صف اولویت قرار داد
101
00:04:09,840 –> 00:04:10,799
و
102
00:04:10,799 –> 00:04:13,519
اکنون از آنجایی که ما فقط این یک و تنها
103
00:04:13,519 –> 00:04:15,680
راس را در صف اولویت خود داریم، راس
104
00:04:15,680 –> 00:04:17,199
بعدی
105
00:04:17,199 –> 00:04:20,720
خواهد بود که بیرون کشیده می شود و کاوش می شود
106
00:04:20,720 –> 00:04:24,320
این کاری است که در مرحله بعدی انجام خواهیم
107
00:04:24,639 –> 00:04:26,000
داد از آنجایی که ما راس شروع را بررسی کرده ایم،
108
00:04:26,000 –> 00:04:27,360
109
00:04:27,360 –> 00:04:29,680
110
00:04:29,680 –> 00:04:32,479
باید چند توضیح از
111
00:04:32,479 –> 00:04:34,400
آنچه اتفاق افتاده است به شما بدهم
112
00:04:34,400 –> 00:04:36,479
، راس شروع
113
00:04:36,479 –> 00:04:38,320
در واقع
114
00:04:38,320 –> 00:04:40,479
تمام همسایگان بلافصل خود را اسکن کرده است،
115
00:04:40,479 –> 00:04:42,720
بنابراین اولین
116
00:04:42,720 –> 00:04:44,240
همسایه
117
00:04:44,240 –> 00:04:45,840
هایی که آن را احاطه کرده اند
118
00:04:45,840 –> 00:04:48,080
و اینها
119
00:04:48,080 –> 00:04:50,960
صفر صفر صفر یک صفر دو
120
00:04:50,960 –> 00:04:53,040
یک دو دو دو
121
00:04:53,040 –> 00:04:56,639
دو یک هستند. دو صفر و 1 0
122
00:04:56,639 –> 00:05:00,160
اینها همسایه های بلافصل آن هستند
123
00:05:00,160 –> 00:05:03,199
حال سؤال این است
124
00:05:03,440 –> 00:05:06,960
که کدام رئوس باید به عنوان
125
00:05:06,960 –> 00:05:08,479
نقاط پرش
126
00:05:08,479 –> 00:05:12,000
در نظر گرفته شوند، بیایید سه صفر اول
127
00:05:12,000 –> 00:05:15,280
یک صفر و دو صفر
128
00:05:15,280 –> 00:05:18,080
صفر صفر را در نظر بگیریم که به هیچ جا منتهی می
129
00:05:18,080 –> 00:05:19,600
شود،
130
00:05:19,600 –> 00:05:20,639
اوه لبه
131
00:05:20,639 –> 00:05:22,240
132
00:05:22,240 –> 00:05:25,919
شبکه ما نیست. به هیچ جا منتهی نمی شود، بنابراین
133
00:05:25,919 –> 00:05:27,919
به عنوان نقطه پرش انتخاب نمی شود
134
00:05:27,919 –> 00:05:31,199
،
135
00:05:31,199 –> 00:05:34,800
همین امر برای راس 1 صدق می کند و در مورد راس 2 نیز صدق
136
00:05:34,800 –> 00:05:39,440
137
00:05:39,440 –> 00:05:41,440
138
00:05:41,440 –> 00:05:43,280
می
139
00:05:43,280 –> 00:05:44,080
140
00:05:44,080 –> 00:05:46,720
کند. و سمت پایین
141
00:05:46,720 –> 00:05:47,440
یا
142
00:05:47,440 –> 00:05:49,759
صرفاً در سمت چپ ما
143
00:05:49,759 –> 00:05:52,160
مستقیماً به سمت پایین سه صفر می رویم و
144
00:05:52,160 –> 00:05:54,800
نتیجه می گیریم که اینجا چیزی وجود ندارد بنابراین این
145
00:05:54,800 –> 00:05:57,759
شاخه مورد توجه نیست و
146
00:05:57,759 –> 00:05:59,120
147
00:05:59,120 –> 00:06:02,160
نخواهد بود و حاوی نقطه پرش نخواهد
148
00:06:02,160 –> 00:06:05,600
بود. همین امر در مورد راس 0 1 نیز صدق می کند. همچنین
149
00:06:05,600 –> 00:06:08,639
به لبه نقطه شبکه منتهی می شود
150
00:06:08,639 –> 00:06:11,199
و همچنین به عنوان یک نقطه جالب کنار گذاشته می شود به
151
00:06:11,199 –> 00:06:14,080
152
00:06:14,639 –> 00:06:16,080
طور مشابه
153
00:06:16,080 –> 00:06:19,120
برای راس 2
154
00:06:19,120 –> 00:06:21,199
1 یک اسکن عمودی را
155
00:06:21,199 –> 00:06:24,080
از راس شروع خود شروع
156
00:06:24,080 –> 00:06:25,680
می کنیم و به
157
00:06:25,680 –> 00:06:28,800
راس 2 1 می رسیم و پس از آن
158
00:06:28,800 –> 00:06:30,960
به راس 31 می رسیم و پیدا می کنیم هیچ چیز جالبی نیست،
159
00:06:30,960 –> 00:06:32,479
160
00:06:32,479 –> 00:06:33,680
بنابراین
161
00:06:33,680 –> 00:06:36,319
هیچ چیز از این مسیر وجود ندارد که
162
00:06:36,319 –> 00:06:39,120
به عنوان نقطه پرش
163
00:06:39,120 –> 00:06:41,520
در این قسمت شناخته شود، وضعیت کمی
164
00:06:41,520 –> 00:06:43,520
متفاوت است،
165
00:06:43,520 –> 00:06:46,960
در حالی که ما از راس شروع خود به صورت مورب به سمت بالا می
166
00:06:46,960 –> 00:06:51,039
رویم، راس 0 2 را پیدا
167
00:06:51,039 –> 00:06:52,560
168
00:06:52,560 –> 00:06:54,880
می کنیم و می توانیم از خود بپرسیم که چه ویژگی خاصی
169
00:06:54,880 –> 00:06:57,360
در مورد آن وجود دارد.
170
00:06:57,440 –> 00:06:59,440
یک قانون در الگوریتم وجود دارد که
171
00:06:59,440 –> 00:07:01,039
می گوید
172
00:07:01,039 –> 00:07:02,960
173
00:07:02,960 –> 00:07:06,000
اگر یک حرکت مورب
174
00:07:06,000 –> 00:07:08,400
وجود داشته باشد و یک راس وجود داشته باشد
175
00:07:08,400 –> 00:07:11,360
که در مسیر این
176
00:07:11,360 –> 00:07:13,199
راس قرار دارد
177
00:07:13,199 –> 00:07:14,000
و
178
00:07:14,000 –> 00:07:15,680
این
179
00:07:15,680 –> 00:07:18,960
راس دیگر یک نقطه پرش
180
00:07:18,960 –> 00:07:20,720
در مورد ما است
181
00:07:20,720 –> 00:07:22,160
182
00:07:22,160 –> 00:07:23,120
183
00:07:23,120 –> 00:07:25,759
که راس 0 4
184
00:07:25,759 –> 00:07:26,560
سپس
185
00:07:26,560 –> 00:07:30,479
0 2 خواهد بود. همچنین یک راس است، شاید
186
00:07:30,479 –> 00:07:33,360
خیلی قابل درک نباشد که من در مورد آن صحبت می کنم،
187
00:07:33,360 –> 00:07:34,400
اما
188
00:07:34,400 –> 00:07:37,120
یک لحظه صبر کنید و من به شما نشان خواهم داد که در مورد چیست
189
00:07:37,120 –> 00:07:39,120
190
00:07:39,120 –> 00:07:40,479
فقط به یاد داشته باشید
191
00:07:40,479 –> 00:07:41,440
که
192
00:07:41,440 –> 00:07:45,520
راس 0 2 یک نقطه پرش است فقط به
193
00:07:45,520 –> 00:07:48,319
این دلیل که جانشین آن در راس آینده
194
00:07:48,319 –> 00:07:51,680
است. 0 4 همچنین یک نقطه پرش است،
195
00:07:51,680 –> 00:07:53,840
این فقط زمانی اعمال می شود که ما یک حرکت مورب داشته باشیم،
196
00:07:53,840 –> 00:07:55,440
197
00:07:55,440 –> 00:07:57,520
198
00:07:57,520 –> 00:08:01,759
درست است برای راس 2 نیز
199
00:08:01,919 –> 00:08:04,479
200
00:08:04,479 –> 00:08:07,360
201
00:08:07,360 –> 00:08:09,440
202
00:08:09,440 –> 00:08:11,120
203
00:08:11,120 –> 00:08:14,080
204
00:08:14,080 –> 00:08:16,960
همینطور است. راس 2 4
205
00:08:16,960 –> 00:08:20,160
و به دلیل آن راس اسکن ما
206
00:08:20,160 –> 00:08:22,879
همانطور که با این پیکان خط چین نشان داده شده است
207
00:08:22,879 –> 00:08:25,039
اسکن ما
208
00:08:25,039 –> 00:08:26,479
در حال حاضر در اینجا در این تکرار به پایان می رسد
209
00:08:26,479 –> 00:08:28,000
210
00:08:28,000 –> 00:08:28,879
و
211
00:08:28,879 –> 00:08:29,759
212
00:08:29,759 –> 00:08:30,800
213
00:08:30,800 –> 00:08:33,839
راس 2 2 را به عنوان یک نقطه پرش اعلام می کند
214
00:08:33,839 –> 00:08:36,240
هر دو این نقاط پرش به صف اولویت ما اضافه می شوند
215
00:08:36,240 –> 00:08:38,159
216
00:08:38,159 –> 00:08:41,440
و شما می توانید آنها را در اینجا به عنوان 0 2 و 2 2 ببینید
217
00:08:41,440 –> 00:08:42,479
.
218
00:08:42,479 –> 00:08:44,720
فقط اجازه دهید توضیح دهم
219
00:08:44,720 –> 00:08:48,160
که عناصر این تاپل چیست،
220
00:08:48,160 –> 00:08:51,360
بنابراین اولین عنصر خود موجودیت
221
00:08:51,360 –> 00:08:52,640
222
00:08:52,640 –> 00:08:57,519
است، برای دو مورد ما 2 2 و 0 2 است،
223
00:08:57,519 –> 00:09:00,480
اوه عدد دوم نشان دهنده
224
00:09:00,480 –> 00:09:03,360
هزینه کل است. از uh
225
00:09:03,360 –> 00:09:05,279
از رأس ما،
226
00:09:05,279 –> 00:09:06,640
227
00:09:06,640 –> 00:09:09,200
من فقط به اسلاید قبلی پشتیبان می گیرم
228
00:09:09,200 –> 00:09:12,880
تا توضیح دهم که چگونه این را محاسبه
229
00:09:12,880 –> 00:09:15,760
کنیم، ما در اینجا و اینجا برای
230
00:09:15,760 –> 00:09:18,320
هر دو نقطه پرش خود مقدار یکسانی داریم
231
00:09:18,320 –> 00:09:21,760
و آخرین عدد نشان دهنده جهت uh
232
00:09:21,760 –> 00:09:23,200
233
00:09:23,200 –> 00:09:25,519
است که جستجو در
234
00:09:25,519 –> 00:09:28,480
آن جهت ها حرکت می کند. تو می توانی آن را
235
00:09:28,480 –> 00:09:30,240
در مقاله
236
00:09:30,240 –> 00:09:31,920
0 نگاه کنید
237
00:09:31,920 –> 00:09:34,240
که از راس شروع
238
00:09:34,240 –> 00:09:38,240
مستقیم به راست می رود، سپس یکی
239
00:09:38,240 –> 00:09:40,640
اگر به صورت مورب به
240
00:09:40,640 –> 00:09:42,000
سمت راست و بالا می رویم،
241
00:09:42,000 –> 00:09:43,440
سپس دو،
242
00:09:43,440 –> 00:09:44,720
سپس سه،
243
00:09:44,720 –> 00:09:47,200
سپس چهار مستقیم به سمت چپ
244
00:09:47,200 –> 00:09:48,880
و پنج
245
00:09:48,880 –> 00:09:50,480
چپ و پایین،
246
00:09:50,480 –> 00:09:52,560
سپس
247
00:09:52,560 –> 00:09:56,480
6 تا انتها منظور من از پایین مستقیم به پایین است.
248
00:09:56,480 –> 00:09:57,839
7
249
00:09:57,839 –> 00:09:59,279
پایین و راست
250
00:09:59,279 –> 00:10:01,920
و 0 بار دیگر
251
00:10:01,920 –> 00:10:03,279
و
252
00:10:03,279 –> 00:10:05,120
هر زمان که
253
00:10:05,120 –> 00:10:06,160
از
254
00:10:06,160 –> 00:10:07,920
این هه رد شدیم،
255
00:10:07,920 –> 00:10:10,160
بیایید تصور کنیم که
256
00:10:10,160 –> 00:10:15,440
مرزی از جهت صفر است، اگر از هفت
257
00:10:15,600 –> 00:10:16,560
به
258
00:10:16,560 –> 00:10:19,120
یک برویم، فرض کنیم
259
00:10:19,120 –> 00:10:20,560
جهات
260
00:10:20,560 –> 00:10:22,880
مانند هفت صفر
261
00:10:22,880 –> 00:10:25,920
یک است، مانند هفت هشت و نه
262
00:10:25,920 –> 00:10:28,079
نیست، جهتی به نام وجود ندارد.
263
00:10:28,079 –> 00:10:29,680
264
00:10:29,680 –> 00:10:32,399
با عددی بزرگتر از هفت
265
00:10:32,399 –> 00:10:35,440
بعد از هفت، یک بار دیگر صفر داریم
266
00:10:35,440 –> 00:10:36,320
و
267
00:10:36,320 –> 00:10:40,000
اگر در جهت دیگر برویم، اگر
268
00:10:40,000 –> 00:10:42,959
از یک به صفر برویم، عدد
269
00:10:42,959 –> 00:10:45,120
بعدی هفت
270
00:10:45,120 –> 00:10:46,800
است، منهای یک یا چیزی شبیه به
271
00:10:46,800 –> 00:10:48,720
آن نیست، هفت
272
00:10:48,720 –> 00:10:51,279
اشکالی ندارد، پس بیایید بیایید یک
273
00:10:51,279 –> 00:10:53,200
لحظه برگردیم
274
00:10:53,200 –> 00:10:54,800
من فقط می خواهم توضیح دهم که چگونه
275
00:10:54,800 –> 00:10:58,800
کل
276
00:10:58,959 –> 00:11:00,480
مسافت کل هزینه را محاسبه کنیم،
277
00:11:00,480 –> 00:11:01,440
بنابراین
278
00:11:01,440 –> 00:11:03,440
اگر ما به این
279
00:11:03,440 –> 00:11:05,440
راس 5 5 نگاه می کنیم،
280
00:11:05,440 –> 00:11:06,720
برای مثال
281
00:11:06,720 –> 00:11:08,959
چقدر
282
00:11:08,959 –> 00:11:11,440
از راس طلا فاصله
283
00:11:11,440 –> 00:11:13,440
دارد،
284
00:11:13,440 –> 00:11:15,760
این چنین است مقدار اکتشافی
285
00:11:15,760 –> 00:11:17,920
همانطور که در مقاله به صورت مورب نشان داده شده
286
00:11:17,920 –> 00:11:23,360
است 7 و 7 و 7 است که 21 است
287
00:11:23,360 –> 00:11:24,320
و
288
00:11:24,320 –> 00:11:25,760
حرکت های مستقیم به
289
00:11:25,760 –> 00:11:29,519
معنی حرکت افقی یا عمودی
290
00:11:29,519 –> 00:11:30,560
291
00:11:30,560 –> 00:11:33,200
پنج واحد هزینه دارد و این کاملاً هفت
292
00:11:33,200 –> 00:11:35,600
به علاوه هفت چهارده به علاوه هفت بیست و
293
00:11:35,600 –> 00:11:39,519
یک به علاوه پنج 26 است
294
00:11:39,519 –> 00:11:43,839
بنابراین برای قسمت تخمینی
295
00:11:43,920 –> 00:11:47,680
توجه کنید که تخمین می تواند از
296
00:11:47,680 –> 00:11:48,959
رئوس
297
00:11:48,959 –> 00:11:50,800
موانع عبور
298
00:11:50,800 –> 00:11:53,760
کند، این فقط یک تخمین است
299
00:11:53,760 –> 00:11:55,760
300
00:11:55,760 –> 00:11:59,200
و قسمت دوم کل
301
00:11:59,200 –> 00:12:00,880
هزینه یک
302
00:12:00,880 –> 00:12:03,600
راس، فاصله واقعی تا
303
00:12:03,600 –> 00:12:05,839
راس شروع است، این چیزی است که
304
00:12:05,839 –> 00:12:08,800
الگوریتم هنگام اجرا محاسبه می کند، بنابراین فقط
305
00:12:08,800 –> 00:12:11,120
به خاطر داشته باشید که وجود دارد دو
306
00:12:11,120 –> 00:12:14,880
جزء از هزینه کل یک راس
307
00:12:14,880 –> 00:12:16,800
هستند،
308
00:12:16,800 –> 00:12:17,920
مسافت
309
00:12:17,920 –> 00:12:21,440
طی شده تا کنون هزینه تا کنون
310
00:12:21,440 –> 00:12:23,839
در کد منبع
311
00:12:23,839 –> 00:12:26,399
از راس شروع
312
00:12:26,399 –> 00:12:27,360
تا
313
00:12:27,360 –> 00:12:29,920
راس مورد نظر ما وجود دارد و
314
00:12:29,920 –> 00:12:31,920
همچنین این بخش دیگر این
315
00:12:31,920 –> 00:12:33,440
مقدار اکتشافی از
316
00:12:33,440 –> 00:12:35,680
راس ما وجود دارد. نگاه کردن
317
00:12:35,680 –> 00:12:38,480
به رأس هدف
318
00:12:38,480 –> 00:12:41,760
همان چیزی است که در الگوریتم جستجوی ستاره ای
319
00:12:41,760 –> 00:12:43,760
وجود دارد،
320
00:12:43,760 –> 00:12:45,680
خوب است، بنابراین بیایید به جایی که
321
00:12:45,680 –> 00:12:47,760
متوقف
322
00:12:47,760 –> 00:12:50,399
شدیم برگردیم، دقیقاً در اینجا بودیم و متوجه شدیم که
323
00:12:50,399 –> 00:12:52,399
رئوس 0 2 و
324
00:12:52,399 –> 00:12:53,920
2 2
325
00:12:53,920 –> 00:12:54,800
به
326
00:12:54,800 –> 00:12:56,560
327
00:12:56,560 –> 00:12:57,839
328
00:12:57,839 –> 00:12:59,839
صف اولویت اضافه می شوند
329
00:12:59,839 –> 00:13:01,440
و نکته بعدی این است
330
00:13:01,440 –> 00:13:03,519
که باید
331
00:13:03,519 –> 00:13:06,720
از صف اولویت خود خارج شویم، راس بعدی
332
00:13:06,720 –> 00:13:08,959
برای کاوش
333
00:13:08,959 –> 00:13:10,880
334
00:13:10,880 –> 00:13:13,920
این راس 2 خواهد بود، همانطور که می توانید تشخیص دهید
335
00:13:13,920 –> 00:13:16,399
اولین راس است،
336
00:13:16,399 –> 00:13:19,200
پس بیایید انجام دهیم.
337
00:13:19,360 –> 00:13:21,760
در حال کاوش در رأس
338
00:13:21,760 –> 00:13:23,360
2 2
339
00:13:23,360 –> 00:13:25,760
ما
340
00:13:25,760 –> 00:13:27,440
در
341
00:13:27,440 –> 00:13:29,920
ابتدا در
342
00:13:29,920 –> 00:13:31,839
343
00:13:31,839 –> 00:13:34,480
جهت پایین رو به پایین اسکن کرده
344
00:13:34,480 –> 00:13:37,839
ایم و با راس 3 2 مواجه شده ایم اما
345
00:13:37,839 –> 00:13:40,480
برای ما جالب نیست
346
00:13:40,480 –> 00:13:43,680
و اکنون در اسکن افقی در واقع
347
00:13:43,680 –> 00:13:46,480
یک نقطه پرش جدید در حرکت افقی کشف کرده ایم
348
00:13:46,480 –> 00:13:50,720
و این راس 2 4
349
00:13:50,720 –> 00:13:52,880
به همین دلیل است که ما آن
350
00:13:52,880 –> 00:13:53,839
351
00:13:53,839 –> 00:13:57,040
را در صف اولویت خود قرار می دهیم
352
00:13:57,040 –> 00:13:59,360
اکنون که به
353
00:13:59,360 –> 00:14:02,880
سمت پایین یا عمودی و افقی اسکن کرده
354
00:14:02,880 –> 00:14:05,040
ایم و در حال حرکت مورب
355
00:14:05,040 –> 00:14:08,320
به راس 3 3 هستیم
356
00:14:08,320 –> 00:14:09,680
و
357
00:14:09,680 –> 00:14:11,839
بعد از این حرکت مورب
358
00:14:11,839 –> 00:14:13,440
3 3
359
00:14:13,440 –> 00:14:15,920
به خودی خود چیز جالبی نیست. می توانید
360
00:14:15,920 –> 00:14:17,920
تصور کنید که ما به صورت عمودی به
361
00:14:17,920 –> 00:14:20,880
سمت پایین ادامه می دهیم اما چیزی
362
00:14:20,880 –> 00:14:24,320
برای پردازش وجود ندارد و
363
00:14:24,320 –> 00:14:26,320
همچنین یک جهت افقی به
364
00:14:26,320 –> 00:14:27,600
سمت راست
365
00:14:27,600 –> 00:14:28,399
366
00:14:28,399 –> 00:14:31,120
وجود دارد و همچنین هیچ چیز جالبی وجود ندارد
367
00:14:31,120 –> 00:14:32,079
بنابراین
368
00:14:32,079 –> 00:14:34,560
این تکرار
369
00:14:34,560 –> 00:14:38,639
با راس 2 4.
370
00:14:38,639 –> 00:14:42,880
حالا بیایید راس 2 4 را کاوش کنیم و
371
00:14:42,880 –> 00:14:45,519
ببینیم
372
00:14:45,519 –> 00:14:48,480
با کاوش راس 2
373
00:14:48,480 –> 00:14:50,800
ما را به کجا می رساند 4 ما دو کار را انجام می
374
00:14:50,800 –> 00:14:52,560
دهیم اولین کار این است
375
00:14:52,560 –> 00:14:54,800
که ما به اسکن
376
00:14:54,800 –> 00:14:56,800
کردن تا آخر به سمت راست ادامه می دهیم،
377
00:14:56,800 –> 00:14:59,279
هیچ چیز جالبی وجود نداشت که در آن متوقف شدیم.
378
00:14:59,279 –> 00:15:01,440
راس 27 چون
379
00:15:01,440 –> 00:15:03,839
380
00:15:03,839 –> 00:15:08,160
عنصری از لبه نقشه شبکه ما را نشان می
381
00:15:08,160 –> 00:15:10,959
دهد، بنابراین هیچ چیز جالبی در اینجا
382
00:15:10,959 –> 00:15:13,839
وجود ندارد و یک چیز جالب دیگر وجود دارد که
383
00:15:13,839 –> 00:15:17,680
باید به خاطر بسپارید و توجه داشته باشید
384
00:15:17,680 –> 00:15:19,279
که ما در واقع
385
00:15:19,279 –> 00:15:22,079
یک دوره اضافی اضافه کرده ایم و چون
386
00:15:22,079 –> 00:15:23,600
387
00:15:23,600 –> 00:15:24,639
388
00:15:24,639 –> 00:15:26,480
389
00:15:26,480 –> 00:15:28,480
همسایه 2 4 را اجباری کرده ایم.
390
00:15:28,480 –> 00:15:31,680
و آن راس 1 است 5. حالا که به
391
00:15:31,680 –> 00:15:32,399
392
00:15:32,399 –> 00:15:34,240
همه همسایه های
393
00:15:34,240 –> 00:15:36,399
راس 2 4 نگاه می کنید
394
00:15:36,399 –> 00:15:40,639
اینها 1 3 2 3 3 3 قبلاً اسکن شده
395
00:15:40,639 –> 00:15:43,680
اند هیچ چیز جالبی در آنها وجود نداشت
396
00:15:43,680 –> 00:15:46,000
سه چهار سه پنج
397
00:15:46,000 –> 00:15:48,800
نیز قبلاً اسکن شده اند دو پنج نیز
398
00:15:48,800 –> 00:15:51,120
قبلاً اسکن شده اند
399
00:15:51,120 –> 00:15:53,600
یک چهار یک مانع
400
00:15:53,600 –> 00:15:56,800
و علاوه بر این مانع،
401
00:15:56,800 –> 00:15:58,320
این
402
00:15:58,320 –> 00:16:00,240
راس 1 5 نیز وجود دارد
403
00:16:00,240 –> 00:16:02,000
که ما آن را تشخیص
404
00:16:02,000 –> 00:16:05,600
دادیم زیرا بعد از یک راس مانع چرخشی را بعد از uh
405
00:16:05,600 –> 00:16:09,199
406
00:16:09,199 –> 00:16:12,560
گرفتیم، بنابراین حالا که چرخیدیم و راس 1
407
00:16:12,560 –> 00:16:15,519
5 را به صف اولویت خود اضافه کردیم،
408
00:16:15,519 –> 00:16:18,639
حالا بیایید این بار یک تکرار بیشتر انجام دهید،
409
00:16:18,639 –> 00:16:23,839
ما به راس 1 5 نگاه می کنیم
410
00:16:25,360 –> 00:16:28,000
و هنگامی که راس 1 5 را بررسی می کنیم، یکی
411
00:16:28,000 –> 00:16:29,600
از اولین چیزهایی که باید در
412
00:16:29,600 –> 00:16:31,120
الگوریتم بررسی
413
00:16:31,120 –> 00:16:32,399
کنیم این است که
414
00:16:32,399 –> 00:16:33,519
آیا
415
00:16:33,519 –> 00:16:37,680
این راس ما در حال کاوش هستیم آیا یک
416
00:16:37,680 –> 00:16:39,440
راس هدف است
417
00:16:39,440 –> 00:16:40,880
که الگوریتم
418
00:16:40,880 –> 00:16:44,880
پیدا شده است. یک پاسخ مثبت به این سوال
419
00:16:44,880 –> 00:16:48,240
، راس 1 5 را به عنوان راس هدف ما تشخیص داد
420
00:16:48,240 –> 00:16:52,160
421
00:16:52,160 –> 00:16:54,639
و مسیر جستجو را بازسازی کرد و اکنون میتوانیم ببینیم که
422
00:16:54,639 –> 00:16:56,480
مسیر جستجوی ما
423
00:16:56,480 –> 00:16:57,600
1 1
424
00:16:57,600 –> 00:16:58,800
2 2
425
00:16:58,800 –> 00:17:00,000
2 4 است،
426
00:17:00,000 –> 00:17:02,720
توجه داشته باشید که ما از این راس 2 3 صرف نظر کردهایم
427
00:17:02,720 –> 00:17:04,880
زیرا این راس از هیچ علاقه ای وجود ندارد، بنابراین این
428
00:17:04,880 –> 00:17:06,400
یک پیشرفت
429
00:17:06,400 –> 00:17:07,760
در رابطه با
430
00:17:07,760 –> 00:17:10,480
الگوریتم ستاره ای است که ما
431
00:17:10,480 –> 00:17:14,240
به راس 2 4 پرش کردیم و راس 1 5 را
432
00:17:14,240 –> 00:17:18,360
پیدا کردیم.
433
00:17:18,400 –> 00:17:20,799
همچنین یک نکته قابل توجه است
434
00:17:20,799 –> 00:17:22,400
اوه ما هرگز
435
00:17:22,400 –> 00:17:24,720
باز نکردیم ما هرگز
436
00:17:24,720 –> 00:17:28,400
راس صفر دو را کاوش نکردیم، بنابراین
437
00:17:28,400 –> 00:17:30,640
صرفه جویی در زمان است
438
00:17:30,640 –> 00:17:33,760
و اوه ما همچنین هرگز رئوس
439
00:17:33,760 –> 00:17:36,160
صفر پنج صفر شش صفر هفت یک شش
440
00:17:36,160 –> 00:17:37,600
یک هفت را کاوش نکردیم
441
00:17:37,600 –> 00:17:40,320
و این نیز صرفه جویی در
442
00:17:40,320 –> 00:17:42,559
زمان است.
443
00:17:42,559 –> 00:17:44,400
444
00:17:44,400 –> 00:17:47,440
445
00:17:47,440 –> 00:17:49,679
446
00:17:49,679 –> 00:17:52,000
447
00:17:52,000 –> 00:17:52,880
در یک
448
00:17:52,880 –> 00:17:54,480
مورد کمتر ساده ببینید
449
00:17:54,480 –> 00:17:56,799
چگونه الگوریتم در اینجا کار می کند،
450
00:17:56,799 –> 00:17:59,360
ما یک نقشه شبکه بزرگتر داریم
451
00:17:59,360 –> 00:18:00,640
که
452
00:18:00,640 –> 00:18:02,559
راس آن 0 0
453
00:18:02,559 –> 00:18:04,640
به عنوان راس شروع است،
454
00:18:04,640 –> 00:18:08,720
ما راس 1 8 را به عنوان راس هدف
455
00:18:08,720 –> 00:18:10,880
داریم و ما
456
00:18:10,880 –> 00:18:13,120
3
457
00:18:13,120 –> 00:18:15,039
سه مانع
458
00:18:15,039 –> 00:18:17,120
در اینجا و اینجا داریم
459
00:18:17,120 –> 00:18:19,919
و همه رئوس سفید
460
00:18:19,919 –> 00:18:22,480
رئوسی هستند که در واقع آزاد هستند. برای بازدید،
461
00:18:22,480 –> 00:18:24,640
آنها برای بازدید در دسترس هستند و اکنون
462
00:18:24,640 –> 00:18:26,320
خواهیم دید
463
00:18:26,320 –> 00:18:29,360
که الگوریتم چقدر هوشمندانه از بسیاری
464
00:18:29,360 –> 00:18:31,600
از این رئوس جلوگیری
465
00:18:31,600 –> 00:18:33,679
می کند و آنها را پردازش نمی کند
466
00:18:33,679 –> 00:18:35,039
و
467
00:18:35,039 –> 00:18:37,200
چگونه راس هدف را خیلی سریع پیدا می کند.
468
00:18:37,200 –> 00:18:38,960
469
00:18:38,960 –> 00:18:41,280
470
00:18:41,280 –> 00:18:44,720
471
00:18:45,919 –> 00:18:47,039
472
00:18:47,039 –> 00:18:50,080
صف اولویت ما
473
00:18:50,080 –> 00:18:50,960
474
00:18:50,960 –> 00:18:53,760
و کار بعدی این است که این را کاوش کنیم
475
00:18:53,760 –> 00:18:55,600
، ما این راس صفر صفر را بررسی می کنیم،
476
00:18:55,600 –> 00:19:00,080
بنابراین در مرحله بعدی
477
00:19:00,080 –> 00:19:03,039
بیایید آن را کاوش کنیم، همه همسایه های موجود را به ما داد
478
00:19:03,039 –> 00:19:04,720
479
00:19:04,720 –> 00:19:06,559
تا اسکن کنیم
480
00:19:06,559 –> 00:19:09,679
این یک چیز خاص در مورد
481
00:19:09,679 –> 00:19:13,280
راس شروع است که آن را انجام خواهد داد. همیشه همه همسایگان خود را به شما می
482
00:19:13,280 –> 00:19:15,120
دهد
483
00:19:15,120 –> 00:19:19,520
زیرا اوه هیچ محدودیتی در مورد
484
00:19:19,520 –> 00:19:21,520
آنچه که باید و باید ارائه دهد وجود
485
00:19:21,520 –> 00:19:23,120
ندارد،
486
00:19:23,120 –> 00:19:26,480
در اصطلاح
487
00:19:26,480 –> 00:19:30,400
الگوریتم پیاده سازی ما در حسگر هرس وجود ندارد،
488
00:19:30,400 –> 00:19:33,840
بنابراین الگوریتم اجرا شد. در تمام مسیر پایین
489
00:19:33,840 –> 00:19:36,799
، چیز جالبی پیدا
490
00:19:36,799 –> 00:19:39,280
نکرد، به سمت راست رفت
491
00:19:39,280 –> 00:19:41,600
و متوقف شد، زیرا
492
00:19:41,600 –> 00:19:44,640
راس 0 2 یک مانع است، بنابراین نمی تواند
493
00:19:44,640 –> 00:19:47,520
جلوتر
494
00:19:47,600 –> 00:19:49,840
برود، همچنین سعی کرد به
495
00:19:49,840 –> 00:19:53,440
سمت چپ و در همه جهات بالا برود، اما
496
00:19:53,440 –> 00:19:55,760
ممکن نبود زیرا
497
00:19:55,760 –> 00:19:56,640
498
00:19:56,640 –> 00:19:58,000
راس
499
00:19:58,000 –> 00:19:59,840
0 0
500
00:19:59,840 –> 00:20:03,360
در لبه است و نمی تواند بیشتر
501
00:20:03,360 –> 00:20:04,960
502
00:20:04,960 –> 00:20:07,919
از این در سمت چپ و در سمت بالا حرکت
503
00:20:07,919 –> 00:20:10,240
کند، اما همچنین
504
00:20:10,240 –> 00:20:13,520
به صورت مورب به سمت چپ رفت و
505
00:20:13,520 –> 00:20:16,640
یک راس در جهت 7 را دنبال
506
00:20:16,640 –> 00:20:20,400
کرد و یک راس 1 پیدا کرد.
507
00:20:20,400 –> 00:20:23,600
1 1 به عنوان یک
508
00:20:23,600 –> 00:20:26,960
نقطه پرش چون بعداً در راس 2 1
509
00:20:26,960 –> 00:20:30,240
به عنوان یک نقطه پرش شناخته
510
00:20:30,240 –> 00:20:33,280
می شود، کج است، می توانید ببینید که در صف اولویت قرار داده شده است
511
00:20:33,280 –> 00:20:35,760
و
512
00:20:35,760 –> 00:20:38,159
513
00:20:38,480 –> 00:20:42,960
اکنون که راس 1 1 را کشف کرده ایم، یک قدم جلوتر برویم.
514
00:20:42,960 –> 00:20:45,360
515
00:20:45,360 –> 00:20:47,440
قبلاً به شما گفتم که
516
00:20:47,440 –> 00:20:50,000
راس 2 1 به عنوان یک نقطه پرش شناخته
517
00:20:50,000 –> 00:20:50,960
می شود
518
00:20:50,960 –> 00:20:53,440
بنابراین راس 2
519
00:20:53,440 –> 00:20:56,320
1 در صف اولویت قرار می گیرد
520
00:20:56,320 –> 00:20:57,440
و
521
00:20:57,440 –> 00:20:59,520
در حال حاضر فقط
522
00:20:59,520 –> 00:21:02,480
راس 2 1 را در صف اولویت قرار داده ایم،
523
00:21:02,480 –> 00:21:04,640
همچنین می توانید متوجه شوید
524
00:21:04,640 –> 00:21:06,240
که با دنبال کردن جهت به راس
525
00:21:06,240 –> 00:21:07,600
2
526
00:21:07,600 –> 00:21:09,120
1 رسیده اید.
527
00:21:09,120 –> 00:21:10,480
528
00:21:10,480 –> 00:21:12,640
6
529
00:21:12,640 –> 00:21:13,840
و
530
00:21:13,840 –> 00:21:16,480
شما می توانید als o توجه کنید که هزینه کل
531
00:21:16,480 –> 00:21:18,240
آن 49 است.
532
00:21:18,240 –> 00:21:20,000
بیایید فقط سعی کنیم
533
00:21:20,000 –> 00:21:21,280
محاسبه
534
00:21:21,280 –> 00:21:24,240
کنیم که چگونه به این عدد 49 رسیدیم.
535
00:21:24,240 –> 00:21:26,720
536
00:21:26,720 –> 00:21:28,240
537
00:21:28,240 –> 00:21:30,400
538
00:21:30,400 –> 00:21:31,919
539
00:21:31,919 –> 00:21:34,720
540
00:21:34,720 –> 00:21:38,559
541
00:21:38,559 –> 00:21:41,120
542
00:21:41,120 –> 00:21:42,000
543
00:21:42,000 –> 00:21:44,480
در کنار
544
00:21:44,480 –> 00:21:46,799
آن 5
545
00:21:46,799 –> 00:21:52,080
10 15 20 25
546
00:21:52,080 –> 00:21:53,440
30
547
00:21:53,440 –> 00:21:56,080
37 است
548
00:21:57,280 –> 00:21:58,799
و
549
00:21:58,799 –> 00:22:04,159
فاصله آن 37 و 13
550
00:22:04,159 –> 00:22:05,520
است، باید
551
00:22:05,520 –> 00:22:09,280
37 و 13 را نشان دهد 50 49 شاید
552
00:22:09,280 –> 00:22:12,159
جایی را از دست داده ام اجازه دهید بررسی
553
00:22:12,159 –> 00:22:14,880
کنم بله وقتی دو هزینه را اضافه کردم خطا کردم.
554
00:22:14,880 –> 00:22:17,840
یک بار دیگر این بار به
555
00:22:17,840 –> 00:22:18,799
556
00:22:18,799 –> 00:22:19,919
ترتیب صحیح
557
00:22:19,919 –> 00:22:22,400
اوه هزینه تا کنون
558
00:22:22,400 –> 00:22:24,559
هفت و پنج است،
559
00:22:24,559 –> 00:22:27,360
من گفتم هفت و شش قبل از اینکه عذرخواهی
560
00:22:27,360 –> 00:22:29,039
کنم هفت است و پنج
561
00:22:29,039 –> 00:22:30,400
به دوازده،
562
00:22:30,400 –> 00:22:34,000
پس بیایید به این سمت برویم 12
563
00:22:34,000 –> 00:22:37,280
و به اضافه پنج 17
564
00:22:37,280 –> 00:22:38,960
22
565
00:22:38,960 –> 00:22:41,360
27
566
00:22:41,360 –> 00:22:43,039
32
567
00:22:43,039 –> 00:22:45,520
37
568
00:22:45,520 –> 00:22:47,280
42
569
00:22:47,280 –> 00:22:48,480
و 7
570
00:22:48,480 –> 00:22:50,080
یعنی 49
571
00:22:50,080 –> 00:22:51,600
بسیار خوب، پس
572
00:22:51,600 –> 00:22:53,679
اکنون می دانید که چگونه
573
00:22:53,679 –> 00:22:56,320
هزینه یک راس را محاسبه کنید،
574
00:22:56,320 –> 00:22:58,400
زمانی که آن را در صف اولویت قرار
575
00:22:58,400 –> 00:23:01,120
می دهید که همیشه سعی
576
00:23:01,120 –> 00:23:02,960
می کنید
577
00:23:02,960 –> 00:23:05,919
تا آنجا که می توانید مستقیم بروید و سپس
5