1354_lecture3_ver1 HarvardUniversity CS50_AI101 20 — Transcript

Full transcript

1. 0:04[музика]
2. 0:23Вітаю з поверненням на курс вступ до
3. 0:25штучного інтелекту з python ми вже
4. 0:27розглянули різні типи завдань ми
5. 0:29розглянули класичні завдання пошуку
6. 0:31дістатися від початкового стану до цілі
7. 0:34знаходячи оптимальний шлях ми розглянули
8. 0:37змагальний Пошук де був ігровий Агент Що
9. 0:39намагається зробити найкращий хід
10. 0:41завдання на основі знань де ми
11. 0:43використовували логіку та висновки щоби
12. 0:46мати можливість розуміти і робити
13. 0:47додаткові висновки ймовірність моделі де
14. 0:50ми можемо не мати певної інформації про
15. 0:52світ але використовуємо знання про
16. 0:54імовірності які у нас є щоби робити
17. 0:56висновки Сьогодні ми звернемо увагу на
18. 0:59іншу категорію за завдань завдання
19. 1:00оптимізації у яких оптимізація полягає у
20. 1:03виборі найкращого варіанта з набору
21. 1:05можливих варіантів ми вже бачили
22. 1:08оптимізацію наприклад в іграх де ми
23. 1:10створювали штучний інтелект що вибирає
24. 1:12найкращий хід з набору можливих ходів а
25. 1:15сьогодні розглянемо категорію типів
26. 1:17завдань і алгоритмів для їх вирішення
27. 1:20які можуть бути використані для
28. 1:22вирішення ширшого кола потенційних
29. 1:24завдань оптимізації розглянемо перший
30. 1:26алгоритм відомий як локальний пошук він
31. 1:30відрізняється від алгоритмів пошуку які
32. 1:32ми бачили раніше ті алгоритми пошуку
33. 1:34наприклад пошуку у ширину або пошук a
34. 1:36зірочка зазвичай підтримують купу різних
35. 1:39шляхів які ми одночасно досліджуємо і ми
36. 1:42розглядаємо купу різних шляхів одночасно
37. 1:45намагаючись знайти свій шлях до рішення
38. 1:47а в локальному пошуку алгоритм
39. 1:49працюватиме з одним вузлом і
40. 1:50розглядатиме один стан ми як правило
41. 1:53запускаємо алгоритм підтримуючи цей
42. 1:55єдиний вузол а потім переходимо до
43. 1:58одного з сусідних вузлів протягом усього
44. 2:00процесу
45. 2:02пошуку це корисно в контекстах не схожих
46. 2:05на завдання що ми бачили раніше як от
47. 2:07проходження лабіринту коли ми шукали
48. 2:09шлях від початкового стану до цілі ідучи
49. 2:12певним шляхом локальний пошук найчастіше
50. 2:15застосовують тоді коли нам зовсім
51. 2:17неважливий шлях а цікавить нас лише
52. 2:19рішення у випадку з лабіринтом рішення
53. 2:22завжди було очевидним ви можете вказати
54. 2:25на нього ви знаєте
55. 2:27ціль а реальне питання тому Яким шляхом
56. 2:31до нього дістатися локальний пошук
57. 2:33згодиться в тих випадках коли з'ясування
58. 2:35того яким є рішення якою є ціль суть
59. 2:37завдання наведу приклад такого завдання
60. 2:40розглянемо два типи будівель житлові
61. 2:42будинки та лікарні ціль полягає в тому
62. 2:45щоб у світі відформатованому у вигляді
63. 2:48сітки де в нас є купа будинків тут отут
64. 2:50два Там ми спробуємо знайти спосіб
65. 2:53розмістити дві лікарні на цій карті
66. 2:56наприклад лікарню тут і лікарню там
67. 2:59завдання полягає в тому щоб розмістити
68. 3:02дві лікарні на карті Однак не
69. 3:04випадково завдання в цьому випадку
70. 3:06полягає в тому щоби мінімізувати
71. 3:08Відстань від будь-якого будинку до
72. 3:11лікарні ви можете уявити яка відстань
73. 3:13від кожного будинку до найближчого
74. 3:15лікарні Існує кілька способів обчислити
75. 3:18цю відстань один із них полягає у
76. 3:20використанні евристики а саме
77. 3:22мангетенської відстані тобто уявлення
78. 3:25про те наскільки рядків і стовпчиків
79. 3:27треба переміститися по сідтці щоб
80. 3:29дістатися лікарні якщо взяти кожен з цих
81. 3:31чотирьох будинків і з'ясувати наскільки
82. 3:34близько Він стоїть до найближчої лікарні
83. 3:36то вийде наступне Цей будинок за три
84. 3:38комірки від лікарні Цей будинок за шість
85. 3:40а ці два будинки за чотири якщо скласти
86. 3:43всі цифри разом отримаємо загальну
87. 3:46вартість шляху 17 Отже для цієї
88. 3:48конкретної конфігурації лікарень лікарні
89. 3:50тут і тут цей стан має вартість
90. 3:5417 мета цього завдання для вирішення
91. 3:57якого ми застосовуємо алгоритм пошуку
92. 3:59полягає в тому щоб з'ясувати Чи можете
93. 4:02ви знайти спосіб мінімізувати цю
94. 4:04вартість мінімізувати загальну суму якщо
95. 4:07підсумувати всі відстані від усіх
96. 4:09будинків до найближчої лікарні як ми
97. 4:11можемо мінімізувати цю кінцеву вартість
98. 4:14якщо подумати про це завдання
99. 4:15абстрагуючись від цієї конкретної
100. 4:17проблеми і подумати про подібні завдання
101. 4:19загалом то їх часто можна сформулювати
102. 4:22думаючи про них як про ландшафт простору
103. 4:24станів на діаграмі ландшафту простору
104. 4:26станів кожна вертикальна смуга
105. 4:28представляє певну стан у якому може
106. 4:30перебувати наш світ наприклад кожна
107. 4:33вертикальна смуга представляє певну
108. 4:35конфігурацію двох
109. 4:37лікарень висота стовпчика як правило
110. 4:40буде представляти функцію цього стану
111. 4:43значення цього стану Можливо в цьому
112. 4:46випадку висота вертикальної смуги
113. 4:48відображає вартість цієї конкретної
114. 4:50конфігурації лікарень з точки зору Суми
115. 4:52всіх відстаней від усіх будинків до
116. 4:55найближчої
117. 4:57лікарні і взагалі коли йдеться про
118. 5:00ландшафт простору станів можна робити
119. 5:02одне з двох ми можемо намагатися
120. 5:05максимізувати значення функції
121. 5:07намагатися знайти глобальний максимум
122. 5:09цього ландшафту простору станів єдиний
123. 5:12стан значення Якого вище за всі інші
124. 5:15стани з яких можна вибирати коли ми
125. 5:18шукаємо глобальний максимум ми будемо
126. 5:20називати функцію яку намагаємося
127. 5:22оптимізувати цільовою функцією функцією
128. 5:25яка вимірює наскільки хороший
129. 5:28стан ми можемо взяти будь-який стан
130. 5:31передати його в цільову функцію і
131. 5:33отримати значення того наскільки він
132. 5:35хороший наша мета полягає в тому щоби
133. 5:37знайти стан який має найвище можливе
134. 5:40значення для цієї цільової функції
135. 5:42еквівалентною але зворотною проблемою є
136. 5:45пошук глобального мінімуму стану який
137. 5:47має найнижче значення зпоміж усіх
138. 5:50можливих після того як Ви передали його
139. 5:52у функцію коли ми шукаємо глобальней
140. 5:54мінімум ми називаємо функцію яку
141. 5:56обчислюємо вартісною функцією як правило
142. 6:00кожен стан має певну вартість чи то
143. 6:02грошову чи то часову чи у випадку з
144. 6:04будинками та лікарнями вартість у
145. 6:06вигляді відстані тобто наскільки далеко
146. 6:09кожен Будинок розташований від
147. 6:11лікарні Ми хочемо мінімізувати вартість
148. 6:14знайти стан який має найнижче можливе
149. 6:16значення цієї
150. 6:18вартості Отже це загальні типи ідей які
151. 6:21можна розглядати за допомогою ландшафту
152. 6:23простору станів шукаючи глобальний
153. 6:25максимум або глобальний мінімум Як же це
154. 6:28зробити згадаємо що в локальному пошуку
155. 6:31ми зазвичай працюємо за цим алгоритмом
156. 6:34підтримуючи лише один Поточний стан
157. 6:36представлений у середині вузла можливо
158. 6:38всередині структури даних де ми
159. 6:40відстежуємо поточне місце перебування а
160. 6:43потім ми збираємося перейти з цього
161. 6:45стану до одного з сусідніх станів які в
162. 6:48цьому випадку представлені в
163. 6:50одновимірному просторі станом що
164. 6:52розташований ліорич або праворуч але для
165. 6:55будь-якого іншого завдання ви можете
166. 6:56визначити що означає бути сусідом у
167. 6:59випадку з лікарнями сусіднім може бути
168. 7:01стан в якому перемістила одну лікарню на
169. 7:03один простір ліворуч або праворуч вгору
170. 7:06або вниз до стану близького до поточного
171. 7:09Але дещо відмінного як наслідок він може
172. 7:12мати дещо інше значення з точки зору
173. 7:14цільової або вартісної
174. 7:16функції це буде нашою загальною
175. 7:18стратегією в локальному пошуку мати
176. 7:20можливість узяти стан зберігаючи
177. 7:22поточний вузол і рухатися туди куди ми
178. 7:25дивимося в ландшафті простору станів
179. 7:27щоби знайти глобальний максимум або
180. 7:29глобальний мінімум мабуть найпростіший
181. 7:31алгоритм який можна використати для
182. 7:34реалізації ідеї локального пошуку - це
183. 7:36алгоритм сходження на вершину яка
184. 7:38основна ідея алгоритму сходження на
185. 7:40вершину скажімо я намагаюся
186. 7:41максимізувати значення стану шукаю де
187. 7:44глобальний максимум почну зі свого стану
188. 7:47як правило під час сходження на вершину
189. 7:49я розглядаю сусідів цього стану з цього
190. 7:52стану я можу піти ліворуч або праворуч
191. 7:54цей сусід вищий А цей нижчий у сходженні
192. 7:58на вершину якщо я хочу зувати значення я
193. 8:00обираю найвищу вершину між станами лівим
194. 8:03і правим цей стан вищий тому Я продовжую
195. 8:06рухатися вперед щоб розглянути його і
196. 8:09потім повторюю процес безперервно
197. 8:11дивлячись на всіх сусідів і вибираючи
198. 8:13найвищого дивлячись на сусідів і
199. 8:15вибираючи найвищого Доки не дійду до ось
200. 8:18такої точки де я дивлюся на обох сусідів
201. 8:20і вони обидва мають менше значення ніж
202. 8:23я цей Поточний стан має значення вище
203. 8:27ніж у будь-якого сусіда на цьому моменті
204. 8:29алгоритм закінчився А я можу сказати
205. 8:32рішення
206. 8:33знайдено те саме працює абсолютно
207. 8:35протилежно при спробі знайти глобальний
208. 8:37мінімум але алгоритм той самий якщо я
209. 8:40хочу знайти глобальний мінімум а
210. 8:41Поточний стан починається тут я буду
211. 8:43дивитися на сусідів вибирати найнижче
212. 8:45можливе значення поки не знайду
213. 8:47глобальний мінімум точку в якій коли я
214. 8:50дивлюся на обох сусідів Кожен з яких має
215. 8:52більше значення і намагаюся мінімізувати
216. 8:55загальну вартість або значення яке я
217. 8:57отримую в результаті обчислення
218. 8:59вартісної
219. 9:01функції Отже сформулюємо цю графічну
220. 9:04ідею у псевдокоді псевдокод для
221. 9:06сходження на вершину може мати Такий
222. 9:08вигляд Ми визначаємо функцію Hill Climb
223. 9:11яка бере за вхідні дані проблему яку ми
224. 9:13вирішуємо І взагалі починаємо з
225. 9:16початкового стану я почну зі зміною
226. 9:18carent яка відстежує початковий стан
227. 9:20наприклад початкову конфігурацію
228. 9:22лікарень У деяких завданнях є початковий
229. 9:25стан тобто якесь місце з якого ви
230. 9:27починаєте У деяких ні але тоді ми можемо
231. 9:30випадково згенерувати початковий стан
232. 9:32вибравши навмання два місця для лікарень
233. 9:34і будемо з'ясовувати як поліпшити
234. 9:37ситуацію але цей початковий стан ми
235. 9:39збережемо всередині змінної Кан і тепер
236. 9:42починається цикл повторюваний процес
237. 9:45який ми будемо виконувати знову і знову
238. 9:47поки алгоритм не завершиться Що ж ми
239. 9:49будемо робити по-перше з'ясуємо всіх
240. 9:51сусідів поточного стану які в мого стану
241. 9:54є сусіди зважаємо на визначення терміну
242. 9:57сусід я ви беру сусіда з найбільшим
243. 10:00значенням і збережу його у змінній під
244. 10:02назвою neighbor щоби відстежувати сусіда
245. 10:06з найбільшим значенням це коли я
246. 10:08намагаюся максимізувати значення Якщо ж
247. 10:10потрібно мінімізувати значення виберіть
248. 10:12сусіда з найнижчим можливим значенням
249. 10:14але ці ідеї фундаментально взаємозамінні
250. 10:17Цілком можливо що в деяких випадках може
251. 10:19бути кілька сусідів Кожен з яких має
252. 10:21однаково високе або однаково низьке
253. 10:24значення у такому разі можна випадковим
254. 10:26чином вибрати одного і просто зберегти
255. 10:28його у змінній neighbor і потім ключове
256. 10:32питання чи цей сусід кращий за мій
257. 10:34Поточний
258. 10:36стан і якщо найкращий сусід якого я зміг
259. 10:40знайти не кращий за мій Поточний стан
260. 10:43тоді алгоритм закінчився і я повернуся
261. 10:46до поточного стану якщо жоден з моїх
262. 10:48сусідів не кращий тоді я лишуся на місці
263. 10:51така загальна логіка алгоритму сходження
264. 10:53на вершину але якщо сусід кращий тоді я
265. 10:56можу переміститися до нього тобто карень
266. 10:59дорівнює neighbр ідея полягає в тому що
267. 11:01якщо я перебуваю в поточному стані і
268. 11:03бачу сусіда Кращого за мене тоді я
269. 11:05перейду до нього а потім повторюватиму
270. 11:07процес постійно рухаючись до кращого
271. 11:09сусіда Доки не досягну точки в якій
272. 11:12жоден сусід не буде кращим тоді можемо
273. 11:15сказати що алгоритм завершився
274. 11:17подивімося на реальний приклад з
275. 11:18будинками і лікарнями якщо ми розмістимо
276. 11:21лікарні в цих місцях тоді їхня загальна
277. 11:23вартість дорівнює 17 якщо ми збираємося
278. 11:26реалізувати алгоритм сходження на
279. 11:28вершину тоді потрібно визначити що
280. 11:30означає взяти цю конфігурацію лікарень
281. 11:32цей конкретний стан і отримати сусіда
282. 11:34цього стану що в цьому випадку означає
283. 11:37сусід візьмемо лікарню і пересунемо її
284. 11:40на клітинку ліворуч праворуч вгору або
285. 11:42вниз тоді в нас буде шість можливих
286. 11:44сусідів цієї конкретної
287. 11:47конфігурації можна взяти одну лікарню і
288. 11:49перемістити її в будь-який із трьох
289. 11:51квадратів або взяти другу лікарню і
290. 11:53перемістити її в будь-який із трьох
291. 11:55квадратів і в кожному з них з'явиться
292. 11:58сусід що ж мені робити ось розташування
293. 12:00і відстані між кожним будинком і
294. 12:02найближчою лікарнею я розгляну всіх
295. 12:06сусідів і подивлюся чи може хтось із них
296. 12:09запропонувати кращу вартість ніж 17
297. 12:11Виявляється що є кілька способів зробити
298. 12:13це і неважливо якщо ми випадково
299. 12:16виберемо серед них найкращий один з
300. 12:18таких можливих способів це поглянути на
301. 12:21цю лікарню і розглянути напрямки в яких
302. 12:24вона може рухатися а цю лишимо незмінною
303. 12:27беремо цю лікарню і переміщаємо
304. 12:29на квадрат угору Це нам не дуже допоможе
305. 12:31вона стане ближчою до цього будинку але
306. 12:33більш віддаленою від цього плюс нічого
307. 12:35не зміниться для цих двох будинків Але
308. 12:37якщо ми візьмемо цю лікарню і
309. 12:39перемістимо її на один квадрат униз
310. 12:42виникне протилежна проблема вона
311. 12:44віддаляється від верхнього будинку і
312. 12:46наближається до нижнього а насправді
313. 12:48потрібно перемістити лікарню на один
314. 12:49квадрат ліворуч перемістивши її на один
315. 12:52квадрат ліворуч ми наблизимо її до обох
316. 12:54будинків праворуч нічого не змінюючи для
317. 12:57будинків ліворуч для них ця лікарня все
318. 13:00одно ближча тому на них це не вплине ми
319. 13:02можемо поліпшити ситуацію обравши сусіда
320. 13:05який приведе до зменшення загальної
321. 13:07вартості зробити Це можна перемістивши
322. 13:10із нинішнього стану до сусіда просто
323. 13:13взявши лікарню і перемістивши її на цей
324. 13:16момент з цією лікарнею не так вже і
325. 13:18багато можна зробити але є інші
326. 13:20оптимізації які ми можемо зробити інші
327. 13:22сусіди до яких можна переміститися і які
328. 13:25отримають краще значення візьмемо цю
329. 13:27лікарню ви бачи що вона розташована вище
330. 13:30ніж обидва Ці будинки можна поліпшити
331. 13:33ситуацію перемістивши її на один квадрат
332. 13:35униз так щоб ми знизили вартість до 13
333. 13:38для цієї конкретної конфігурації ми
334. 13:41можемо зробити ще краще Якщо перемістимо
335. 13:43її на одну клітинку ліворуч тепер ми
336. 13:46маємо вартість 11 тому що Цей будинок
337. 13:48розташований на відстані однієї клітини
338. 13:51від лікарні а цей на відстані чотирьох
339. 13:53цей на відстані трьох і цей теж трьох
340. 13:56Отже ми досягли набагато кращої вартості
341. 13:58ніж на початку із початковою
342. 14:00конфігурацією просто взявши кожен стан і
343. 14:02поставивши собі питання Чи можемо ми
344. 14:05зробити краще роблячи невеличкі зміни
345. 14:07переходячи до одного сусіда до іншого і
346. 14:10так далі ми можемо побачити що на цьому
347. 14:13етапі алгоритм може
348. 14:14завершитися немає жодного сусіда до
349. 14:17якого можна прийти щоби поліпшити
350. 14:19ситуацію і отримати вартість меншу за 11
351. 14:22бо якщо ми візьмемо цю лікарню і
352. 14:24перенесемо її вгору або праворуч вона
353. 14:27стане ще далі якщо перенесе її вниз це
354. 14:29не змінить ситуації вона стане далі від
355. 14:32цього будинку але ближче до цього так
356. 14:34само і з цією лікарнею будь-який сусіду
357. 14:37якого ми її перемістимо вгору ліворуч
358. 14:39вниз чи праворуч або віддалить її від
359. 14:41будинків і збільшить вартість або це не
360. 14:43матиме жодного впливу на вартість
361. 14:46питання яке ми можемо зараз поставити Чи
362. 14:49це найкраще що ми могли зробити Чи це
363. 14:51найкраще розміщення лікарень яке ми
364. 14:54могли б мати Виявляється що відповідь ні
365. 14:56бо є кращий спосіб розмістити Ліка
366. 14:58лікарні є навіть кілька способів як це
367. 15:00зробити один із них узяти цю лікарню і
368. 15:03перемістити її по діагоналі на цей
369. 15:05квадрат який не входить у визначення
370. 15:08сусід ми могли рухатися тільки ліворуч
371. 15:11праворуч вгору або вниз але так явно
372. 15:13краще тепер загальна вартість дев'ять
373. 15:16тепер лікарня ближча до обох будинків як
374. 15:19наслідок загальна вартість менша Але ми
375. 15:21не змогли знайти цей стан бо для цього
376. 15:23нам довелося пройти через стан який
377. 15:25нічим не кращий за той в якому ми
378. 15:28перебували раніше це обмеження може
379. 15:30виникнути у вас коли ви намагаєтеся
380. 15:32реалізувати алгоритм сходження на
381. 15:34вершину воно полягає в тому що він не
382. 15:37завжди може дати оптимальне рішення якщо
383. 15:39ми намагаємося максимізувати значення
384. 15:41тобто знайти глобальний максимум може
385. 15:43виникнути побоювання що ми можемо
386. 15:45застрягти в одному з локальних
387. 15:47максимумів він виділений синім кольором
388. 15:50локальний максимум - це будь-який стан
389. 15:52значення Якого вище ніж у сусіда якщо ми
390. 15:55опинимося в одному з цих двох станів
391. 15:57намагаючись максимізувати значення стану
392. 15:59ми не будемо робити жодних змін Не
393. 16:02будемо рухатися праворуч або ліворуч бо
394. 16:04там ще
395. 16:05гірше Але все-таки ми не знайшли
396. 16:07глобального оптимуму ми не зробили все
397. 16:10що могли так само і у випадку з
398. 16:13лікарнями Ми намагаємося знайти
399. 16:14глобальний мінімум тобто значення яке
400. 16:17буде нижчим ніж у всіх інших але ми
401. 16:19можемо застрягти на одному з локальних
402. 16:21мінімумів у будь-якому з цих станів чиє
403. 16:24значення нижче ніж у всіх його сусідів
404. 16:27але все ще не настільки ке як локальний
405. 16:29мінімум висновок полягає в тому що не
406. 16:31завжди коли ми запускаємо безхідрісний
407. 16:34алгоритм сходження на вершину ми
408. 16:36знайдемо оптимальне рішення щось може
409. 16:38піти не так наприклад якщо почнемо
410. 16:40звідси і спробуємо максимізувати
411. 16:43значення ми перейдемо до найвищого
412. 16:45сусіда перейдемо до найвищого сусіда
413. 16:47перейдемо до найвищого сусіда і
414. 16:49зупинимося так і не зрозумівши що є
415. 16:52навіть кращий стан до якого ми могли б
416. 16:54дійти інші проблеми які ви можете уявити
417. 16:57просто поглянувши на ландшафт простору
418. 16:59станів - це різні типи плато Щось на
419. 17:01кшталт цього плаского локального
420. 17:03максимуму де всі шість станів мають
421. 17:05абсолютно однакове значення тобто в разі
422. 17:08застосування алгоритму який ми показали
423. 17:10раніше Жоден із сусідів не кращий Тобто
424. 17:13ми можемо застрягти На цьому пласкому
425. 17:15локальному максимумі і навіть якщо ви
426. 17:17дозволите собі переміститися до одного з
427. 17:19сусідів буде незрозуміло до якого йти І
428. 17:22Ви також можете застрягнути тут А ось
429. 17:24тут є ще один це називається плече Це не
430. 17:27зовсім локальне Макс бо є місце де ми
431. 17:29можемо піднятися вище і не локальний
432. 17:31мінімум бо можемо опуститися нижче
433. 17:34просуватися вперед можна але це пласка
434. 17:37ділянка де Якщо у вас є алгоритм
435. 17:39локального пошуку ви можете загубитися
436. 17:41не маючи можливості просунутися вгору
437. 17:43якщо ми намагаємося максимізувати або
438. 17:45вниз якщо намагаємося мінімізувати а
439. 17:48отже ми можемо знайти рішення яке
440. 17:50насправді може не бути оптимальним і
441. 17:51оскільки потенціал який дає сходження на
442. 17:54вершину не завжди дає оптимальний
443. 17:56результат Виявляється що існують різ
444. 17:58новиди та варіації алгоритму сходження
445. 18:00на вершину які допомагають вирішити
446. 18:02проблему краще залежно від контексту і
447. 18:05залежно від конкретного типу завдання
448. 18:07деякі з цих варіантів можуть бути більш
449. 18:09прийнятними ніж інші ми вже розглянули
450. 18:12версію сходження на вершину яка зазвичай
451. 18:14називається найстрімкіше сходження на
452. 18:17вершину Його ідея полягає в тому що Ми
453. 18:19обираємо сусіда з найбільшим значенням у
454. 18:21випадку якщо намагаємося максимізувати
455. 18:23або сусіда з найменшим значенням якщо
456. 18:25намагаємося мінімізувати але загалом
457. 18:27якщо у мене є п'ять сусідів і всі вони
458. 18:29кращі за мій Поточний стан я вибера
459. 18:31найкращого З цих п'яти іноді це Може
460. 18:33спрацювати досить добре це свого роду
461. 18:35жадібний підхід коли намагаєшся зробити
462. 18:37найкращу операцію на кожному конкретному
463. 18:39кроці але це не завжди може спрацювати
464. 18:41бувають випадки коли я хочу обрати
465. 18:43варіант який кращі тільки трішки не
466. 18:45найкращі бо згодом це може привести до
467. 18:48ще кращого результату є й інші варіанти
468. 18:51базового алгоритму один з них
469. 18:53стохастичне сходження на вершину у цьому
470. 18:55випадку ми вибираємо випадково з усіх
471. 18:57сусідів які мають бі більше значення
472. 18:59якщо в поточному стані є п'ять кращих
473. 19:01сусідів то замість вибору найкращого як
474. 19:03при найстрімкішому сходженні
475. 19:05стохастичний алгоритм вибере випадково
476. 19:07одного з них думаючи що він кращий І
477. 19:09можливо є потенціал для подальшого
478. 19:11прогресу навіть якщо це не найкращий
479. 19:13локальний варіант який можна було би
480. 19:15вибрати першочергове сходження на
481. 19:17вершину полягає у виборі найпершого
482. 19:19сусіда який має найбільше значення Але З
483. 19:22цього випливає і поведінка за схожою
484. 19:24ідею замість того щоб розглядати всіх
485. 19:26сусідів Як тільки ми знайдемо сусі
486. 19:28Кращого за наш поточний стан ми
487. 19:30перейдемо до нього Можливо там є певні
488. 19:32поліпшення ефективності можливо є
489. 19:34потенціал для пошуку рішення яке інші
490. 19:36стратегії не змогли знайти і навіть з
491. 19:38усіма цими варіантами все одно є
492. 19:40потенційний ризик опинитися на
493. 19:42локальному мінімумі або локальному
494. 19:43максимумі цей ризик можна зменшити
495. 19:45повторюючи процес кілька разів ще один
496. 19:48варіант сходження на вершину - це
497. 19:49сходження на вершину з випадковим
498. 19:51перезаписком ідея полягає в тому що ми
499. 19:53можемо сходити на вершину кілька разів
500. 19:55якщо ми застосуємо найстрімкіше
501. 19:57сходження на вершину то почнемо з
502. 19:59якогось випадкового стану спробуємо
503. 20:01з'ясувати як вирішити завдання з'ясуємо
504. 20:04до якого локального максимуму або
505. 20:06локального мінімуму ми дійдемо а потім
506. 20:08ми випадково почнемо заново і спробуємо
507. 20:10ще раз виберемо нову стартову
508. 20:13конфігурацію спробуємо з'ясувати у який
509. 20:15локальний максимум або мінімум і зробимо
510. 20:17Це кілька разів А після цього зможемо
511. 20:19вибрати найкращий варіант з усіх
512. 20:21розглянутих Отже це ще один можливий
513. 20:24варіант І хоча я казав що зазвичай
514. 20:26локальний пошук просто відстежиє один
515. 20:28вузел а потім переходить до одного з
516. 20:30його сусідів існують і інші варіанти
517. 20:32сходження на вершину наприклад локальний
518. 20:34променевий Пошук де замість того щоб
519. 20:36відстежувати лише один поточний
520. 20:38найкращий стан ми відстежуємо ке сусідів
521. 20:40із більшим значенням тобто замість того
522. 20:42щоб починати з однієї випадкової
523. 20:43початкової конфігурації ми відстежуємо
524. 20:46три-чотири або п'ять випадково
525. 20:47згенерованих сусідів а потім виберемо
526. 20:49три-чотири або п'ять найкращих зпоміж
527. 20:52них і будемо постійно повторювати процес
528. 20:54із думкою що тепер ми маємо більше
529. 20:57варіантів для роз Ду і більше шляхів
530. 20:59пошуку оптимального
531. 21:01рішення тож подивімось на реальний код
532. 21:04який може реалізувати деякі з цих ідей
533. 21:07наприклад найстрімкіше сходження на
534. 21:09вершину для вирішення завдання з
535. 21:12лікарнями я перейду до каталогу
536. 21:14hospitals де створив базову структуру
537. 21:16для вирішення завдань такого типу
538. 21:19відкрию файл
539. 21:20hospitals.p і ми з вами переглядемо код
540. 21:24я визначив клас Space який
541. 21:26представлятиме простір станів цей клас
542. 21:28має висоту ширину а також певну
543. 21:31кількість лікарень Тобто ви можете
544. 21:32налаштувати розмір карти кількість
545. 21:34лікарень є функція додавання нового
546. 21:37будинку до простору станів а також деякі
547. 21:40функції які нададуть мені всі доступні
548. 21:42місця якщо я захочу розмістити лікарні
549. 21:45Випадково А ось і алгоритм сходження на
550. 21:48вершину Отже що ми будемо робити в
551. 21:51алгоритмі сходження на вершину почнемо з
552. 21:53випадкової ініціалізації місця
553. 21:55розташування лікарень ми не знаємо де
554. 21:57вони мають бути тому розмістимо їх
555. 21:59випадково я запускаю цикл для кожної
556. 22:03лікарні потім додаю нову лікарню у
557. 22:06випадковому
558. 22:08місці отримую всі доступні місця і
559. 22:11випадковим чином обираю одне з них як
560. 22:13місце куди я хочу додати цю конкретну
561. 22:15лікарню В мене є логування розміщення та
562. 22:18генерування зображень які ми розглянемо
563. 22:21пізніше але ось ключова ідея я продовжу
564. 22:23повторювати лгоритм я можу вказати
565. 22:26максимальну кількість повторень а бо
566. 22:28запускатиме його доти доки він не
567. 22:30досягне локального максимуму або
568. 22:32локального мінімуму А тепер ми
569. 22:34розглянемо всі лікарні які потенційно
570. 22:36можна перемістити розглянемо кожну з
571. 22:38двох лікарень або більше якщо їх більше
572. 22:40і розглянемо всі місця куди лікарня може
573. 22:43переміститися сусідів цієї лікарні куди
574. 22:45ми можемо її перемістити а потім
575. 22:48подивимося чи буде це краще ніж те місце
576. 22:51де вона стоїть зараз якщо позиція буде
577. 22:54кращою тоді ми продовжимо оновлювати
578. 22:56найкращого сусі і будемо його
579. 22:59відстежувати потім ми можемо поставити
580. 23:01собі питання що робити якщо вартість
581. 23:04найкращого сусіда більша або дорівнює
582. 23:06вартості поточного набору лікарень тобто
583. 23:09якщо вартість найкращого сусіда більша
584. 23:11за поточну вартість тобто якщо найкращий
585. 23:13сусідній стан гірший за Поточний стан
586. 23:16Тоді не варто робити жодних змін і варто
587. 23:19повернути поточний набір лікарень але
588. 23:23якщо інакше тоді можна оновити лікарні
589. 23:25щоби замінити їх на одного найкращих
590. 23:28сусідів А якщо є кілька рівноцінних
591. 23:30розташувань Я використовую
592. 23:32randomкраchoice щоби вибрати одне з них
593. 23:34випадково це реалізація на пайтоні цієї
594. 23:37ідеї про яку Ми щойно говорили ідеє
595. 23:40взяти Поточний стан поточний набір
596. 23:41лікарень згенерувати всіх сусідів
597. 23:44переглянути всі способи якими ми можемо
598. 23:46взяти лікарню і перемістити її на
599. 23:48клітинку ліворуч праворуч вгору або вниз
600. 23:51а потім на основі цієї інформації
601. 23:52з'ясувати найкращий сусідній стан або
602. 23:55набір найкращих сусідів і вибрати з них
603. 23:57один щоби зробити це Ми щоразу генеруємо
604. 24:00зображення А зараз подивимося на кінець
605. 24:03коду я випадковим чином згенерую простір
606. 24:06заввишки 10 і завширшки 20 у якому
607. 24:09розміщу три лікарні я випадковим чином
608. 24:12згенерую 15 будинків які додам у
609. 24:15випадкові місця а потім я запущу
610. 24:17алгоритм сходження на вершину щоб
611. 24:19з'ясувати де ж розмістити ці
612. 24:22лікарні запускаємо програму запускаючи
613. 24:25python hospitals Як ви бачите споча
614. 24:28початковий стан мав вартість 72 але ми
615. 24:30постійно знаходили сусідні стани які
616. 24:32змогли зменшити вартість до
617. 24:356966 і аж до 53
618. 24:38це найкращий сусід якого ми
619. 24:40знайшли Ми можемо побачити графічне
620. 24:43зображення відкривши файл ось наприклад
621. 24:46початкова
622. 24:47конфігурація ми випадковим чином вибрали
623. 24:50місце для всіх 15 будинків а потім
624. 24:53випадковим чином вибрали місця для трьох
625. 24:55лікарень які були розташовані десь у
626. 24:58сеередині простору станів якщо скласти
627. 25:01всі відстані від кожного будинка до
628. 25:03найближчої лікарні то вийде загальна
629. 25:05вартість
630. 25:0672 тепер постає питання до яких сусідів
631. 25:09ми можемо переміститися щоби поліпшити
632. 25:11ситуацію першим алгоритм знайшов оцю
633. 25:14лікарню праворуч і перемістив її ліворуч
634. 25:17це логічно бо якщо ви подивитеся на
635. 25:20будинки в цьому районі то п'ять будинків
636. 25:22будуть найближчими до цієї лікарні
637. 25:25переміщення її ліворуч зменшує загальну
638. 25:27відстань принаймні до більшості цих
639. 25:29будинків хоча й збільшує відстань до
640. 25:32одного з них Таким чином ми можемо
641. 25:34поліпшувати ситуацію постійно знаходячи
642. 25:37способи переміщення лікарень поки не
643. 25:39зупинимося на цьому конкретному стані з
644. 25:43вартістю
645. 25:4653 ми визначили місце для кожної лікарні
646. 25:49і тепер жоден сусід до яких ми можемо
647. 25:51переміститися не поліпшить ситуації ми
648. 25:54можемо взяти цю лікарню і цю лікарню і
649. 25:57цю лікарню подивитись на кожного сусіда
650. 25:59і Кожен з них не буде кращим за цю
651. 26:01конкретну конфігурацію зновутаки це не
652. 26:04обов'язково найкращий варіант може
653. 26:06існувати якась інша конфігурація
654. 26:07лікарень яка є глобальним мінімумом А ця
655. 26:10може бути локальним мінімумом тобто
656. 26:12найкращою з усіх сусідніх Але можливо не
657. 26:15найкращою в усьому можливому просторі
658. 26:17станів можна шукати по всьому простору
659. 26:19станів розглядаючи всі можливі
660. 26:21конфігурації але це займе багато часу
661. 26:24особливо з огляду на те що простір
662. 26:26станів стає більшим і можливих станів
663. 26:29теж може бути більше щоби переглянути їх
664. 26:31усі знадобиться багато часу тому
665. 26:34можливість використовувати такі
666. 26:35алгоритми локального пошуку часто може
667. 26:38бути корисною для пошуку найкращого
668. 26:40рішення особливо якщо ми не дбаємо про
669. 26:42те щоби зробити якнайкраще а просто
670. 26:45хочемо зробити все добре і знайти вдале
671. 26:47розміщення лікарень звісно ми можемо
672. 26:50спробувати пом'якшити деякі проблеми
673. 26:52використовуючи випадковий перезапуск
674. 26:54замість сходження на вершину ідея
675. 26:56полягає в тому що замість одноразового
676. 26:58сходження на вершину ми можемо
677. 27:00використати цей алгоритм безліч разів на
678. 27:02одній і тій самій карті і з'ясувати який
679. 27:04варіант найкращий я реалізував функцію
680. 27:07Random
681. 27:08restart яка перезапускає алгоритм певну
682. 27:11максимальну кількість разів цей процес
683. 27:14треба повторити цю кількість разів
684. 27:16запустити алгоритм сходження на
685. 27:18вершину з'ясувати Яка вартість шляху від
686. 27:22усіх будинків до лікарень а потім
687. 27:24з'ясувати чи це краще за те що ми робили
688. 27:27до цього я можу спробувати цю саму ідею
689. 27:29де замість запуску hillim я запущу ROM і
690. 27:34я випадково перезапущу наприклад 20
691. 27:36разів продовжуємо зараз я видаляю всі
692. 27:39зображення а потім перезапущу програму
693. 27:42починаємо з пошуку початкового стану
694. 27:44коли ми запустили сходження на вершину
695. 27:46то найкраща вартість яку ми змогли
696. 27:48знайти була 56 кожна ітерація - це
697. 27:51окрема ітерація алгоритму сходження на
698. 27:53вершину ми запускаємо алгоритм не один
699. 27:55раз а 20 разів постійно поки ки не
700. 27:57знайдемо локальний мінімум і щоразу ми
701. 28:00дивимося Чи вдалося нам досягти кращого
702. 28:02результату ніж попередні ми перейшли від
703. 28:0556 до 46 це більше ігноруємо це 41 що
704. 28:10менше ми його лишили і продовжили і за
705. 28:12всі інші 16 разів коли ми запускали
706. 28:15алгоритм сходження на вершину ми не
707. 28:17знайшли нічого кращого за 41 зновутаки
708. 28:21можливо є спосіб зробити краще який ми
709. 28:23просто не знайшли але Схоже що цей
710. 28:26спосіб виявився досить не поганим
711. 28:28рішенням завдання Це була третя спроба
712. 28:31можемо поглянути на неї відкрити файл
713. 28:33номер
714. 28:34три Ось цей стан має вартість
715. 28:3741 після запуску алгоритму сходження на
716. 28:40вершину для певної випадкової початкової
717. 28:42конфігурації лікарень це було локальним
718. 28:44мінімумом з точки зору спроби
719. 28:47мінімізувати вартість нам це непогано
720. 28:49вдалося адже будинки в цьому районі
721. 28:51близькі до цієї лікарні будинки в цьому
722. 28:54до цієї лікарні Та й ця Лікарня
723. 28:56розташована максимально вдала відносно
724. 28:58будинків Отже такі алгоритми можуть бути
725. 29:00корисними для розв'язку подібних
726. 29:03завдань але реальна проблема багатьох
727. 29:06цих видів алгоритмів сходження на
728. 29:08вершину крутого стохастичного
729. 29:10першочергового тощо полягає в тому що
730. 29:12вони ніколи не роблять кроку який
731. 29:14погіршує нашу ситуацію Вони завжди
732. 29:16беруть Поточний стан дивляться на
733. 29:18сусідів і думають Чи можемо ми зробити
734. 29:20краще і переміщаються до цього сусіда
735. 29:23кого із сусідів ми оберемо залежить від
736. 29:26різних типів алгорит
737. 29:27але ми ніколи не переходимо з поточної
738. 29:29позиції в гіршу позицію зрештою це і
739. 29:32потрібно робити якщо ми шукаємо
740. 29:33глобальний максимум або глобальний
741. 29:35мінімум бо іноді якщо Ми застрягли Ми
742. 29:38хочемо знайти спосіб відійти від
743. 29:40локального максимуму або локального
744. 29:42мінімуму щоб знайти глобальний максимум
745. 29:44або глобальний мінімум або збільшити
746. 29:46імовірність знаходження найпопулярнішою
747. 29:49технікою яка намагається підійти до
748. 29:51завдання під цим кутом зору є імітація
749. 29:53відпалу це моделювання реального
750. 29:56фізичного процесу відпалу думайте про це
751. 29:58І з точки зору фізики фізичної ситуації
752. 30:01Де у вас є певна система частинок Уявіть
753. 30:04що коли ви нагріваєте певну фізичну
754. 30:06систему там з'являється багато енергії
755. 30:08усе рухається хаотично але з часом Коли
756. 30:11система остигає вона застигає в якомусь
757. 30:13кінцевому положенні цей буде загальною
758. 30:16ідеєю імітацію відпалу ми імітуватимемо
759. 30:20процес високотемпературної системи у
760. 30:22якій усе рухається хаотично але з часом
761. 30:25температура знижується тобто зрештою ми
762. 30:28дійдемо до остаточного рішення ідея
763. 30:31полягає в тому що от у нас є ландшафт
764. 30:33простору станів ми починаємо з
765. 30:35початкового стану якщо ми намагаємося
766. 30:38максимізувати значення стану наші
767. 30:40традиційні алгоритми сходження на
768. 30:42вершину візьмуть стан подивляться на
769. 30:45двох сусідів і завжди оберуть того який
770. 30:48збільшить значення
771. 30:50стану Але якщо ми хочемо мати Хоч якийсь
772. 30:53шанс знайти глобальний максимум Ми не
773. 30:56можемо завжди робити правильні кроки Ми
774. 30:58повинні іноді робити погані кроки І
775. 31:00дозволяти собі рухатися у напрямку який
776. 31:03як нам здається на цей момент погіршає
777. 31:06ситуацію щоби потім знайти шлях до
778. 31:08глобального
779. 31:10максимуму звісно коли ми досягнемо
780. 31:12глобального максимуму коли виконаємо не
781. 31:15один пошук тоді ми ймовірно не захочемо
782. 31:18рухатися до станів гірших за Поточний
783. 31:20стан і саме Тут з'являється схожість до
784. 31:23відпалу коли ми починаємо виконувати
785. 31:25більше випадкових рухів але з м їх
786. 31:27кількість зменшується що засновано на
787. 31:30температурному графікові основна схема
788. 31:32приблизно така на початку імітації
789. 31:34відпалу ми маємо вищий температурний
790. 31:37стан під вищим температурним станом ми
791. 31:40маємо на увазі що ми з більшою
792. 31:42імовірністю Приймемо сусідів які гірший
793. 31:45за Поточний стан що якщо один із сусідів
794. 31:47гірший за Поточний стан особливо якщо не
795. 31:50набагато гірший а трішки гірший то ми з
796. 31:52більшою імовірністю приймемо це і
797. 31:54перейдемо до цього сусіда в будь-якому
798. 31:57випадку але пізніше коли ми запустимо
799. 31:59імітацію відпалу ми знизимо температуру
800. 32:02А при нижчій температурі ми зменшуємо
801. 32:05вірністю Приймемо сусідів гірших за
802. 32:07Поточний стан тепер формалізуємо запис
803. 32:10за допомогою псевдокоду У нас є функція
804. 32:13simulated eniling яка приймає як вхідні
805. 32:16дані завдання яке Ми намагаємося
806. 32:18вирішити а також потенційну деяку
807. 32:20максимальну кількість разів запуску
808. 32:22імітації відпалу разів пошуку сусідів це
809. 32:25значення буде змінюватися залеж від
810. 32:27завдання ми знову почнемо з поточного
811. 32:30стану який буде дорівнювати початковому
812. 32:32стану завдання але тепер нам потрібно
813. 32:34повторити цей процес знову і знову
814. 32:36максимальну кількість разів Спочатку ми
815. 32:38обчислимо температуру функція tempче
816. 32:42бере поточний час ті починаючи з одиниці
817. 32:45і доходячи до максимуму а потім дає нам
818. 32:48температуру яку ми можемо
819. 32:50використовувати в обчисленнях ідея
820. 32:53полягає в тому що ця Температура буде
821. 32:55вищою на початку а потім буде
822. 32:57нижчою функція тече може працювати
823. 33:00кількома способами один з найпростіших -
824. 33:03це сказати що вона як пропорція часу що
825. 33:05нам лишився скільки часу у нас лишилося
826. 33:08виходячи зі значення максимуму спочатку
827. 33:10у вас буде багато часу але згодом
828. 33:12Температура буде знижуватися бо у вас
829. 33:14лишається дедалі менше
830. 33:17часу обчислюємо температуру для
831. 33:19поточного часу а потім обираємо
832. 33:21випадкового сусіда ми більше не будемо
833. 33:25обирати найкращого сусіда або з
834. 33:27найкращих ми виберемо випадкового сусіда
835. 33:30він може бути кращим може бути гіршим
836. 33:32але ми це вирахуємо ми обчислимо Дельту
837. 33:35і і в цьому випадку означає енергія
838. 33:38тобто наскільки сусід кращий за Поточний
839. 33:40стан якщо Дельта і позитивна це означає
840. 33:43що сусід кращий за Поточний стан якщо
841. 33:46Дельта і від'ємна це означає що сусід
842. 33:48гірший за Поточний стан Таким чином ми
843. 33:50можемо мати такий стан якщо Дельта і
844. 33:53більша за нуль то стан сусіда кращий за
845. 33:55Поточний стан
846. 33:57якщо коли-небудь виникне така ситуація
847. 34:00ми просто оновимо зміну каent до
848. 34:03значення цього сусіда так само як і
849. 34:05раніше перемістимось туди де ми зараз
850. 34:07перебуваємо щоби стати сусідом бо він
851. 34:09кращий за Поточний стан ми просто
852. 34:11Приймемо це але тепер відмінність у тому
853. 34:14що якщо раніше ми ніколи не хотіли
854. 34:16робити кроки які погіршують ситуацію то
855. 34:18тепер ми іноді хочемо рухатися так щоб
856. 34:20ситуація погіршилася бо іноді нам
857. 34:22потрібно зміститись від локального
858. 34:23мінімуму або локального максимуму щоби
859. 34:26збільшити мовір того що ми знайдемо
860. 34:28глобальний мінімум або глобальний
861. 34:29максимум пізніше Як же це зробити як ми
862. 34:32вирішуємо іноді приймати стан який може
863. 34:34бути гіршим ми Приймемо гірший стан із
864. 34:37певною ймовірністю ця ймовірність має
865. 34:39ґрунтуватися на кількох факторах
866. 34:41частково Вона має ґрунтуватися на
867. 34:43температурі якщо температура вища Ми з
868. 34:46більшою імовірністю перемістимося до
869. 34:48гіршого сусіда А якщо нижча то зменшує
870. 34:51імовірністю але це також до певної міри
871. 34:54має базуватися на дельті і Якщо сусід
872. 34:57набагато гірший за Поточний стан Ми з
873. 34:59меншою імовірністю захочемо вибрати його
874. 35:01ніж Якщо сусід лише трохи гірший за
875. 35:03Поточний стан знову ж таки є кілька
876. 35:06способів це вирахувати але Виявляється
877. 35:08що Один з найпопулярніших - Це просто
878. 35:11обчислити і в степені дельтаі поділене
879. 35:13на T і константа дельтаі поділене T - Це
880. 35:17ось ці дельтаі і T ми обчислюємо це
881. 35:21значення яке буде десь між нулем і
882. 35:23одиницею і це ймовірність з якою ми
883. 35:25скажемо перейдімо до цього сусіда
884. 35:28Виявляється що коли ви порахуєте це
885. 35:30значення Коли Дельта і така що сусідній
886. 35:32стан не набагато гірше за поточний тоді
887. 35:34імовірність того що ми перейдемо до
888. 35:36цього стану буде вищою і так само коли
889. 35:39температура нижча Ми з меншою
890. 35:40імовірністю перейдемо до цього стану
891. 35:42Отже це загальна картина імітації
892. 35:44відпалу процесу коли ми беремо завдання
893. 35:47і починаємо генерувати випадкових
894. 35:49сусідів ми завжди перемістимося до
895. 35:51сусіда якщо він кращий за Поточний стан
896. 35:54але навіть якщо сусід гірший за Поточний
897. 35:56стан ми і іноді будемо переходити туди
898. 35:58залежно від того наскільки він гірший а
899. 36:00також від температури у результаті мета
900. 36:03всього цього процесу полягає в тому що
901. 36:05коли ми починаємо Шукати шлях до
902. 36:07глобального максимуму або глобального
903. 36:09мінімуму ми можемо змістити себе якщо
904. 36:11застрягнемо в локальному максимумі або
905. 36:13локальному мінімумі щоби зрештою знайти
906. 36:16шлях до дослідження тієї частини
907. 36:17простору станів яка буде найкращою коли
908. 36:20температура знижується Ми застигаємо там
909. 36:23не надто видаляючись від того що ми
910. 36:25вважаємо найкращим з того що можемо
911. 36:27зробити на цей момент у кінці ми просто
912. 36:29повертаємо той стан в якому перебуваємо
913. 36:31на цей момент такий висновок цього
914. 36:33алгоритму ми змогли знайти
915. 36:36рішення ці типи алгоритмів мають багато
916. 36:38різних застосувань щоразу коли ви берете
917. 36:41проблему і формулюєте її як щось де ви
918. 36:43можете дослідити певну конфігурацію а
919. 36:46потім запитати чи якась із сусідніх
920. 36:48конфігурацій краще за поточну і мати
921. 36:50який спосіб виміряти це тоді є
922. 36:53відповідний випадок для цих алгоритмів
923. 36:55сходження на вершину чи імітації відпалу
924. 36:58іноді це може бути завдання з
925. 37:00розташуванням об'єктів наприклад ви
926. 37:02плануєте місто і хочете з'ясувати де
927. 37:04мають бути лікарні безумовно є й інші
928. 37:07застосування однією з найвідоміших задач
929. 37:09в інформатиці є задача комівояжера
930. 37:12задача комівояжера загалом формулюється
931. 37:14Так є купа міст позначених крапками Я
932. 37:17хочу знайти такий маршрут який пройде
933. 37:19через усі ці міста і поверне мене туди
934. 37:21звідки я почав тобто маршрут який
935. 37:23починається тут проходить через усі ці
936. 37:26міста І повертається туди звідки я почав
937. 37:28Я хочу мінімізувати загальну відстань
938. 37:30яку я маю подолати або ж загальну
939. 37:33вартість проходження шляху ви розумієте
940. 37:35що ця проблема актуальна для компанії
941. 37:37доставки яким треба доставити купу
942. 37:40вантажів у різні будинки вони хочуть
943. 37:42з'ясувати як дістатися зі складу до всіх
944. 37:45цих різних будинків і повернутися назад
945. 37:48використовуючи якомога менше часу
946. 37:51відстані та енергії тобто ви можете
947. 37:54розв'язати і подібні завдання
948. 37:56Виявляється що розв'язання такого роду
949. 37:58завдань дуже складне з обчислювальної
950. 38:00точки зору і дуже дороге воно підпадає
951. 38:03під категорію NP повних задач тобто
952. 38:06задач для Розв'язання яких не існує
953. 38:09жодного ефективного способу тобто
954. 38:12зрештою Ми повинні придумати якесь
955. 38:14наближення якісь способи спробувати
956. 38:16знайти хороше рішення Навіть якщо ми не
957. 38:19знайдемо глобального найкращого рішення
958. 38:21яке ми можемо знайти принаймні не за
959. 38:24можливий або реальний проміжок часу
960. 38:27тому візьмемо задачу комивояжера
961. 38:29спробуємо сформулювати її за допомогою
962. 38:32локального пошуку і будемо мислити
963. 38:34приблизно так я можу вибрати певний стан
964. 38:36певну конфігурацію певний маршрут між
965. 38:39усіма цими вузлами можу виміряти
966. 38:41вартість цього стану з'ясувати відстань
967. 38:44і можливо захочу мінімізувати цю
968. 38:46вартість і тоді єдине питання таке А
969. 38:49яким же буде сусід цьогого стану що
970. 38:51означає їхати цим маршрутом і мати
971. 38:53сусідній маршрут близький до нього але
972. 38:56трохи в відмінний так що загальна
973. 38:58відстань може бути іншою існує багато
974. 39:00різних визначень того що таке сусід ком
975. 39:02вояжера одне з них полягає в тому що
976. 39:04сусід - це те що станеться якщо ми
977. 39:07виберемо два ребра між вузлами і
978. 39:10поміняємо їх місцями наприклад я можу
979. 39:13вибрати ці два ребра одне яке йде сюди і
980. 39:16друге яке йде сюди і поміняти їх місцями
981. 39:19що це буде за процес загалом Спершу
982. 39:22потрібно виділити обидва ребра з графа
983. 39:25взяти цей вузол і з'єднати його з вузлом
984. 39:27з яким він не був з'єднаний тобто З оцим
985. 39:30угорі потім потрібно взяти ці стрілки
986. 39:33які спочатку йшли сюди і змінити їх
987. 39:36напрямок а потім заповнити останній
988. 39:38порожній перехід додавши стрілку яка йде
989. 39:41в цьому напрямку тобто взявши два ребра
990. 39:43і помінявши їх місцями я зміг розглянути
991. 39:46одного можливого сусіда цієї конкретної
992. 39:48конфігурації Схоже що сусід справді
993. 39:51кращий він долає меншу відстань ніж
994. 39:54Поточний стан щоби пройти через усі
995. 39:56міста та на маршруті ви можете уявити
996. 39:58собі реалізацію цієї ідеї в алгоритмі
997. 40:00сходження на вершину або імітації
998. 40:02відпалу де ми повторюємо цей процес щоби
999. 40:05взяти стан задачі комівояжера подивитися
1000. 40:08на всіх сусідів а потім перейти до них
1001. 40:10якщо вони кращі чи навіть якщо гірші
1002. 40:12поки ми не зупинимося на якомусь
1003. 40:15найкращому
1004. 40:16рішенні і Виявляється що ці типи
1005. 40:19алгоритмів наближення навіть якщо вони
1006. 40:20не завжди знаходять найкраще рішення
1007. 40:23часто можуть досить добре справлятися зі
1008. 40:25спробами має знайти рішення Отже це був
1009. 40:28погляд на локальний пошук особливо
1010. 40:30категорію алгоритмів які можна
1011. 40:32використовувати для розв'язку певного
1012. 40:34типу завдань де нас не дуже цікавить
1013. 40:37шлях мене не хвилювали кроки які я робив
1014. 40:40щоб вирішити де мають бути лікарні мене
1015. 40:42цікавило лише саме рішення Мене хвилює
1016. 40:45лише те де мають бути лікарні або який
1017. 40:47має бути маршрут мандрівного комівояжера
1018. 40:50інший тип алгоритмів - це так звані
1019. 40:52задачі лінійного програмування лінійне
1020. 40:55програмування часто з'являється в
1021. 40:57контексті коли ми намагаємося
1022. 40:58оптимізувати якусь математичну функцію
1023. 41:01Але часто лінійне програмування
1024. 41:03з'являється тоді коли ми маємо реальні
1025. 41:05числові значення Тобто це не просто
1026. 41:08дискретні фіксовані значення які ми
1027. 41:10можемо мати а будь-які десяткові
1028. 41:12значення які потрібно обчислити лінійне
1029. 41:15програмування - це сімейство типів задач
1030. 41:17де ми можемо мати наприклад таку
1031. 41:19ситуацію мета лінійного програмування
1032. 41:21мінімізація вартості функції Можна
1033. 41:24спробувати максимізувати її але часто це
1034. 41:26спроба саме мінімізувати вартісну
1035. 41:28функцію яка має певну кількість змінних
1036. 41:31x1х2х3 аж до xn просто певну кількість
1037. 41:35змінних значення яких я хочу знати
1038. 41:37вартісна функція може мати коефіцієнти
1039. 41:39перед змінними це те що ми називаємо
1040. 41:42лінійним рівнянням де є змінні які можна
1041. 41:45помножити на коефіцієнт а потім скласти
1042. 41:48ми не будемо нічого зводити В квадрат чи
1043. 41:50куб бо це дасть інші типи рівнянь у
1044. 41:53лінійному програмуванні ми маємо справу
1045. 41:55з лінійними рівняннями на додачу до
1046. 41:58лінійних обмежень що таке лінійне
1047. 42:00обмеження якщо ми розв'яжемо конкретне
1048. 42:02рівняння яке є лінійною комбінацією всіх
1049. 42:05цих змінних воно буде менше або
1050. 42:07дорівнюватиме деякій межі B ми можемо
1051. 42:10мати ряд різних обмежень які ми можемо
1052. 42:12накласти на нашу вправу з лінійного
1053. 42:15програмування так само як ми можемо мати
1054. 42:18обмеження які говорять що це лінійне
1055. 42:20рівняння менше або дорівнює деякій межі
1056. 42:23B воно також може дорівнювати чомусь
1057. 42:26Якщо ви хочете щоби сума певної
1058. 42:28комбінації змінних дорівнювала певному
1059. 42:30значенню ви можете це вказати Також ми
1060. 42:32можемо вказати що кожна змінна має нижню
1061. 42:34і верхню межу що вона має бути додатним
1062. 42:37числом або числом меншим за 50 є багато
1063. 42:40інших варіантів які ми можемо зробити
1064. 42:42для визначення меж змінної та
1065. 42:44виявляється що якщо ви можете взяти
1066. 42:46завдання і сформулювати його в цих
1067. 42:48термінах сформулювати завдання так що
1068. 42:50ваша мета мінімізувати вартісну функцію
1069. 42:53і ви мінімізуєте її з урахуванням певних
1070. 42:55обмежень з урахуванням рівнянь які мають
1071. 42:57Такий вигляд деякої послідовності
1072. 42:59змінних що менше за певну межу або
1073. 43:02дорівнює певному значенню то існує ряд
1074. 43:05алгоритмів які вже існують для вирішення
1075. 43:07такого роду
1076. 43:08завдань розгляньмо приклад ось приклад
1077. 43:12завдання яке може виникнути у світі
1078. 43:14лінійного програмування часто це
1079. 43:16відбувається коли ми намагаємося
1080. 43:18оптимізувати щось і хочемо мати
1081. 43:20можливість робити обчислення і у нас є
1082. 43:22обмеження на те що ми оптимізуємо ну
1083. 43:24наприклад ми на заводі у нас є дві
1084. 43:27машини X1 і X2 година роботи X1 коштує
1085. 43:3150 $ година роботи X2 80 долав мета те
1086. 43:35що ми намагаємося зробити мінімізувати
1087. 43:37загальні
1088. 43:39витрати як це робити але ми повинні
1089. 43:43робити це з урахуванням певних обмежень
1090. 43:45може існувати обмеження по робочій силі
1091. 43:48X1 потребує п'ять одиниць робочої сили
1092. 43:50на годину X2 дві одиниці робочої сили на
1093. 43:52годину загалом 20 одиниць робочої сили
1094. 43:55які ми повинні витратити ми можемо
1095. 43:57витратити не більше ніж 20 одиниць
1096. 44:00робочої сили і ми маємо їх витратити на
1097. 44:02X1 і X2 кожн з яких потребує різної
1098. 44:05кількості праці Також ми можемо мати
1099. 44:07таке обмеження 1 вироблятиме 10 одиниць
1100. 44:10продукції за годину X2 12 одиниць
1101. 44:14продукції за годину а компанії потрібно
1102. 44:1690 одиниць продукції Отже у нас є мета
1103. 44:20те чого потрібно досягти 90 одиниць
1104. 44:22продукції але є обмеження X1 виробляє
1105. 44:25лише 10 одиниць продукції за годину X2
1106. 44:2812 одиниць продукції за годину подібні
1107. 44:30завдання виникають досить часто ви
1108. 44:32почнете помічати закономірності в таких
1109. 44:34завданнях де я намагаюся виконати
1110. 44:36оптимізацію для досягнення мети
1111. 44:39мінімізувати витрати максимізувати
1112. 44:40випуск продукції чи прибуток тощо і є
1113. 44:43обмеження які накладаються на цей процес
1114. 44:46тепер потрібно сформулювати це завдання
1115. 44:48в лінійних рівняннях почнемо з першого
1116. 44:50пункту дві машини X1 і X2 X1 коштує 50
1117. 44:55до$ за годину
1118. 44:56x280 можемо придумати цільову функцію
1119. 44:59точніше вартісну функцію
1120. 45:0250* X1 + 80 * X2 де X1 буде зміною що
1121. 45:08представляє кількість годин роботи
1122. 45:10машини X1 а X2 буде зміна що представляє
1123. 45:13кількість годин роботи машини X2 що ми
1124. 45:16мінімізуємо вартісну функцію яка показує
1125. 45:19скільки коштує експлуатація обох машин
1126. 45:22за годину це приклад лінійного рівняння
1127. 45:24комбінація змінних плюс коефіцієнти які
1128. 45:27стоять перед ними я хочу мінімізувати це
1129. 45:30загальне значення Але я повинен зробити
1130. 45:33це з урахуванням цих обмежень для Х1
1131. 45:36потрібно п'ять одиниць робочої сили за
1132. 45:38годину X2 -дві А загалом потрібно
1133. 45:41витратити 20 одиниць робочої сили це дає
1134. 45:44нам таке обмеження 5х1 + 2х2 менше або
1135. 45:48дорівнює 20 20 - це загальна кількість
1136. 45:51одиниць робочої сили яку ми маємо
1137. 45:53витратити вона витрачається на X1 і X2
1138. 45:57для кожної з яких потрібна різна
1139. 45:59кількість одиниць робочої сили за годину
1140. 46:01і ще є таке обмеження X1 виробляє 10
1141. 46:04одиниць продукції за годину X2 12 А нам
1142. 46:07потрібно 90 одиниць продукції який же це
1143. 46:10має вигляд 10х1 + 12х2 - це кількість
1144. 46:15продукції за годину вона має бути
1145. 46:17щонайменше 90 більше чудово але не менше
1146. 46:20ніж 90 пам'ятаєте що я сказав раніше що
1147. 46:23Загалом у лінійному програмуванні ми
1148. 46:25маємо справу з обмеженнями дорівнює або
1149. 46:28менше чи дорівнює а тут у нас більше або
1150. 46:30дорівнює це не проблема Коли ми маємо
1151. 46:33такий знак множимо рівняння на -1 і це
1152. 46:36перетворить його на менше або дорівнює
1153. 46:39-90 замість більше або дорівнює 90 це
1154. 46:43буде еквівалентний вираз який можна
1155. 46:45використовувати для представлення
1156. 46:46завдання тепер коли у нас є вартісна
1157. 46:49функція та обмеження які на неї
1158. 46:52накладено Виявляється що існує ряд
1159. 46:54алгоритмів які можна використовувати для
1160. 46:56вирішення подібних завдань вони більше
1161. 46:58стосуються геометрії та лінійної алгебри
1162. 47:01в які ми не будемо заглиблюватися але
1163. 47:04найпопулярнішим з цих типів алгоритмів є
1164. 47:07симплексметод один з перших алгоритмів
1165. 47:09винайдених для вирішення лінійних задач
1166. 47:12а згодом для цього почали
1167. 47:13використовувати методи внутрішньої точки
1168. 47:15Важливо не стільки зрозуміти як саме
1169. 47:18працюють ці алгоритми а більше
1170. 47:20усвідомити що вони існують для
1171. 47:22ефективного знаходження рішень щоразу
1172. 47:24коли ми маємо завдання та форми Отже ми
1173. 47:27зараз можемо поглянути на каталог
1174. 47:34Production де у нас є файл під назвою
1175. 47:37production.pie де я використовую ppy це
1176. 47:41бібліотека для багатьох функцій
1177. 47:42пов'язаних з наукою у пайтоні зараз я
1178. 47:45запущу функцію оптимізації щоби
1179. 47:47запустити лінійну програму крапка linpr
1180. 47:50пробує вирішити цю лінійну програму коли
1181. 47:52Я надам цьому виразу цьому виклику
1182. 47:54функції всі дані про мою лінійну
1183. 47:56програму Вони мають бути у певному
1184. 47:59форматі що спочатку може вас трохи
1185. 48:01плутати першим аргументом для
1186. 48:05spy.optimize.linproc є вартісна функція
1187. 48:08Яка в цьому випадку представлена масивом
1188. 48:10або списком що містить 50 і 80 бо
1189. 48:13спочатку вартість функції була
1190. 48:1650х1 + 80х2 тому на пайthні Я просто
1191. 48:20кажу 50 і 80 - це коефіцієнти які я
1192. 48:23намагаюся оптимізувати а потім я вказую
1193. 48:25всі обмеження обмеження я записав вище в
1194. 48:28коментарях перше обмеження 5х1 + 2х2
1195. 48:33менше або дорівнює 20 друге обмеження
1196. 48:36-10х1 +
1197. 48:38-12х2 менше або дорівнює
1198. 48:41-90 cpй очікує що ці обмеження будуть у
1199. 48:46певному форматі спочатку очікує Що Я
1200. 48:48надам всі коефіцієнти для рівнянь
1201. 48:51верхньої межі
1202. 48:53означає верхня межа де коефіцієнти
1203. 48:55першого рівняння дорівнюють 5 і 2 тому
1204. 48:58що ми маємо 5х1 і 2х2 а коефіцієнти
1205. 49:02другого рівняння -10 і
1206. 49:05-12 бо ми маємо -10х1 +
1207. 49:08-12х2 тут ми наводимо його як окремий
1208. 49:11аргумент щоби розділити яка верхня межа
1209. 49:14для кожного з цих обмежень для першого
1210. 49:16обмеження верхня межа дорівнює 20 а для
1211. 49:19другого обмеження верхня межа становить
1212. 49:2290 загадковий спосіб представити їх це
1213. 49:26не так просто як написати математичні
1214. 49:28рівняння насправді ми очікуємо отримати
1215. 49:31всі коефіцієнти і всі числа які є в цих
1216. 49:34рівняннях спочатку надавши коефіцієнти
1217. 49:36для вартісної функції потім надавши всі
1218. 49:38коефіцієнти для обмежень нерівностей а
1219. 49:41потім надавши всі верхні межі для
1220. 49:43обмежень
1221. 49:44нерівностей і коли вся ця інформація є
1222. 49:48ми можемо запустити будь-який метод
1223. 49:50внутрішньої точки або симплексметод
1224. 49:53навіть якщо ви не розумієте як вони прац
1225. 49:55цюють просто запустіть функцію і
1226. 49:57З'ясуйте яким має бути результат якщо
1227. 50:00результат успішний ми розв'язали задачу
1228. 50:03виводимо на екран значення X1 і X2
1229. 50:06інакше виводимо на екран відсутній
1230. 50:08розв'язок Отже я запускаю програму
1231. 50:11запустивши python
1232. 50:14production.p обчислення триває секунду
1233. 50:17але потім ми бачимо яким має бути
1234. 50:19оптимальне рішення X1 має працювати
1235. 50:21івтори години X2
1236. 50:246,25 години
1237. 50:25Ми зробили це просто сформулювали
1238. 50:28завдання у вигляді лінійного рівняння
1239. 50:30яке ми намагалися оптимізувати вартості
1240. 50:33яку ми намагалися мінімізувати і
1241. 50:35обмежень багато-багато завдань
1242. 50:37підпадають під цю категорію їх можна
1243. 50:40розв'язати якщо ви можете просто
1244. 50:42зрозуміти як використовувати рівняння і
1245. 50:44обмеження щоби представити загальну ідею
1246. 50:48ця тема сьогодні ще кілька разів
1247. 50:50з'явиться коли ми захочемо взяти
1248. 50:52завдання і звести його до такого
1249. 50:53завдання яке нам під силу розв'язати
1250. 50:56використовуючи методи щоб знайти рішення
1251. 50:59більш ефективно або більш
1252. 51:02результативно Виявляється що такі типи
1253. 51:05завдань де ми маємо обмеження
1254. 51:07проявляються й іншими способами існує
1255. 51:10клас завдань більш широко відомі як
1256. 51:12завдання задоволення обмежень Зараз ми
1257. 51:15розглянемо Як сформулювати завдання
1258. 51:17задоволення обмежень і як його
1259. 51:20розв'язати основна ідея завдань
1260. 51:22задоволення обмежень полягає в тому що у
1261. 51:24нас є певна кіль змінних які мають
1262. 51:27набути певних значень А нам потрібно
1263. 51:29з'ясувати яких значень має бути кожна ця
1264. 51:31змінна але на цій змінні накладені певні
1265. 51:35обмеження які обмежують те яких значень
1266. 51:37ці зміні можуть набувати розгляньмо
1267. 51:40приклад з реального світу розклад
1268. 51:42іспитів У мене є чотири студенти 1 2 3 4
1269. 51:46Кожен з них відвідує певну кількість
1270. 51:49різних предметів предмети позначимо
1271. 51:51буквами студент о відвідує предмети AB і
1272. 51:54C студент2 предмети bdі і так
1273. 51:58далі університет призначає іспити з усіх
1274. 52:03цих предметів але має для цього лише три
1275. 52:05дні понеділок вівторок і середу ми
1276. 52:09повинні запланувати іспит Із кожного
1277. 52:11предмета але обмеження з якими ми
1278. 52:14стикаємося під час складання розкладу
1279. 52:16полягає в тому що ніхто не повинен
1280. 52:18складати два іспити в один день ми
1281. 52:21спробуємо звести це до мінімуму або
1282. 52:23взагалі усунути якщо це мож
1283. 52:25Як же нам почати представляти цю ідею як
1284. 52:28структурувати її так щоб комп'ютер з
1285. 52:30алгоритмом штучного інтелекту почав
1286. 52:32намагатися розв'язати завдання для
1287. 52:34початку подивимося на предмети і
1288. 52:37представимо Кожен з них як вузол
1289. 52:40графа а потім створимо ребро між двома
1290. 52:43вузлами графа Якщо між ними є
1291. 52:48обмеження що це означає почнемо зі
1292. 52:51студента О який вивчає предмети A B і C
1293. 52:55це означає що іспити з a і b не можуть
1294. 52:58бути в один день іспити з A і C не
1295. 53:00можуть бути в один день і іспити з B і C
1296. 53:03також не можуть бути в один день я можу
1297. 53:05відобразити це на графі додавши такі
1298. 53:07ребра одне між A і b одне між B і C одне
1299. 53:11між c і
1300. 53:12a це закодовано ідеєю про те що між цими
1301. 53:15вузлами є обмеження зокрема таке що вони
1302. 53:18не можуть дорівнювати одне одному є й
1303. 53:20інші типи обмежень Це залежить від типу
1304. 53:24завдання
1305. 53:26а потім ми можемо зробити те саме для
1306. 53:29кожного студента другий студент вивчає
1307. 53:31предмети BD це означає що між B D і
1308. 53:34мають бути ребра третій студент вивчає
1309. 53:36предмети cі і F тож візьмемо cі і F і
1310. 53:40з'єднаємо їх додавши ребра між
1311. 53:43ними Ну і четвертий вивчає предмети і F
1312. 53:46і G і ми можемо зобразити це додавши
1313. 53:49ребра між і F і G Хоча і і F уже мають
1314. 53:53ребро ще одне не потрібне бо це
1315. 53:56обмеження за кодовою ідею що іспити з
1316. 53:58предметів і та F не можуть відбуватися в
1317. 54:01один день Отже Ми отримали граф обмежень
1318. 54:05це певне графічне представлення всіх
1319. 54:07моїх змінних і обмежень між цими
1320. 54:09можливими змінними де в цьому
1321. 54:11конкретному випадку кожне обмеження є
1322. 54:14обмеженням нерівності тобто ребро між B
1323. 54:17і D означає що будь-яке значення якого
1324. 54:21набуває змінна бі не може бути тим самим
1325. 54:23значенням якого набуває змінна дій так
1326. 54:26що ж таке власне завдання задоволення
1327. 54:28обмежень це деяка множина змінних від X1
1328. 54:32до xn множина областей визначення для
1329. 54:35кожної з цих змінних кожна змінна має
1330. 54:39набувати певних значень можливо кожна
1331. 54:41змінна має одну і ту саму область
1332. 54:42визначення а можливо кожна змінна має
1333. 54:44дещо іншу область і ще є множина
1334. 54:47обмежень множина с містить обмеження
1335. 54:50накладені на ці змінні наприклад 1 не
1336. 54:52дорівнює X2 але можуть бути інші
1337. 54:55варіанти наприклад X1 = X2 + 1 Якщо ці
1338. 54:58змінні набувають числових значень у
1339. 55:00своїй області типи обмежень
1340. 55:02різнитимуться в залежності від
1341. 55:05завдання задоволення обмежень
1342. 55:08проявляється в будь-якій ситуації де є
1343. 55:11змінні на які накладено
1344. 55:13обмеження розглянемо це на прикладі
1345. 55:16популярної гри судоку це ігрове поле 9х9
1346. 55:20де потрібно заповнити числами кожну
1347. 55:22клітинку так щоби в жодному рядку чи
1348. 55:24стовпчику чи в полі 3 на3 не було
1349. 55:26повторюваного
1350. 55:28числа отже чому ж це завдання
1351. 55:31задоволення обмежень тут змінні - це всі
1352. 55:35порожні клітинки в судоку вони
1353. 55:37представлені тут так само як координати
1354. 55:40XY це клітинки в які потрібно вставити
1355. 55:43значення Але я не знаю якого саме
1356. 55:45значення Вони мають набути областю
1357. 55:47визначення будуть усі числа від одного
1358. 55:50до девяти будь-яке значення яке я можу
1359. 55:52вписати в клітинку це область для кожної
1360. 55:55і цих змінних а обмеження тоді матимуть
1361. 55:57таку форму ця клітинка не може
1362. 56:00дорівнювати цій клітинці не може
1363. 56:02дорівнювати цій клітинці і так далі і
1364. 56:05всі вони мають бути різними і однаковими
1365. 56:08для всіх рядків стовпчиків і квадратів
1366. 56:103х3ри Таким чином обмеження
1367. 56:12визначатимуть які значення насправді
1368. 56:14дозволені ми можемо сформулювати ту саму
1369. 56:16ідею у завданні про розклад іспитів
1370. 56:19змінними будуть предмети від a до G
1371. 56:21область визначення для кожної з цих
1372. 56:23змінних будуть по понеділок вівторок і
1373. 56:25середа це можливі значення яких може
1374. 56:28набувати кожна змінна що в цьому випадку
1375. 56:30Просто показує коли відбувається іспит з
1376. 56:33цього предмета обмеження матимуть Такий
1377. 56:36вигляд a не дорівнює b a не дорівнює C
1378. 56:38тобто іспити з a і b не можуть бути в
1379. 56:40один день іспити з A і C не можуть бути
1380. 56:42в один день або більш формально Ці дві
1381. 56:45змінні не можуть набувати однакових
1382. 56:46значень у межах своєї області
1383. 56:50визначення Отже це формулювання завдання
1384. 56:53задоволення обмеж
1385. 56:55ми можемо його використовувати щоб
1386. 56:57вирішити це завдання обмеження можуть
1387. 56:59мати різні форми існують жорсткі
1388. 57:02обмеження які повинні бути виконані для
1389. 57:05отримання правильного рішення наприклад
1390. 57:07як у судоку ви не можете допустити щоб
1391. 57:10ця клітинка і ця клітинка які
1392. 57:12розташовані поруч набували однакового
1393. 57:15значення це жорстке обмеження але
1394. 57:17завдання можуть мати і м'які обмеження
1395. 57:20вони виражають певне поняття переваги
1396. 57:22наприклад іспити з a і b не можуть бути
1397. 57:24в один день Але хтось вважає за краще
1398. 57:26щоб іспит a відбувся раніше ніж іспит B
1399. 57:29не обов'язково Саме так але має бути
1400. 57:31певне вираження того що певне рішення
1401. 57:34краще за інше рішення і в такому випадку
1402. 57:36ви можете сформулювати завдання як
1403. 57:38спробу оптимізації для максимізації
1404. 57:41вподобань людей ви хочете щоби
1405. 57:43вподобання людей були задоволені
1406. 57:45максимально однак у цьому випадку ми
1407. 57:47здебільшого матимемо справу з жорсткими
1408. 57:50обмеженнями які мають бути виконані щоб
1409. 57:52отримати правильне рішення ми хочемо з
1410. 57:54з'ясувати які значення будуть присвоєні
1411. 57:56цим змінним щоб зрештою дозволити нам
1412. 57:59вирішити завдання дозволивши призначити
1413. 58:01певний день кожному предмету так щоби не
1414. 58:04виникало конфліктів Виявляється що ми
1415. 58:06можемо класифікувати обмеження в
1416. 58:08завданні задоволення обмежень на кілька
1417. 58:11різних категорій перша з цих категорій
1418. 58:13мабуть найпростіші типи обмежень відомі
1419. 58:16як унарні обмеження це обмеження яке
1420. 58:19містить лише одну змінну наприклад
1421. 58:21унарним обмеженням може бути Щось на
1422. 58:23кшталт е не дорівнює понеділок Що
1423. 58:26означає що іспит з предмета a неможливий
1424. 58:28у понеділок якщо з якихось причин
1425. 58:31викладача в понеділок не буде У завданні
1426. 58:33може бути отаке обмеження воно містить
1427. 58:35лише одну змінну a і може означати що a
1428. 58:38не дорівнює понеділку або a дорівнюю
1429. 58:41чомусь або у випадку з числами більше
1430. 58:43або менше чогось обмеження яке має лише
1431. 58:46одну змінну вважаємо унарним обмеженням
1432. 58:49є ще бінарне обмеження тобто обмеження
1433. 58:51які містить дві змінні це буде обмеження
1434. 58:55накшталт тих які ми розглядали раніше
1435. 58:58Щось на кшталт a не дорівнює b є
1436. 59:00прикладом бінарного обмеження тому що це
1437. 59:02обмеження в якому беруть участь дві
1438. 59:04змінні a і b і Ми представили це за
1439. 59:07допомогою дуги або ребра яке з'єднує
1440. 59:09змінну a зі змінною
1441. 59:12B використовуючи знання про унарне
1442. 59:15обмеження і бінарне обмеження ми можемо
1443. 59:17багато чого сказати про завдання
1444. 59:19задоволення
1445. 59:20обмежень Наприклад ми можемо спробувати
1446. 59:23зробити вузол суміс
1447. 59:25що означає сумісність
1448. 59:27вузла що всі значення в області
1449. 59:30визначення змінної задовольняють унарні
1450. 59:32обмеження цієї змінної для кожної
1451. 59:35змінної в завданні якщо всі її значення
1452. 59:38задовольняють унарні обмеження для цією
1453. 59:40змінною ми можемо сказати що все
1454. 59:43завдання має вузлову сумісність або ми
1455. 59:45навіть можемо сказати що певна змінна
1456. 59:48має вузлову сумісність якщо ми просто
1457. 59:50хочемо зробити один вузол сумісним
1458. 59:53усередині неї
1459. 59:56як це показати графічно розглянемо
1460. 59:58спрощений приклад де замість купи різних
1461. 1:00:01предметів ми візьмемо лише два предмети
1462. 1:00:03a та b іспит кожного з яких проходить у
1463. 1:00:06понеділок вівторок або середу Отже це
1464. 1:00:09область визначення змінної a а це
1465. 1:00:11область змінної B і уявімо що в нас є
1466. 1:00:14такі обмеження a не дорівнює понеділку b
1467. 1:00:17не дорівнює вівторку b не дорівнює
1468. 1:00:19понеділку a не дорівнює b Отакі
1469. 1:00:21обмеження для цього конкретного завдання
1470. 1:00:23тепер ми можемо спробувати забезпечити
1471. 1:00:25вузлову сумісність це означає що ми
1472. 1:00:28переконуємося що всі значення в області
1473. 1:00:31будь-якої змінною задовольняють її
1474. 1:00:33унарні
1475. 1:00:35обмеження починаємо зі спроби зробити
1476. 1:00:38вузол A сумісним чи він
1477. 1:00:41сумісний чи кожне значення в області a
1478. 1:00:44задовольняє його унарні обмеження
1479. 1:00:47Спочатку ми побачимо що понеділок не
1480. 1:00:49задовольняє унарні обмеження вузла a
1481. 1:00:52тому що ми маємо унарне обмеження що A
1482. 1:00:54дорівнює понеділку однак понеділок є в
1483. 1:00:57області a Отже це вузлова не сумісність
1484. 1:01:00тому що в області визначення є понеділок
1485. 1:01:03але це недопустиме значення для цього
1486. 1:01:06вузла як же зробити цей вузол сумісним
1487. 1:01:09для цього потрібно вилучити понеділок з
1488. 1:01:11області a тепер a може бути тільки у
1489. 1:01:14вівторок або середу тому що обмеження
1490. 1:01:17показувало що a не дорівнює
1491. 1:01:19понеділку На цьому етапі a тепер
1492. 1:01:22сумісний вузол для кожного значення
1493. 1:01:25якого може набувати Ей вівторок і середа
1494. 1:01:28не існує унарного обмеження Яке би
1495. 1:01:31суперечило цій ідеї не існує обмежень
1496. 1:01:33які б говорили що a не може бути у
1497. 1:01:35вівторок або що a не може бути в середу
1498. 1:01:38тепер ми можемо звернути увагу на Бій
1499. 1:01:40Бій також має область понеділок вівторок
1500. 1:01:42і середа і ми можемо почати перевіряти
1501. 1:01:45чи задовольняють ці зміні унарні
1502. 1:01:46обмеження ось унарна обмеження B не
1503. 1:01:49дорівнює
1504. 1:01:50вівторку воно не задовольняється цією
1505. 1:01:53областю ви значення понеділок вівторок і
1506. 1:01:55середа тому що вівторок - це можливе
1507. 1:01:58значення якого може набувати змінна бі
1508. 1:02:00не сумісне з унарним обмеженням що B не
1509. 1:02:04дорівнює вівторку щоб розв'язати цю
1510. 1:02:06проблему ми видалимо вівторок з області
1511. 1:02:09B тепер область B містить лише понеділок
1512. 1:02:11і середу але як виявляється є ще одне
1513. 1:02:14унарне обмеження яке ми наклали на
1514. 1:02:16змінну b b не дорівнює понеділку це
1515. 1:02:19означає що це значення понеділок в
1516. 1:02:21області B не сумісне з унарними
1517. 1:02:23обмеження б бо є обмеження яке говорить
1518. 1:02:26що бі не може бути понеділком а отже
1519. 1:02:29видаляємо понеділок з області бі ми
1520. 1:02:31переглянули всі унарні обмеження Ми ще
1521. 1:02:34не розглядали це бінарне обмеження але
1522. 1:02:36ми розглянули всі унарні обмеження тобто
1523. 1:02:39обмеження які містять лише одну змінну і
1524. 1:02:42ми переконалися що кожен вузол
1525. 1:02:44відповідає цим унарним обмеженням тепер
1526. 1:02:46ми можемо сказати що ми забезпечили
1527. 1:02:48вузлову сумісність що для кожного з цих
1528. 1:02:51можливих вузлів ми можемо вибрати
1529. 1:02:53будь-яке з значення в області і не буде
1530. 1:02:56порушено жодного унарного
1531. 1:03:00обмеження Таким чином вузлову сумісність
1532. 1:03:02досить легко забезпечити Ми беремо кожен
1533. 1:03:05вузол І переконуємося що значення в
1534. 1:03:07області задовольняють унарні обмеження
1535. 1:03:11трохи цікавіше стає коли ми розглядаємо
1536. 1:03:13різні типи сумісності наприклад дугову
1537. 1:03:16сумісність дугова сумісність означає що
1538. 1:03:19всі значення в області змінної
1539. 1:03:20задовольняють бінарні обмеження змінної
1540. 1:03:23тобто коли ми намагаємося привести a до
1541. 1:03:25дугової сумісності ми вже не просто
1542. 1:03:28розглядаємо унарні обмеження які
1543. 1:03:30стосуються a Ми намагаємося врахувати
1544. 1:03:33всі бінарні обмеження які стосуються a
1545. 1:03:36тобто будь-яке ребро яке з'єднує a з
1546. 1:03:39іншою змінною всередині графа обмежень
1547. 1:03:41який ми розглядали раніше Якщо говорити
1548. 1:03:44більш формально то дуга - Це просто інше
1549. 1:03:47слово для позначення ребра яке з'єднує
1550. 1:03:50два вузли всередині графа обмежень ми
1551. 1:03:52можемо визначити дугову сумі місність
1552. 1:03:54трохи точніше для того щоб зробити
1553. 1:03:57змінну
1554. 1:03:58дугосумісною по відношенню до змінної y
1555. 1:04:01нам потрібно Видалити будь-який елемент
1556. 1:04:03з області визначення
1557. 1:04:05щоб переконатися що кожен вибір в
1558. 1:04:08області
1559. 1:04:09має можливий вибір для
1560. 1:04:12y інакше кажучи якщо у мене є зміна
1561. 1:04:15яку я хочу зробити дугосумісною то мені
1562. 1:04:18потрібно переглянути всі можливі
1563. 1:04:19значення яких може набувати х і
1564. 1:04:22переконатися що для всіх цих можливих
1565. 1:04:24значень є вибір який я можу зробити для
1566. 1:04:26y Якщо між X І Y є дуга щоби
1567. 1:04:29переконатися що y також має варіант які
1568. 1:04:32я можу
1569. 1:04:33вибрати розглянемо приклад повертаючись
1570. 1:04:36до попереднього прикладу ми вже
1571. 1:04:38забезпечили вузлову сумісність сказавши
1572. 1:04:40що a може бути тільки у вівторок або
1573. 1:04:42середу і не може бути в понеділок і ми
1574. 1:04:45сказали що область визначення B
1575. 1:04:47складається лише з середи бо ми знаємо
1576. 1:04:49що B не дорівнює Ні вівторку ні
1577. 1:04:52понеділку тепер тепер розглянемо дугову
1578. 1:04:55сумісність спробуємо зробити a
1579. 1:04:57дугосумісною із B що означає зробити a
1580. 1:05:02дугосумісним із B що для будь-якого
1581. 1:05:05вибору який ми робимо в області
1582. 1:05:06визначення a існує деякий вибір який ми
1583. 1:05:09можемо зробити в області B який буде
1584. 1:05:12сумісним спробуємо для a ми можемо
1585. 1:05:15вибрати вівторок як можливе значення
1586. 1:05:17якщо я виберу вівторок для A чи існує
1587. 1:05:19значення для B яке задовольняє бінарне
1588. 1:05:21обмеження так у B середа льнить це
1589. 1:05:24обмеження що a не дорівнює b тому що
1590. 1:05:27вівторок не дорівнює середі однак якщо
1591. 1:05:30ми вибрали середу для a тоді в області B
1592. 1:05:34немає вибору який би задовольняв це
1593. 1:05:36бінарне обмеження я ніяк не можу вибрати
1594. 1:05:39для B щось що задовольняє обмеження a не
1595. 1:05:42дорівнює b бо я знаю що B - це середа
1596. 1:05:46якщо я коли-небудь потраплю в таку
1597. 1:05:47ситуацію де побачу що є можливе значення
1598. 1:05:50для a якого немає в області B і яке не
1599. 1:05:53задовольняє обмеження тоді це не дугова
1600. 1:05:56сумісність А щоб зробити його
1601. 1:05:59дугосумісним Мені потрібно взяти середу
1602. 1:06:01і вилучити її з області a середа не може
1603. 1:06:04бути можливим вибором для a бо вона не
1604. 1:06:07сумісна з цим бінарним обмеженням для B
1605. 1:06:10не було жодного способу щоб я міг
1606. 1:06:12вибрати середу для a і при цьому мати
1607. 1:06:14доступне рішення вибравши щось і для B
1608. 1:06:18Тепер я зміг забезпечити дугову
1609. 1:06:20сумісність і таким чином розв'язав
1610. 1:06:22завдання маючи обмеження що іспити з a і
1611. 1:06:26b не можуть бути або в понеділок або у
1612. 1:06:28вівторок або в середу єдине рішення
1613. 1:06:30полягає в тому що іспит a має бути у
1614. 1:06:32вівторок а іспит бі у
1615. 1:06:34середу і це єдиний доступний
1616. 1:06:38варіант якщо ми хочемо застосувати
1617. 1:06:40послідовність до більшого графа а не
1618. 1:06:43просто розглядати одну конкретну пару є
1619. 1:06:45способи зробити і це ми можемо створити
1620. 1:06:48псевдокод для написання алгоритму який
1621. 1:06:50забезпечує дугову сумісність і ми
1622. 1:06:52почнемо з визна функції під назвоюise за
1623. 1:06:56вхідні даніise бере csp інакше відомо як
1624. 1:07:00завдання задоволення обмежень а також
1625. 1:07:02дві змінні X І Y вай зробить
1626. 1:07:06дугосумісною по відношенню до y тобто
1627. 1:07:08виділить з області визначення усе що не
1628. 1:07:11допускає можливого варіанта для
1629. 1:07:16y Як це працює спочатку відстежимо чи
1630. 1:07:20виконали ми ваice чи ні команда зрештою
1631. 1:07:23поверне True або False True у випадку
1632. 1:07:26якщо ми дійсно внесли зміни в областьі X
1633. 1:07:28і поверне False якщо ми не внесли жодних
1634. 1:07:31змін в область X за мить побачимо чому
1635. 1:07:34це може бути корисно але почнемо з того
1636. 1:07:36що нехай reваise дорівнює fлse ми не
1637. 1:07:39внесли ніяких змін потім пройдемося по
1638. 1:07:42всіх можливих значень в області тобто
1639. 1:07:44пройдемося по області визначення
1640. 1:07:46для кожного маленького X в області
1641. 1:07:49Я хочу переконатися що для кожного з цих
1642. 1:07:51варіантів Я маю доступний варіант в Y
1643. 1:07:54який задовольняє бінарні обмеження
1644. 1:07:56визначені всередині csp всередині
1645. 1:07:58завдання задоволення обмежень Отже якщо
1646. 1:08:02станеться так що в області визначення y
1647. 1:08:04не буде значення y яке задовольняє
1648. 1:08:07обмеження для І Y тоді це означає що це
1649. 1:08:11значення не має бути в області
1650. 1:08:15Тобто ми виділимо із області X і
1651. 1:08:18встановимо rваise дорівнює True бо я
1652. 1:08:21змінив область видаливши маленький
1653. 1:08:24а видалив Я маленький х тому що він не
1654. 1:08:27був
1655. 1:08:28госумісним і я ніяк не міг вибрати
1656. 1:08:30значення для y яке б задовольняло це
1657. 1:08:33обмеження XY Отже у цьому випадку ми
1658. 1:08:36продовжимо і встановимо rвай дорівнює
1659. 1:08:38True будемо робити це знову і знову для
1660. 1:08:40кожного значення в області
1661. 1:08:42іноді це може спрацювати іноді це може
1662. 1:08:45не дозволити робити вибір для y і тоді
1663. 1:08:47потрібно буде Виділити це значення з
1664. 1:08:49області
1665. 1:08:50і в кінці ми просто повертаємо ревай щоб
1666. 1:08:52вказати чи дійсно ми внесли зміни Отже
1667. 1:08:55функція reваise є реалізацією того що ви
1668. 1:08:58бачили графічну хвилину тому вона робить
1669. 1:09:00одну змінну X дугосумісною з іншою
1670. 1:09:03змінною в цьому випадку y але загалом
1671. 1:09:07коли ми хочемо забезпечити
1672. 1:09:08дугосумісність потрібно забезпечити
1673. 1:09:11дугосумісність не тільки для однієї дуги
1674. 1:09:13але й для всього завдання задоволення
1675. 1:09:15обмежень і Виявляється що для цього
1676. 1:09:17також існує алгоритм відомий як AC3 AC3
1677. 1:09:21бере завдання задоволення обмежень і
1678. 1:09:23забезпе дугосумісність у всьому
1679. 1:09:26завданні як він це робить Він підтримує
1680. 1:09:29чергу всіх дуг які йому потрібно зробити
1681. 1:09:32сумісними з часом ми можемо видаляти
1682. 1:09:34елементи з цієї черги коли почнемо
1683. 1:09:37працювати з сумісністю дух можливо
1684. 1:09:40доведеться додавати щось до цієї черги
1685. 1:09:42якщо з'явиться більше вузлів які
1686. 1:09:44потрібно буде зробити дугосумісними Отже
1687. 1:09:46почнемо з черги яка містить всі дуги
1688. 1:09:49завдань і задоволення обмежень усі ребра
1689. 1:09:51які з'єднують вузли що мають між собою
1690. 1:09:53якесь бінарне
1691. 1:09:56обмеження покии черга не порожня є
1692. 1:09:59Робота яку потрібно виконати черга - це
1693. 1:10:02все те що нам потрібно зробити
1694. 1:10:05госумісним поки черга не порожня нам Є
1695. 1:10:08над чим працювати що ми маємо зробити
1696. 1:10:11почнемо з того що видалимо щось із черги
1697. 1:10:14і строго кажучи це не обов'язково має
1698. 1:10:16бути черга але черга - Це традиційний
1699. 1:10:18спосіб зробити це ми видалимо з черги і
1700. 1:10:21це дасть нам догу між двома змінними X І
1701. 1:10:24Y Я хотів би зробити так щоб була
1702. 1:10:27сумісна з Y Як це зробити Ми можемо
1703. 1:10:30скористатися функцією rваise про яку ми
1704. 1:10:32говорили хвилину тому викликаємо функцію
1705. 1:10:35revise у якої за вхідні дані буде
1706. 1:10:38завдання задоволення обмеження а також
1707. 1:10:40змінні і y бо я хочу зробити
1708. 1:10:43догосумісним з Y інакше кажучи видаілити
1709. 1:10:46всі значення з області X які не
1710. 1:10:49залишають доступного варіанта для y
1711. 1:10:51Пригадайте що повертає функція rріва
1712. 1:10:54Вона повертає True якщо ми дійсно внесли
1713. 1:10:56зміни якщо ми видалили щось з області бо
1714. 1:10:59не було доступного варіанта для y і
1715. 1:11:02повертає fлse якщо ми взагалі не вносили
1716. 1:11:04змін в область визначення
1717. 1:11:06і виходить що якщо вай повертає fлse
1718. 1:11:08якщо ми не внесли жодних змін тоді для
1719. 1:11:11цієї дуги немає чого більше робити Ми
1720. 1:11:13можемо перейти до наступної дуги у черзі
1721. 1:11:16Але якщо ми внесли зміни якщо зменшили
1722. 1:11:19область
1723. 1:11:19видаливши значення з неї тоді це створює
1724. 1:11:22потенційні проблеми Пізніше це може
1725. 1:11:25означати що деяка дога яка була сумісна
1726. 1:11:28з Х цей вузол може більше не бути
1727. 1:11:32дугосумісним з
1728. 1:11:34бо якщо раніше існував варіант який ми
1729. 1:11:36могли вибрати для х То тепер його може
1730. 1:11:38не бути бо ми видаілили щось із Х для
1731. 1:11:41того щоб якась інша дуга була
1732. 1:11:43дугосумісною якщо ми коли-небудь
1733. 1:11:46переглядали область х потрібно буде
1734. 1:11:48додати дещо до черги деякі додаткові
1735. 1:11:51дуги які ми захочемо перевірити як нам
1736. 1:11:54це зробити Спершу ми переконаємося що
1737. 1:11:56область X не дорівнює нулю якщо область
1738. 1:11:59x дорівнює 0лю це означає що для взагалі
1739. 1:12:01Немає доступних варіантів Тобто ви не
1740. 1:12:04можете вирішити завдання задоволення
1741. 1:12:06обмежень якщо ми видалили все з області
1742. 1:12:09визначення ми повернемо значення fлse
1743. 1:12:12яке означає що виконати завдання
1744. 1:12:14неможливо бо в області х нічого не
1745. 1:12:16лишилося проте якщо в області х лишилися
1746. 1:12:19змінні але їх стало менше тоді ми
1747. 1:12:21переберемо кожну змінну Z яка є у всіх
1748. 1:12:24сусідів X окрім
1749. 1:12:27y з Y ми вже розібралися але ми
1750. 1:12:30розглянемо всіх інших сусідів
1751. 1:12:32і запитаємо себе чи не буде більше
1752. 1:12:35дугосумісної дуга від кожної із цих Z до
1753. 1:12:38X бо якщо для кожного Z ми могли вибрати
1754. 1:12:41варіант який відповідав би кожному з
1755. 1:12:43можливих значень
1756. 1:12:44То тепер такого варіанта може не бути
1757. 1:12:46тому що ми видалили деякі елементи з
1758. 1:12:49області
1759. 1:12:50Тому далі ми продовжимо ставити в чергу
1760. 1:12:52додаючи щось до неї дугу ZX для всіх
1761. 1:12:56сусідніх Z Отже нам потрібно додати ще
1762. 1:12:59кілька дух до черги щоби продовжувати
1763. 1:13:02забезпечувати сумісність дух у самому
1764. 1:13:04кінці якщо ми пройдемо через весь процес
1765. 1:13:06ми зможемо повернути тру Але це вже AC3
1766. 1:13:09алгоритм для забезпечення сумісності дух
1767. 1:13:12в завданні задоволення обмежень основна
1768. 1:13:15ідея полягає в тому щоб просто
1769. 1:13:16відстежувати всі дуги які можуть
1770. 1:13:18знадобитися для забезпечення сумісності
1771. 1:13:20дух зробити дугу сумісною можна за
1772. 1:13:22допомогою функції А якщо ми її
1773. 1:13:25переглянули то можливо до черги потрібно
1774. 1:13:27буде додати нові дуги щоб переконатися
1775. 1:13:29що все лишається дугосумісним навіть
1776. 1:13:32після того як ми виділимо деякі елементи
1777. 1:13:34з області визначення певної
1778. 1:13:36змінної що ж станеться якщо ми спробуємо
1779. 1:13:40застосувати сумісність дух на такому
1780. 1:13:42графі де кожна змінна має область що
1781. 1:13:44складається з понеділка вівторка і
1782. 1:13:46середи Виявляється що застосування
1783. 1:13:48сумісності дух на цьому графі нічого не
1784. 1:13:51змінює Хоча і може вирішити деякі
1785. 1:13:53проблеми для будь-якої конкретної дуги
1786. 1:13:56Що розглядає дві зміні завжди є спосіб
1787. 1:13:59пристосуватися до будь-якого вибору який
1788. 1:14:01я роблю для однієї з них і зробити вибір
1789. 1:14:04для іншої тому що є три варіанти і Мені
1790. 1:14:06просто потрібно щоб ці два різнилися
1791. 1:14:09насправді легко взяти дугу І заявити що
1792. 1:14:11вона дугосумісна бо якщо я виберу
1793. 1:14:14понеділок для дії а потім виберу щось що
1794. 1:14:16не є понеділком для бі в сумісності дух
1795. 1:14:19ми розглядаємо сумісність тільки між
1796. 1:14:21бінарними обмеженнями між двома вузлами
1797. 1:14:24і ми ще не розглядаємо всі інші
1798. 1:14:27вузли використання AC3 забезпечення
1799. 1:14:30сумісності дух Іноді може мати ефект
1800. 1:14:32зменшення області визначення щоби
1801. 1:14:35полегшити пошук рішень але це не завжди
1802. 1:14:37вирішує
1803. 1:14:38проблему можливо Нам все одно доведеться
1804. 1:14:41шукати щоби знайти рішення для цього ми
1805. 1:14:44можемо використовувати класичні
1806. 1:14:46традиційні алгоритми пошуку ви
1807. 1:14:48пам'ятаєте що завдання пошуку зазвичай
1808. 1:14:51складається з таких частин є початковий
1809. 1:14:53стан дії модель переходу яка переводить
1810. 1:14:55мене з одного стану в інший перевірка
1811. 1:14:57цілі яка показує чи правильно я
1812. 1:14:59задовольнив ціль і функція вартості
1813. 1:15:01шляху тому що у випадку проходження
1814. 1:15:03лабіринту Я намагався дістатися до цілі
1815. 1:15:06якомога швидше Отже ви можете
1816. 1:15:09сформулювати csp або завдання
1817. 1:15:11задоволення обмежень як один з цих типів
1818. 1:15:14завдань пошуку початковим станом буде
1819. 1:15:16порожнє присвоєння де присвоєння це
1820. 1:15:18спосіб присвоїти будь-які змінні і
1821. 1:15:20будь-яке конкретне значення якщо це
1822. 1:15:23порожнє значення тобто жодні змінні ще
1823. 1:15:26не присвоєно жодного значення тоді
1824. 1:15:28єдиною дією яку я можу виконати буде
1825. 1:15:31додавання до нього пари змінна дорівнює
1826. 1:15:33значення тобто я додам нове значення для
1827. 1:15:36цієї змінної а модель переходу визначає
1828. 1:15:39що відбувається коли ви виконуєте цю дію
1829. 1:15:43ви отримуєте нове присвоєння в якому ця
1830. 1:15:45змінна дорівнює цьому значенню перевірка
1831. 1:15:48цілі - це перевірка того чи всі змінні
1832. 1:15:50були присвоєні і чи всі обмеження були
1833. 1:15:52виконані а функція вартості шляху не має
1834. 1:15:55значення Мене не цікавить шлях Мене
1835. 1:15:58цікавить лише те щоб знайти таке
1836. 1:15:59присвоєння яке задовольняє всі обмеження
1837. 1:16:02тому всі шляхи мають однакову вартість
1838. 1:16:05Мене не цікавить шлях до цілі Мене
1839. 1:16:07цікавить лише рішення про що ми вже
1840. 1:16:10говорили
1841. 1:16:12раніше проблема в тому що якщо ми просто
1842. 1:16:14реалізуємо цей наївний алгоритм пошуку
1843. 1:16:17реалізуючи пошук у ширину або пошук у
1844. 1:16:20глибину Це буде дуже неефективно існують
1845. 1:16:22способ би скористатися перевагами
1846. 1:16:24ефективності в структурі самого завдання
1847. 1:16:26задоволення обмежень і одна з ключових
1848. 1:16:28ідей полягає в тому що ми можемо просто
1849. 1:16:31впорядкувати ці змінні і немає значення
1850. 1:16:33в якому порядку Ми присвоюємо змінні A =
1851. 1:16:362 а потім B = 8 це буде те саме що і b
1852. 1:16:40рі 8 а потім a Дор 2 зміна порядку
1853. 1:16:43нічого не змінює у фундаментальній
1854. 1:16:46природі
1855. 1:16:47присвоювання є кілька способів якими ми
1856. 1:16:50можемо спробувати переглянути ідею
1857. 1:16:52алгоритму пошуку щоби застосувати її
1858. 1:16:55конкретно до завдання задоволення
1859. 1:16:56обмежень Виявляється що алгоритм пошуку
1860. 1:16:59який ми зазвичай використовуємо коли
1861. 1:17:01говоримо про завдання задоволення
1862. 1:17:03обмежень називається пошук З поверненням
1863. 1:17:06Його ідея полягає в тому що ми будемо
1864. 1:17:08йти вперед і робити присвоєння від
1865. 1:17:09змінних до значень А якщо ми коли-небудь
1866. 1:17:12застрягнемо дійдемо до місця де не
1867. 1:17:14зможемо йти вперед зберігаючи при цьому
1868. 1:17:16обмеження які нам потрібно виконати ми
1869. 1:17:19повернемося назад і спробуємо натомість
1870. 1:17:21щось інше
1871. 1:17:23ось найпростіший приклад пошуку у
1872. 1:17:25зворотному напрямку функція backтрек яка
1873. 1:17:28бере за вхідні дані присвоєння і
1874. 1:17:31завдання задоволення обмежень спочатку в
1875. 1:17:33нас немає жодних присвоєних змінних коли
1876. 1:17:35ми запустимо пошук З поверненням це
1877. 1:17:37присвоєння буде порожним без жодних
1878. 1:17:40змінних усередині але пізніше ми
1879. 1:17:42побачимо що це буде рекурсивна функція
1880. 1:17:45Отже функція backктraк приймає за вхідні
1881. 1:17:47дані присвоєння і завдання якщо
1882. 1:17:49присвоєння завершено Тобто всі зміні
1883. 1:17:52присвоєно ми повертаємо присвоєння
1884. 1:17:54звісно Спочатку це буде не так Оскільки
1885. 1:17:56ми починаємо з порожнього значення Але з
1886. 1:17:59часом ми можемо додати щось до нього і
1887. 1:18:01якщо коли-небудь присвоєння буде
1888. 1:18:03завершено тоді все ми його просто
1889. 1:18:05повернемо але Якщо ні тоді Є над чим
1890. 1:18:08працювати нам потрібно вибрати
1891. 1:18:10неприсвоєну зміну для цього конкретного
1892. 1:18:13завдання потрібно взяти завдання
1893. 1:18:15подивитися на змінні які вже було
1894. 1:18:17присвоєно і вибрати змінну яку ще не
1895. 1:18:20було
1896. 1:18:21присвоєно Я виберу таку змінну а потім
1897. 1:18:24Мені потрібно врахувати всі значення в
1898. 1:18:26області цієї змінної викличемо функцію
1899. 1:18:29domain values поговоримо про неї пізніше
1900. 1:18:32яка візьме змінну і поверне мені
1901. 1:18:33впорядкований список всіх значень її
1902. 1:18:36області визначення я взяв випадково
1903. 1:18:38невибрану змінну Я збираюся перебрати
1904. 1:18:41всі можливі значення ідея в тому що я
1905. 1:18:43просто спробую всі ці значення як
1906. 1:18:45можливі значення
1907. 1:18:47змінною і якщо значення поки що
1908. 1:18:50відповідає призначенню не порушує
1909. 1:18:52жодного обмеження тоді додамо змінна
1910. 1:18:55дорівнює значення бо воно поки що
1911. 1:18:57відповідає призначенню А тепер
1912. 1:18:59рекурсивно викличемо бектрек щоби
1913. 1:19:01зробити решту присвоєнь також
1914. 1:19:05сумісним отже викличемо бектрек з новим
1915. 1:19:08присвоєнням яке я щойно додав зміна
1916. 1:19:11дорівнює значення Тепер я рекурсивно
1917. 1:19:14викликаю бектрак і дивлюся на результат
1918. 1:19:16якщо результат не невдалий тоді я просто
1919. 1:19:19поверну
1920. 1:19:21результат А якщо ні то що ще може
1921. 1:19:25статися якщо виявиться що результат був
1922. 1:19:28невдалим тоді це означає що це значення
1923. 1:19:30було поганим вибором для цієї конкретної
1924. 1:19:32змінної Бо коли я присвоїв цій змінні це
1925. 1:19:35значення зрештою я опинився в ситуації
1926. 1:19:37коли порушив обмеження я більше нічого
1927. 1:19:40не міг зробити Тому зараз я вилучу
1928. 1:19:42змінна дорівнює значення з присвоєння
1929. 1:19:45повернуся назад це значення не
1930. 1:19:47спрацювало спробуємо замість нього
1931. 1:19:49інше і в самому кінці якщо ми так і не
1932. 1:19:52не змогли повернути повне присвоєння ми
1933. 1:19:54повернемо фейр бо це означає що жодне
1934. 1:19:57значення не спрацювало для цієї
1935. 1:19:59конкретної змінної у цьому і полягає
1936. 1:20:02ідея пошуку З поверненням взяти кожну
1937. 1:20:04зміну спробувати значення для них і
1938. 1:20:06спробувати пошук З поверненням щоб
1939. 1:20:08побачити чи зможемо ми досягти прогресу
1940. 1:20:11а якщо ми зайдемо в глухий кут у
1941. 1:20:13ситуації коли немає жодного можливого
1942. 1:20:15значення яке б задовольняло обмеження ми
1943. 1:20:17повернемо фейлер і зрештою Ми зробимо
1944. 1:20:20інший вибір повертаючись назад і
1945. 1:20:22пробуючи що щось
1946. 1:20:23інше застосуємо цей алгоритм на практиці
1947. 1:20:26спробуємо використати пошук З
1948. 1:20:28поверненням для вирішення цього завдання
1949. 1:20:30де потрібно з'ясувати який день іспиту
1950. 1:20:33призначити кожному предмету понеділок
1951. 1:20:35вівторок чи середу причому так щоб він
1952. 1:20:37задовольняв обмеження що Кожне з цих
1953. 1:20:40ребер означає що в один і той самий день
1954. 1:20:42не може проходити іспит з двох предметів
1955. 1:20:44я почну з вузла неважливо з якого Але в
1956. 1:20:47цьому випадку почну з a далі пройдуся по
1957. 1:20:50значеннях з області у цьому випадку
1958. 1:20:53почну з понеділка почнемо з понеділка і
1959. 1:20:55призначимо е підемо по порядку понеділок
1960. 1:20:57вівторок
1961. 1:20:59середа тепер розглянемо вузол B я зробив
1962. 1:21:03присвоєння для a рекурсивно викликав
1963. 1:21:05бектрек цією новою частиною присвоєння
1964. 1:21:07Тепер я виберу іншу неприсвоєну зміну
1965. 1:21:09наприклад B Де також почну з понеділка
1966. 1:21:12бо це найперше значення в області B
1967. 1:21:14тепер подумаю чи не порушує понеділок
1968. 1:21:16якісь обмеження Виявляється що порушує
1969. 1:21:19він порушує обмеження між A і b тому що
1970. 1:21:21a і b тепер в понеділок а це не спрацює
1971. 1:21:25тому що B не може бути в той самий день
1972. 1:21:27що і a Отже це не спрацює тому замість
1973. 1:21:30цього спробуємо вівторок наступне
1974. 1:21:32значення в області B чи відповідає це
1975. 1:21:34поставленому завданню так b- вівторок a-
1976. 1:21:37понеділок поки що відповідаю тому що
1977. 1:21:39вони не в один день Це добре Тепер ми
1978. 1:21:41можемо рекурсивно викликати бектрек і
1979. 1:21:43спробуємо ще раз виберемо іншу не
1980. 1:21:45присвоїмо зміну наприклад дії пройдемося
1981. 1:21:47по її можливих значень чи відповідає
1982. 1:21:49понеділок цьому присвоєнню Так
1983. 1:21:51відповідає д - це різні дні понеділок і
1984. 1:21:54вівторок a b також різні дні понеділок і
1985. 1:21:57вівторок Поки що все добре спробуємо ще
1986. 1:22:00раз перейдемо до змінної і Чи можемо ми
1987. 1:22:03її зробити сумісною перебираємо можливі
1988. 1:22:05значення ми рекурсивно викликали бектрек
1989. 1:22:08можемо почати з понеділка сумісності не
1990. 1:22:10буде тому що іспити з D та і
1991. 1:22:12відбуваються в один день тож можемо
1992. 1:22:15спробувати вівторок натомість перейти до
1993. 1:22:17наступного і запитати чи це буде
1994. 1:22:19сумісним ні не буде тому що іспити з B
1995. 1:22:21та і відбуваються вди день Гаразд
1996. 1:22:23спробуємо середу і середа виявляється
1997. 1:22:25підходить тому що іспити з D та і тепер
1998. 1:22:28відбуваються в різні дні іспити з B та і
1999. 1:22:31також відбуваються в різні дні поки що
2000. 1:22:33здається все гаразд Я рекурсивно
2001. 1:22:36викликаю бектрек вибираю іншу
2002. 1:22:38неприсвоєно змінно цього разу с вибираю
2003. 1:22:40значення якого може набути с починаю З
2004. 1:22:44понеділка Виявляється що сумісності
2005. 1:22:46немає тому що тепер іспити з A і C
2006. 1:22:49відбуваються в один день і я вибираю
2007. 1:22:51вівторок він також ж не буде сумісним
2008. 1:22:53тому що іспити з бій і сі тепер
2009. 1:22:55відбуваються в один день тоді я спробую
2010. 1:22:58середу але і середа не підходить тому що
2011. 1:23:00іспити з C та і теж відбуваються в один
2012. 1:23:04день ми перебрали всі можливі значення
2013. 1:23:07для с понеділок вівторок і середу і
2014. 1:23:09жодне з них не буде сумісним ми ніяк не
2015. 1:23:12можемо отримати сумісне присвоєння
2016. 1:23:13бектрек у цьому випадку поверне фейлер і
2017. 1:23:17тоді ми повернемося аж сюди для вузла і
2018. 1:23:19ми перебрали і понеділок і вівторок і
2019. 1:23:21середу і жоден день не спрацював середа
2020. 1:23:25яка Здавалося б мала спрацювати
2021. 1:23:27повернулася зі значенням failр це
2022. 1:23:29означає що ми ніяк не можемо присвоїти
2023. 1:23:31значення і невдача повертаємося до ді що
2024. 1:23:34означає що присвоєня понеділка ді теж
2025. 1:23:36неправильне Треба спробувати щось інше
2026. 1:23:39Що як замість понеділка ми спробуємо
2027. 1:23:42вівторок вівторок не підходить тому що
2028. 1:23:45іспити з біїді тепер в один день а от
2029. 1:23:48середа
2030. 1:23:50підходить тепер ми знову можемо
2031. 1:23:52просуватися вперед повертаємося до і яке
2032. 1:23:55з цих значень спрацює Виявляється що
2033. 1:23:57понеділок Тому що він не порушує жодних
2034. 1:23:59обмежень тоді переходимо до сі понеділок
2035. 1:24:02не підходить бо порушує обмеження навіть
2036. 1:24:04два обмеження вівторок не працює Тому що
2037. 1:24:06також порушує обмеження а от середа
2038. 1:24:08працює переходимо до наступної змінної F
2039. 1:24:11понеділок підходить Ні він порушує
2040. 1:24:13обмеження а вівторок підходить І нарешті
2041. 1:24:16можемо перевірити останню зміну G
2042. 1:24:18рекурсивно викликавши бектрек ще раз
2043. 1:24:20понеділок не буде сумісним тому що
2044. 1:24:21порушує обмеження вівторок також порушує
2045. 1:24:24обмеження а от середа не порушує
2046. 1:24:28обмеження зараз на цьому етапі
2047. 1:24:30рекурсивно викликаємо бектрек в останньо
2048. 1:24:33У нас є задовільний розподіл усіх
2049. 1:24:35змінних На цьому етапі можна сказати що
2050. 1:24:37ми
2051. 1:24:38закінчили ми змогли успішно присвоїти
2052. 1:24:41значення кожній зміні Так що не порушили
2053. 1:24:44жодних
2054. 1:24:46обмежень у понеділок будуть іспити з
2055. 1:24:48предметів a та і у вівторок складатимуть
2056. 1:24:50іспити з предметів B та F а в середу
2057. 1:24:52можна провести іспити з предметів CD і G
2058. 1:24:56і тут немає жодних порушених
2059. 1:25:00обмежень Це був графічний огляд того як
2060. 1:25:03це може працювати тепер подивімося який
2061. 1:25:06код ми можемо використати для того щоби
2062. 1:25:08вирішити це завдання Я зараз перейду до
2063. 1:25:13каталога
2064. 1:25:14scheduel ось ми тут почнемо з перегляду
2065. 1:25:17schedule 0.p ми тут я визначаю список
2066. 1:25:21змінних A B C D E FG це все різні класи
2067. 1:25:26під ними я визначаю список
2068. 1:25:29обмежень обмеження a і B - це обмеження
2069. 1:25:32тому що вони не можуть бути в один день
2070. 1:25:34так само A і C b c і так далі всі пари
2071. 1:25:38обмежень і ось який вигляд може мати
2072. 1:25:40функція
2073. 1:25:42backtrack
2074. 1:25:43по-перше якщо присвоєння завершено якщо
2075. 1:25:46я присвоїв кожній зміні значення просто
2076. 1:25:49поверніть
2077. 1:25:51його потім ми беремо неприсвоєну змінну
2078. 1:25:54з цього присвоєння потім для кожного з
2079. 1:25:56можливих значень у області визначення
2080. 1:25:58понеділок вівторок середа створимо нове
2081. 1:26:00присвоєння яке присвоює змінній це
2082. 1:26:03значення я назву цю функцію consistн Ось
2083. 1:26:07я її показує вона перевіряє чи нове
2084. 1:26:10присвоєння сумісне якщо воно сумісне ми
2085. 1:26:12викличемо функцію backтraк щоб
2086. 1:26:14продовжити виконання пошуку З
2087. 1:26:15поверненням І доки результат не nн Тобто
2088. 1:26:18нефейлер ми можемо продовжити і
2089. 1:26:20повернути цей результат Але якщо ми
2090. 1:26:23перебираємо всі значення і нічого не
2091. 1:26:25виходить тоді розв'язку немає ми
2092. 1:26:27повертаємо
2093. 1:26:29нан що роблять ці функції Select unite
2094. 1:26:33variable вибирає зміну яку ще не
2095. 1:26:35присвоєно вона перебирає всі зміні і
2096. 1:26:37якщо вона ще не призначена ми повернемо
2097. 1:26:39цю змінну А що робить функція
2098. 1:26:43consнistн вона перебирає всі
2099. 1:26:46обмеження якщо ми маємо ситуацію коли ми
2100. 1:26:49присвоїли змінним обидва значення але
2101. 1:26:52вони однакові то це порушення обмеження
2102. 1:26:55і в цьому випадку ми повернемо фолse але
2103. 1:26:58якщо нічого не суперечи тоді присвоєння
2104. 1:27:01сумісне і повернеться
2105. 1:27:03True І тоді все що робить програма це
2106. 1:27:06викликає бектрек до порожнього значення
2107. 1:27:09порожнього словника у якому ще не
2108. 1:27:10присвоєно жодної змінною і немає жодних
2109. 1:27:12значень зберігаю його всередині
2110. 1:27:14розв'язку а потім виводить його на екран
2111. 1:27:17запустивши цю програму я запускаю Python
2112. 1:27:20schedule 0.p
2113. 1:27:22і в результаті я отримую присвоєння
2114. 1:27:24значень усім цим змінним Виявляється що
2115. 1:27:27ми присвоюємо е понеділок як її слід
2116. 1:27:30було очікувати бій вівторок с середа
2117. 1:27:32тобто саме про це ми говорили раніше про
2118. 1:27:34присвоєння кожній змінні значень які не
2119. 1:27:37порушують жодних
2120. 1:27:39обмежень мені довелося виконати чималий
2121. 1:27:41обсяг роботи щоб реалізувати цю ідею
2122. 1:27:43самому довелося написати функцію бектрек
2123. 1:27:46яка рекурсивно намагалася здійснити цей
2124. 1:27:48пошук З поверненням але Виявляється що
2125. 1:27:50завдання задоволення межень настільки
2126. 1:27:52популярні що існує багато бібліотек які
2127. 1:27:55вже реалізують подібні ідеї знову ж таки
2128. 1:27:58як і раніше конкретна бібліотека не
2129. 1:28:00настільки важлива Як сам факт існування
2130. 1:28:03бібліотек це лише один з прикладів
2131. 1:28:05бібліотеки обмежень python де замість
2132. 1:28:07того щоб пробити всю роботу з нуля
2133. 1:28:09всередині schedle 1.p я просто
2134. 1:28:11використовую бібліотеку яка вже реалізує
2135. 1:28:14багато з цих ідей я створюю нове
2136. 1:28:16завдання додам до нього зміні з певними
2137. 1:28:18областями визначення додаю купу
2138. 1:28:21індивідуальних обмежень викликаю Add
2139. 1:28:23constraint і передаю функцію яка описує
2140. 1:28:26що це за обмеження обмеження переважно
2141. 1:28:29говорить що це функція яка приймає дві
2142. 1:28:31змінні X І Y і гарантує що не дорівнює y
2143. 1:28:34забезпечуючи ідею що не можна в один
2144. 1:28:37день скласти іспити з цих двох предметів
2145. 1:28:39а потім для будь-якої задачі на
2146. 1:28:41задоволення обмежень я можу викликати
2147. 1:28:43Get Solutions щоб отримати всі розв'язки
2148. 1:28:46цієї задачі а потім для кожного з цих
2149. 1:28:49розв'язків роздрукувати те що це за
2150. 1:28:51розв'язок і якщо я запущу python
2151. 1:28:53schedule 1.p то побачу що насправді
2152. 1:28:56Існує декілька різних рішень які можна
2153. 1:28:58використати для розв'язання проблеми
2154. 1:29:00насправді є шість різних рішень
2155. 1:29:02присвоєння змінним значення які дадуть
2156. 1:29:04мені задовільну відповідь на це завдання
2157. 1:29:06задоволення обмежень Отже це була
2158. 1:29:09реалізація дуже простого пошуку З
2159. 1:29:11поверненням де ми перебирали всі змінні
2160. 1:29:13вибирали ту якій Не було присвоєного
2161. 1:29:15нічого пробували можливі значення яких
2162. 1:29:17вона могла набути і якщо це не
2163. 1:29:19порушувало жодних обмежень ми продовжули
2164. 1:29:22пробувати інші змінні А якщо заходили в
2165. 1:29:25глухий кут то поверталися але ми могли
2166. 1:29:28би діяти більш розумно щоби підвищити
2167. 1:29:30ефективність вирішення подібних завдань
2168. 1:29:33Наприклад ми могли би повернутися до
2169. 1:29:35ідеї висновку використовуючи знання які
2170. 1:29:39ми знаємо щоби мати можливість робити
2171. 1:29:41висновки і зробити решту процесу
2172. 1:29:43вирішення
2173. 1:29:45простішим А тепер повернемося до того
2174. 1:29:48місця де Ми застрягли вперше коли ми
2175. 1:29:51вирішували завдання задоволення обмежень
2176. 1:29:54Ми розібралися з бій а потім перейшли до
2177. 1:29:57дії і присвоїли її значення понеділок бо
2178. 1:29:59здавалося що має бути саме так і що
2179. 1:30:02обмеження не порушуються але згодом
2180. 1:30:04виявилося що вибір невдалий що він не
2181. 1:30:06був сумісним зрештою значені у чому
2182. 1:30:09полягає питання Чи можемо ми
2183. 1:30:11використовуючи знання які маємо на
2184. 1:30:13початковому етапі щось зробити щоб
2185. 1:30:16уникнути такої ситуації щоб не йти
2186. 1:30:18шляхом який зрештою нікуди не приведе
2187. 1:30:23Виявляється що ми маємо подібні знання
2188. 1:30:26Ми можемо подивитися на структуру графа
2189. 1:30:28і можемо сказати що зараз наприклад
2190. 1:30:31область с містить значення понеділок
2191. 1:30:33вівторок і
2192. 1:30:35середа і на основі цих значень ми можемо
2193. 1:30:38сказати що цей граф не
2194. 1:30:41дугосумісний нагадаю що сумісність дух
2195. 1:30:43полягає в тому що для кожного можливого
2196. 1:30:45значення вузла існує деяке інше значення
2197. 1:30:49яке ми можемо вибрати як видно тут
2198. 1:30:52понеділок і вівторок не будуть можливими
2199. 1:30:54значеннями які ми можемо вибрати для с
2200. 1:30:57Вони не будуть сумісними з вузлом B тому
2201. 1:31:00що b дорівнює вівторку а це означає що C
2202. 1:31:03не може бути вівторком А оскільки A
2203. 1:31:06дорівнює понеділку C також не може бути
2204. 1:31:08понеділком використовуючи цю інформацію
2205. 1:31:11зробивши C догосумісним з a і b ми
2206. 1:31:15можемо видалити понеділок і вівторок з
2207. 1:31:17області визначення Сі і залишити Сі і
2208. 1:31:20середою якщо ми продовжимо забезпечувати
2209. 1:31:23сумісність дух то побачимо що можна
2210. 1:31:25зробити й інші висновки ми бачимо що
2211. 1:31:28єдиним варіантом для b є вівторок А
2212. 1:31:30єдиним варіантом для с середа якщо ми
2213. 1:31:33хочемо зробити і дугосумісним то і не
2214. 1:31:35може бути вівторком бо не буде
2215. 1:31:37госумісним із B і не може бути середою
2216. 1:31:40бо не буде довгосумісним із C тому ми
2217. 1:31:43встановлюємо для і значення понеділок а
2218. 1:31:46потім повторимо цей процес щоб зробити
2219. 1:31:48ді довгосумісним із B і і ді має бути
2220. 1:31:52середою це єдиний можливий варіант і так
2221. 1:31:54само ми можемо зробити ті самі висновки
2222. 1:31:56для F і G Виявляється що без додаткового
2223. 1:32:00пошуку просто застосувавши сумісність
2224. 1:32:02дух ми змогли з'ясувати Що слід
2225. 1:32:04присвоювати кожній зміні причому без
2226. 1:32:07повернення суть цього процесу полягає в
2227. 1:32:10тому щоби ми чергували процес пошуку і
2228. 1:32:14висновки коли намагалися застосувати
2229. 1:32:17сумісність дух цей алгоритм часто
2230. 1:32:19називають підтримкою сумісності дух він
2231. 1:32:23застосовує сумісність дух щоразу коли ми
2232. 1:32:26присвоюємо нове значення
2233. 1:32:29змінні іноді ми можемо застосувати
2234. 1:32:32сумісність дух за допомогою алгоритму
2235. 1:32:34AC3 на самому початку завдання ще до
2236. 1:32:37того як почнемо пошук щоб обмежити
2237. 1:32:40область змінних і полегшити пошук але ми
2238. 1:32:44також можемо скористатися перевагами
2239. 1:32:46чергування пошуку та сумісності дух
2240. 1:32:48щоразу в процесі пошуку коли ми робимо
2241. 1:32:51нове прис двоєння Ми також застосовуємо
2242. 1:32:53сумісність дух щоби переконатися що що
2243. 1:32:56ми виключаємо можливість значення з
2244. 1:32:57областей визначення де це можливо як же
2245. 1:33:00ми це робимо це еквівалентно тому що
2246. 1:33:03кожного разу коли ми присвоюємо нове
2247. 1:33:05значення змінні ми будемо викликати
2248. 1:33:07алгаритм AC3 який забезпечує сумісність
2249. 1:33:10дух у завданні задоволення обмежень Ми
2250. 1:33:13почнемо з черги не з усіх дух які ми
2251. 1:33:15робили спочатку а лише з тих дух які ми
2252. 1:33:18хочемо зробити сумісними з
2253. 1:33:20тобто зі змінною яй Ми щойно присвоїли
2254. 1:33:23значення тобто з усіх дух yx dy - це
2255. 1:33:27сусідх тобто має спільне обмеження з
2256. 1:33:32підтримуючи послідовність під час пошуку
2257. 1:33:34з повернення ми можемо зробити процес
2258. 1:33:36пошуку трохи
2259. 1:33:38ефективнішим це переглянута версія
2260. 1:33:40функції
2261. 1:33:42backtrack зміни виділено жовтим кольором
2262. 1:33:45як і раніше щоразу коли ми додаємо
2263. 1:33:48змінна дорівнює значення ми запускаємо
2264. 1:33:50процедуру висновку яка може робити
2265. 1:33:52багато різних речей одна з яких - це
2266. 1:33:55виклик алгоритму підтримки сумісності
2267. 1:33:56дух щоби переконатися що ми можемо
2268. 1:33:59забезпечити сумісність дух у завданні у
2269. 1:34:02результаті цього процесу ми зможемо
2270. 1:34:03зробити нові висновки наприклад отримати
2271. 1:34:06нові гарантії того що ця змінна має
2272. 1:34:08дорівнювати цьому значенню Це може
2273. 1:34:11статися один раз чий багато разів Якщо
2274. 1:34:13ці висновки не невдалі якщо вони не
2275. 1:34:16призводять до ситуації коли немає
2276. 1:34:17жодного можливого способу просунутися
2277. 1:34:19вперед тоді ми можемо продовжити
2278. 1:34:22додавати ці висновки ті нові знання які
2279. 1:34:24я знаю про те яким змінним слід
2280. 1:34:27присвоїти які значення я можу додати їх
2281. 1:34:30до присвоєння щоб швидше просуватися
2282. 1:34:32вперед використовуючи інформацію яку я
2283. 1:34:35можу просто вивести інформацію яку я
2284. 1:34:37знаю виходячи з решти структури завдання
2285. 1:34:39задоволення обмежень є ще одна зміна яку
2286. 1:34:41потрібно буде внести якщо виявиться що
2287. 1:34:44це значення не працює то тут потрібно
2288. 1:34:46буде видалити Не тільки змінна дорівнює
2289. 1:34:48значення але й усі висновки які я зробив
2290. 1:34:53отак можна вирішити завдання
2291. 1:34:54повертаючись назад не так часто ніж
2292. 1:34:57спочатку просто скориставшись тим фактом
2293. 1:34:59що кожного разу коли ми присвоюємо
2294. 1:35:01змінні і нове значення це може зменшити
2295. 1:35:04області визначення інших змінних Також
2296. 1:35:07ми можемо використовувати цю інформацію
2297. 1:35:09щоби швидше робити висновки і вирішувати
2298. 1:35:11завдання
2299. 1:35:13ефективніше Виявляється що є й інші
2300. 1:35:16евристики які ми можемо використовувати
2301. 1:35:18щоби підвищити ефективність процесу
2302. 1:35:20пошуку усе зводиться до кількох функцій
2303. 1:35:23про які я вже говорив але не говорив як
2304. 1:35:26вони працюють одна з них функція Select
2305. 1:35:30un Inside variable де ми вибираємо якусь
2306. 1:35:34змінну завдані задоволення обмежень які
2307. 1:35:36ще не було присвоєно значення досі я
2308. 1:35:39вибирав змінні навмання просто вибирав
2309. 1:35:41одну змінну без присвоєного значення
2310. 1:35:44просто вирішував що ця зміна буде
2311. 1:35:46наступною а потім будемо рухатися далі
2312. 1:35:48та виявляється що трішки подумавши
2313. 1:35:50дотримуючись певних евристик ми можемо
2314. 1:35:53зробити процес пошуку набагато
2315. 1:35:54ефективнішим просто ретельно обираючи
2316. 1:35:57яку змінну досліджувати
2317. 1:36:00далі наприклад евристика мінімальних
2318. 1:36:03залишкових значень або mrv евристика що
2319. 1:36:07це означає якщо в мене є вибір яку зміну
2320. 1:36:09вибрати Я маю вибрати зміну з найменшою
2321. 1:36:12областю визначення зміну яка має
2322. 1:36:14найменшу кількість залишкових значень
2323. 1:36:17ідея в тому що якщо Лишилося тільки два
2324. 1:36:19залишкові значення Я можу дуже швидко
2325. 1:36:21відкинути одне з них щоби дістатися до
2326. 1:36:24іншого бо одне з цих двох значень має
2327. 1:36:26бути рішенням якщо рішення існує А іноді
2328. 1:36:30мінімальні залишкові значення можуть не
2329. 1:36:31дати переконливого результату Наприклад
2330. 1:36:34якщо всі вузли мають однакову кількість
2331. 1:36:37залишкових значень У такому випадку може
2332. 1:36:39бути корисною ще одна евристика - Це
2333. 1:36:41евристика степені степінь вузла - це
2334. 1:36:43кількість вузлів які приєднані до цього
2335. 1:36:46вузла кількість вузлів які обмежені цим
2336. 1:36:48конкретним вузлом яку змінну мені слід
2337. 1:36:50вибрати вибирати зміну з високим
2338. 1:36:52степенем яка пов'язана з багатьма
2339. 1:36:54вузлами чи зміну з низьким степенем яка
2340. 1:36:57не пов'язана з багатьма вузлами часто є
2341. 1:37:00сенс вибрати змінну яка має найвищий
2342. 1:37:02степінь тобто пов'язана з більшістю
2343. 1:37:04інших вузлів як таку що ви шукатимете в
2344. 1:37:07першу чергу Чому так Тому що вибір
2345. 1:37:09змінної з високим степенем одразу ж
2346. 1:37:12обмежує решту змінних і це радше за все
2347. 1:37:14дозволить виключити великі ділянки
2348. 1:37:16простору станів які вам узагалі не
2349. 1:37:19потрібно
2350. 1:37:20переглядати
2351. 1:37:22Як же це відбувається на практиці
2352. 1:37:24повернімося до завдання пошуку у цьому
2353. 1:37:27конкретному випадку я присвоїв значення
2354. 1:37:29тут присвоїв тут Куди ж рухатися
2355. 1:37:33далі згідно з веристикою мінімальних
2356. 1:37:35залишкових значень Я маю вибрати змінну
2357. 1:37:38яка має найменше можливих залишкових
2358. 1:37:40значень у цьому випадку це вузол C який
2359. 1:37:43має лише одну змінну в області
2360. 1:37:45визначення у цьому випадку середа це
2361. 1:37:48дуже розумний вибір для наступного
2362. 1:37:50присвоєння бо Я знаю що це єдиний
2363. 1:37:53варіант Я знаю що єдиний можливий
2364. 1:37:54варіант для с - це середа тому я можу
2365. 1:37:57присвоїти значення тут а потім уже
2366. 1:37:59досліджувати решту
2367. 1:38:02простору тим часом на самому початку
2368. 1:38:05коли я ще не знав які вузли повинні мати
2369. 1:38:07яке значення потрібно було вибрати якому
2370. 1:38:11вузлу присвоїти значення першому я
2371. 1:38:14довільно вибрав Горішній вузол a але ми
2372. 1:38:17можемо підійти до цього більш розумно
2373. 1:38:19Подивіться на граф усі вузли мають
2374. 1:38:22область однакового розміру три тому
2375. 1:38:25мінімальні залишкові значення нам не
2376. 1:38:27допоможуть але ми бачимо що вузол і має
2377. 1:38:30найвищий степінь він пов'язаний з
2378. 1:38:32найбільшою кількістю інших вузлів
2379. 1:38:34можливо є сенс почати пошук не з вузла a
2380. 1:38:37а з вузла з найвищим степенем почати
2381. 1:38:39пошук з вузла і тому що звідси буде
2382. 1:38:41набагато легше застосувати обмеження які
2383. 1:38:44поруч усунувши великі ділянки простору
2384. 1:38:46пошуку які можливо і не знадобляться для
2385. 1:38:50пошуку почавши з і ми можемо одразу ж
2386. 1:38:53присвоїти інші значення а потім можемо
2387. 1:38:56присвоїти значення іншим змінним без
2388. 1:38:58жодних повернень Навіть якщо я не
2389. 1:39:00використовую процедури висновку
2390. 1:39:02починаємо з вузла який має вищий степінь
2391. 1:39:05і дуже швидко обмежимо значення яких
2392. 1:39:07можуть набувати інші
2393. 1:39:09вузли Таким чином ми можемо вибирати
2394. 1:39:12змінні без присвоєних значень у певному
2395. 1:39:14порядку а не випадково якщо підійдемо до
2396. 1:39:18процесу вибору змінних з розумом то
2397. 1:39:20зробимо процес пошуку набагато
2398. 1:39:22ефективнішим і нам Не доведеться шукати
2399. 1:39:24в тих частинах простору пошуку які
2400. 1:39:26зрештою не матимуть значення інша
2401. 1:39:29функція про яку ми ще не говорили це
2402. 1:39:31функція domain values ця функція приймає
2403. 1:39:34змінну і повертає послідовність усіх
2404. 1:39:37значень в області визначення цієї
2405. 1:39:39змінної безхитрий спосіб підійти до
2406. 1:39:42цього - це те що ми робили раніше тобто
2407. 1:39:44просто йти по порядку в понеділок
2408. 1:39:46вівторок середа але проблема в тому що
2409. 1:39:48пошук у такому порядку може бути не на
2410. 1:39:51наефективнішим іноді ефективніше буде
2411. 1:39:53спочатку вибрати значення які ймовірно є
2412. 1:39:55рішенням а потім перейти до інших
2413. 1:39:59значень як же оцінити чи є значення
2414. 1:40:02більш імовірним для вирішення завдання
2415. 1:40:04чи менш імовірним ви можете поглянути на
2416. 1:40:07те скільки обмежень додається Скільки
2417. 1:40:09значень видаляється з областей коли ви
2418. 1:40:12присвоюєте нове значення цій конкретній
2419. 1:40:16змінні тут ми можемо використати
2420. 1:40:19евристику найменш обмеж значення її суть
2421. 1:40:22у тому що ми маємо повертати змінні в
2422. 1:40:25порядку заснованому на кількості
2423. 1:40:27варіантів які виключені для сусідніх
2424. 1:40:29значень я почну з найменш обмеженого
2425. 1:40:31значення значення яке виключає найменше
2426. 1:40:34можливих варіантів ідея полягає в тому
2427. 1:40:37що якщо мене цікавить тільки пошук
2428. 1:40:39рішення якщо я починаю зі значення яке
2429. 1:40:42виключає багато інших варіантів я
2430. 1:40:45виключає багато можливостей які можливо
2431. 1:40:47зроблять менш імовірним те що саме цей
2432. 1:40:50вибір приведе до рішення з іншого боку
2433. 1:40:53якщо в мене є змінна і я починаю з
2434. 1:40:55вибору значення яке не виключає дуже
2435. 1:40:57багато Тоді в мене лишається багато
2436. 1:40:59простору де можна шукати рішення це може
2437. 1:41:02здатися трохи нелогічним і трохи
2438. 1:41:04суперечить тому Про що ми говорили
2439. 1:41:06раніше коли я казав що коли ви вибираєте
2440. 1:41:09зміну Вам слід вибирати ту у якої
2441. 1:41:11лишиться найменше можливих значень але
2442. 1:41:14тут я хочу вибрати значення для змінної
2443. 1:41:16яка є найменш обмеженою загальна ідея
2444. 1:41:19така що коли я вибираю змінну Я хочу
2445. 1:41:21скоротити велику частину простору пошуку
2446. 1:41:23просто вибравши змінну яка дозволить
2447. 1:41:25швидко виключити можливі варіанти тоді
2448. 1:41:28як тут у межах конкретної зміної коли я
2449. 1:41:31розглядаю значення яких може набувати ця
2450. 1:41:33зміна я хочу просто знайти рішення тому
2451. 1:41:36я вибираю таке значення яке залишає
2452. 1:41:38відкритою можливість знайти рішення з
2453. 1:41:40максимально можливою
2454. 1:41:42іймовірністю не виключаючи багато
2455. 1:41:44варіантів я лишаю можливість того що я
2456. 1:41:46все ще можу знайти рішення без
2457. 1:41:48необхідності повертатися
2458. 1:41:51наприклад у цій конкретній ситуації якщо
2459. 1:41:53я намагаюся вибрати значення для вузла с
2460. 1:41:56то С дорівнює або вівторку або середі ми
2461. 1:42:01знаємо що це не може бути понеділок Тому
2462. 1:42:03що це суперечить цій області визначення
2463. 1:42:06де ми вже знаємо що a - це понеділок
2464. 1:42:09Отже C має бути вівторок або
2465. 1:42:12середа Питання в тому що спробувати
2466. 1:42:15спершу вівторок чи середа якщо я виберу
2467. 1:42:18вівторок що буде виключено один варіант
2468. 1:42:20від відпадає тут другий варіант відпадає
2469. 1:42:22тут і третій варіант відпадає тут
2470. 1:42:25вибравши вівторок я відкидаю три можливі
2471. 1:42:28варіанти А якщо вибрати середу вибір
2472. 1:42:30середи виключає один варіант Тут і один
2473. 1:42:32варіант Тут Отже В мене є два вибори я
2474. 1:42:35можу вибрати вівторок який виключає три
2475. 1:42:37варіанти або середу яка виключає два
2476. 1:42:39варіанти згідно з евристикою найменш
2477. 1:42:41обмеженого значення Я маю вибрати середу
2478. 1:42:44яка виключає найменшу кількість можливих
2479. 1:42:46варіантів залишаючи відкритими якомога
2480. 1:42:49більше шансів для того щоб зрештою
2481. 1:42:51знайти рішення всередині простору станів
2482. 1:42:54якщо ми продовжимо цей процес то
2483. 1:42:56знайдемо рішення присвоєння зміним
2484. 1:42:59значень які дозволять призначити кожному
2485. 1:43:01з цих іспитів кожному з цих предметів
2486. 1:43:04дату іспиту яка не буде конфліктувати з
2487. 1:43:07тими хто записаний на два іспити
2488. 1:43:10одночасно Отже основний висновок з
2489. 1:43:13усього цього полягає в тому що є багато
2490. 1:43:15різних способів сформулювати завдання
2491. 1:43:18Сьогодні ми розглянули як можна
2492. 1:43:20фомулювати завдання локального пошуку
2493. 1:43:22тобто завдання в якому ми розглядаємо
2494. 1:43:24поточний вузол і переходимо до
2495. 1:43:26сусіднього на основі того чи цей сусід
2496. 1:43:29кращий чи гірший за поточний вузол ми
2497. 1:43:32розглядали лінійні програми де описуючи
2498. 1:43:34все рівняннями й обмеженнями можна
2499. 1:43:36вирішувати завдання ефективніше ми
2500. 1:43:38розглядали завдання задоволення обмежень
2501. 1:43:40створення графа всіх обмежень які
2502. 1:43:43пов'язані зі зміними що мають певні
2503. 1:43:45обмеження між собою і використання цієї
2504. 1:43:48інформації для того щоби зрозуміти яким
2505. 1:43:50має бути рішення висновок якщо ми хочемо
2506. 1:43:53за допомогою штучного інтелекту вирішити
2507. 1:43:56якесь завдання Чи то з'ясувати де мають
2508. 1:43:58бути лікарні чи то вирішити задачу
2509. 1:44:01комівояжера чи то оптимізувати
2510. 1:44:03виробництво чи то з'ясувати як
2511. 1:44:05задовольнити певні обмеження чи то в
2512. 1:44:07судоку чи то в розкладі іспитів в
2513. 1:44:10університеті чи то розв'язати будь-які
2514. 1:44:12найрізноманітніші завдання Якщо ми
2515. 1:44:15можемо сформулювати це завдання як одне
2516. 1:44:16з таких тоді ми можемо використовувати
2517. 1:44:19відомі нам алгоритми алгоритми для
2518. 1:44:21сумісності дух і пошуку З поверненням
2519. 1:44:24алгоритми сходження на вершину і
2520. 1:44:27імітації відпалу симплексметоди і методи
2521. 1:44:30внутрішньої точки які можна
2522. 1:44:31використовувати для вирішення лінійних
2523. 1:44:34програм ми можемо використовувати ці
2524. 1:44:36методи щоби вирішити різноманітні
2525. 1:44:38завдання у світі оптимізації в рамках
2526. 1:44:40штучного інтелекту це вступ до штучного
2527. 1:44:43інтелекту з python побачимося наступного
2528. 1:44:49разу
2529. 1:44:51fore