Задачи, които се решават с ходове
Съветникът от миналия час дава отговор с една проверка на правилата. Но много задачи не са „кой е отговорът“, а „каква поредица от стъпки води до целта“: да се нареди пъзел, да се намери път в града, роботът да подреди кутиите, програмата да победи в игра. Отговорът е план, а не дума.
Компютърът няма интуиция за такива задачи. Има нещо друго: може да пробва много. Номерът е да опишем задачата така, че „пробването“ да стане механично. Това описание се нарича пространство от състояния (state space) и е в основата на навигацията, на планирането и на шахматните програми — темата на следващия час.
Състояние, ход, цел
Пространство от състояния
Множеството от всички възможни състояния на задачата заедно с ходовете, които водят от едно състояние в друго. Решение е път от началното до целевото състояние.
- Състояние — моментна снимка на всичко, което има значение. Не повече, не по-малко.
- Ход — действие, което превръща едно състояние в друго. Някои ходове са забранени в дадено състояние.
- Начално и целево състояние — откъде тръгваме и какво искаме. Целта може да е и условие („някоя кана съдържа 4 л“), не конкретно състояние.
- Граф на състоянията — състоянията са възли, ходовете — ребра. Търсенето на решение е търсене на път в този граф.
Вълк, коза и зеле
Фермер трябва да пренесе вълк, коза и зеле през река. В лодката се събира той и още едно нещо. Останат ли сами, вълкът изяжда козата, а козата — зелето. Кое е състоянието тук? Не „колко пъти е преминал“, а само: кой е на кой бряг.
| Състояние (ляв | десен) | Възможни ходове | Позволено? |
|---|---|---|
| ФВКЗ | – | Ф сам; Ф+В; Ф+К; Ф+З | само Ф+К — иначе някой изяжда някого |
| ВЗ | ФК | Ф сам; Ф+К | и двата (Ф+К е връщане назад) |
| ФВЗ | К | Ф сам; Ф+В; Ф+З | Ф+В и Ф+З; Ф сам оставя вълка със зелето — може, но е безполезно |
| З | ФВК | Ф сам; Ф+В; Ф+К | само Ф+К — вълкът и козата не остават сами |
Как обхождаме графа
Напосоки
От всяко състояние избираме случаен позволен ход. Работи за мънички задачи и не гарантира нищо: може да се въртим в кръг с часове. Затова първото правило на всяко търсене: помним посетените състояния и не влизаме повторно в тях.
В ширина
- Разглеждаме всички състояния на един ход от началото.
- После всички на два хода, които още не сме виждали.
- После на три хода… докато някое от новите е целта.
Търсенето в ширина (breadth-first) винаги намира решението с най-малко ходове. Цената: разглежда всичко на по-малко разстояние от целта и помни всички тези състояния.
В дълбочина
Тръгваме по един път докрай — ход след ход, докато не стигнем целта или задънена улица. Тогава се връщаме на последното разклонение и пробваме другия ход. Търсенето в дълбочина (depth-first) помни малко, но може да се залута далече от целта и да намери дълъг път вместо къс.
| В ширина | В дълбочина | |
|---|---|---|
| Най-кратък път | гарантирано | не |
| Памет | всички състояния на текущия слой | само текущия път |
| Риск | много състояния при далечна цел | залутване в дълъг клон |
| Кога | искаме най-краткия план | решението е дълбоко, паметта — малка |
Евристика — компас, не карта
Защо изобщо ни е нещо повече от ширина? Заради размера. Пъзелът 8 (осем плочки в квадрат 3×3) има 181 440 достижими състояния. Кубчето на Рубик — над 4·10¹⁹. Шахът — повече позиции, отколкото можем да изброим. Да обходим всичко е невъзможно; трябва да обхождаме умно.
Евристика (heuristic)
Бърза, приблизителна оценка колко е далеч дадено състояние от целта, пресметната само от самото състояние, без да се търси напред.
- Пъзел 8 — броят плочки не на мястото си, или сборът от разстоянията им до мястото.
- Път в града — разстоянието по права линия до целта (реалният път е поне толкова).
- Лодката — колко неща са още на левия бряг.
Най-простото търсене с евристика — алчното (greedy) — винаги продължава от посетеното състояние с най-добра оценка. То върви „по нюх“ право към целта и в добрите случаи разглежда няколко пъти по-малко състояния от търсенето в ширина. Ще го измерите в практикума.
Какво трябва да запомниш
- Задачата се описва със състояние (снимка на важното), ходове, начално и целево състояние.
- Графът на състоянията: възли — състояния, ребра — ходове. Решението е път в него.
- Ширина: най-кратък път, много памет. Дълбочина: малко памет, риск от залутване. Винаги помним посетените.
- Евристика: бърза оценка колко е далеч целта, пресметната от самото състояние.
- Евристиката насочва и пести време, но не гарантира — понякога целта иска стъпка „назад“.