I.9. Пространство на състоянията – основни понятия и задачи — Разширена писмена разработка

Разширена писмена разработка. I.9. Пространство на състоянията – основни понятия и задачи

Подробен авторски текст за подготовка по конспекта на СУ. Краткият вариант е запазен на основната страница на темата. За преговор използвай плана; за обосновка — определенията и разработените примери. Това не е официален изпитен образец.

Кратка разработка и уроци по темата · Учебник и справочник · План за изпита · Покритие · Източници

Обхват от конспекта

Пространство на състоянията – основни понятия и задачи. Формулировка на задачата за търсене на път до определена цел. Основни стратегии за неинформирано търсене. Методи за информирано търсене на път до определена цел.

Покритие на конспекта

Всяка подточка води към съответния раздел на разработката.

  1. Пространство на състоянията – основни понятия и задачи — 1. Пространство на състоянията
  2. Формулировка на задачата за търсене на път до определена цел — 2. Формулиране на задача за път до цел
  3. Основни стратегии за неинформирано търсене — 3. Основни стратегии за неинформирано търсене
  4. Методи за информирано търсене на път до определена цел — 4. Информирано търсене, евристики и A*

Кратък план за изпита

  1. Състояние, оператор, пространство и граф на търсене.
  2. Начало, цел, цена на път и формулиране на задача.
  3. Фронт, посетени състояния и критерии за сравнение.
  4. BFS, DFS, ограничена дълбочина, итеративно задълбочаване и UCS.
  5. Изкачване, локален максимум и плато; отсичане и best-first.
  6. Като допълнение: greedy и A*; условия за оптималност.
  7. Разработен пример и избор на стратегия.

1. Пространство на състоянията

Състоянието е описание на съществените за решаването на задача характеристики в даден момент. То трябва да съдържа достатъчно информация за определяне на допустимите действия и последствията им. Прекалено бедното описание смесва различни ситуации, а прекалено подробното създава излишно голямо пространство. Например при намиране на маршрут текущият град е достатъчен само ако бъдещите възможности не зависят от премълчани величини като оставащо гориво.

В учебника пространството на състоянията е съвкупността от възможните състояния, достижими от дадено начално състояние. В графовия модел към тях добавяме допустимите преходи. Оператор, или действие, преобразува състояние в друго, когато предусловията му са изпълнени. Представяме състоянията като върхове, а действията като насочени ребра. Възможно е графът да не е предварително изброен: наследниците се генерират при нужда.

Разграничаваме три задачи при работа с това пространство: да го генерираме; да търсим решение върху вече генерираното пространство; или да съчетаем постепенно генериране с търсене и оценяване. Последният вариант позволява да намерим целта, без да построяваме целия граф. По вида на търсеното решение учебникът различава път до цел, печеливша стратегия при игра и цел при ограничителни условия. В тази изпитна тема централна е първата задача; останалите очертават контекста.

Сверка със СУ 8: §1.1.1–1.1.6, стр. 16–19. Представянето с Лисп на стр. 17–18 илюстрира предшественици, наследници и вложени списъци; синтаксисът му не е отделна подточка на I.9.

Дървото на търсене е различно от графа на състоянията. Негов възел представя конкретен път до състояние, затова едно състояние може да се срещне многократно през различни пътища. Това поражда повторения и цикли и изисква решение кога две посещения са еквивалентни и кога новият път е по-добър.

2. Формулиране на задача за път до цел

Задачата се задава чрез начално състояние, множество допустими действия, функция на прехода, тест за цел и цена на действията. Решението е последователност от действия от началото до състояние, удовлетворяващо целта. При адитивна цена стойността на пътя е сумата от цените на неговите ребра. Допустимо решение и оптимално решение не са едно и също: оптималното има най-ниска цена според зададения критерий.

При пъзел с плочки състоянието описва разположението, действието мести съседна плочка в празната позиция, а целта проверява желаното подреждане. Ако всяко движение струва 1, оптимизацията е по брой движения. При маршрут с различни дължини или разходи минималният брой ребра може да не съвпадне с най-ниската цена.

Сверка със СУ 8: Видове цели и постановка: §1.1.6 и §1.2, стр. 19. Генериране и оценяване на състояние: §1.1.3, стр. 16–17. Оценка V в учебника е обща оценка; не всяка такава функция е оценка на оставаща цена h.

Общата схема пази фронт от открити, но необработени възли. Избира възел според стратегията, проверява за цел в подходящия момент и генерира наследници. При графово търсене се пазят посетени състояния или най-добри намерени цени. За UCS и A* целта обичайно се приема, когато е извадена като най-приоритетна, а не при първото ѝ генериране: по-късно може да се намери по-евтин път.

Ред на посещение ≠ път: списъкът на разгледаните върхове може да съдържа върхове от различни клонове. За да възстановим действителния път, пазим предшественик за всяко достигнато състояние и след достигане на целта проследяваме тези връзки назад. При по-добър път актуализираме и цената, и предшественика. СУ 8, стр. 22–23 изрично разграничава обхода от търсения път.

3. Основни стратегии за неинформирано търсене

Неинформираните стратегии използват описанието на задачата, без допълнителна оценка за близост до целта. BFS разглежда възли по нарастваща дълбочина чрез опашка. При крайно разклонение и достижима цел на крайна дълбочина то е пълно. При еднаква положителна цена на всяка стъпка намира и оптимален път. При различни цени тази гаранция отпада.

DFS използва стек или рекурсия и предпочита най-дълбокия открит възел. Паметта за активния път е малка в сравнение с фронта на BFS, но без защита от цикли може да не завърши. При безкрайна дълбочина може да остане в безкраен клон, макар да има решение в друг. Дори когато намира цел, не гарантира минимална дълбочина или цена.

Сверка със СУ 8: §1.2.1, стр. 19–23. На стр. 21 разликата DFS/BFS е поставяне на наследниците отпред/отзад в списъка на неизследваните състояния. Тук уточняваме гаранциите: „пълно изчерпване“ не означава, че DFS непременно завършва в безкрайно пространство; „най-кратък“ при BFS е по брой стъпки, а не по произволни тегла. Състоянията във фронта също се проверяват за дубликати, за да не се обработва многократно един и същ връх.

Търсенето с ограничена дълбочина спира на предварително зададена граница. То трябва да различава „няма решение“ от „достигната е границата“. Итеративното задълбочаване повтаря ограниченото търсене за граници 0,1,2,… . При крайно разклонение съчетава намиране на най-плитка цел с умерена памет, за сметка на повторно разглеждане на горните нива.

Допълнение към основното изложение на СУ 8: итеративното задълбочаване по-горе и UCS по-долу разширяват сравнението; не ги представяме като самостоятелни разгърнати раздели на проверените страници от книгата.

Uniform-cost search, UCS, избира най-малката натрупана цена g(n) чрез приоритетна опашка. При неотрицателни цени и правилно обработване на подобренията то намира най-евтиния път в краен граф. За гаранция за пълнота в безкрайни пространства обичайно се изискват крайно разклонение и положителна долна граница ε на цената на действие. Нулеви цикли не трябва да пораждат безкрайно повторно разгръщане.

Сравняваме стратегиите по пълнота, оптималност, време и памет. Ако b е факторът на разклонение, d — дълбочината на най-плитка цел, а m — максимална дълбочина, типичната дървовидна оценка за BFS е O(bd+1) време и памет, а за DFS — O(bm) време и O(bm) памет за фронта. При изрично зададен краен граф BFS/DFS с маркиране и списъци на съседство имат O(|V|+|E|) време и O(|V|) допълнителна памет. Това са различни модели на размера на входа, а не противоречащи си оценки.

4. Информирано търсене, евристики и A*

4.1. Изкачване и отсичане по оценка

Информираното търсене използва знание за задачата чрез оценяваща функция. При изкачване по-високата оценка означава по-перспективно състояние. Опростеният метод избира първия наследник, който подобрява текущата оценка. Методът на най-бързото изкачване оценява всички непосредствени наследници и избира най-добрия, ако той е строго по-добър от текущото състояние. И в двата случая действителната проверка за цел е отделна от проверката дали оценката се е подобрила.

При локален максимум текущото състояние е по-добро от съседите си, но още не е целта. При плато съседни състояния имат еднакви оценки и строгото правило за подобрение не позволява следваща стъпка. Затова прекратяване поради липса на подобрение не доказва, че задачата няма решение. Връщането назад и пробването на друга посока може да помогне; това вече е допълнение към простото еднопосочно изкачване.

Например нека S има оценка V(S)=3 и два наследника A и B с V(A)=5 и V(B)=4. A води само към C с V(C)=2, а B води към целта G с V(G)=10; други преходи няма. Най-бързото изкачване избира A и спира там, защото 2<5. Целта G все пак е достижима по S→B→G. Това е авторски пример за локален максимум, а не задача с липсващи предпоставки.

Учебникът разглежда и отсичане на състояния с близки оценки и чрез прагови оценки за безперспективност. Те намаляват разглежданите варианти, но ако отстранят единствения път до решение, се губи пълнотата. В тази тема „отсичане“ по евристична оценка не е доказателство, че отстраненият клон със сигурност няма решение.

Сверка със СУ 8: §1.2.2, стр. 23–26. Примерът с блокове и различни оценки е на стр. 24–26. Резултатът зависи не само от стратегията, но и от качеството на оценката.

4.2. Метод на най-доброто спускане — best-first

В §1.2.3 названието е „метод на най-доброто спускане“ (best-first). Избира се най-перспективният измежду всички чакащи възли, не само сред наследниците на текущия. Неизбраните възможности се запазват и могат да бъдат разгледани по-късно. Това го отличава от простото изкачване. По-ниска стойност означава по-добра оценка, когато функцията оценява разход.

Списъкът open съдържа генерираните, оценени, но още неразгърнати възли; closed съдържа разгърнатите. На стр. 28 оценката е записана като f′=g+h′: g е известната цена от началото, а h′ — приближение на оставащата цена. При открит по-евтин път се преразглеждат родителят и цената, а при нужда подобрението се предава и към наследниците. Не бива да отъждествяваме общото best-first само с алчния избор по h.

Сверка със СУ 8: §1.2.3, стр. 26–29, само до началото на §1.3 на стр. 29. „Открит/закрит връх“ в общото описание на стр. 17 има по-широк смисъл от конкретното членство в open/closed на стр. 28. По-долу разграничаваме съвременните варианти и условията за гаранциите им.

4.3. Допълнение: greedy и A*

При търсене на път с цена евристиката h(n) оценява оставащата цена от състояние до цел. Тя използва знание за предметната област и не е доказана реална цена. Допустима евристика никога не надценява оптималната оставаща цена: 0≤h(n)≤h*(n). Съгласуваната евристика изпълнява h(n)≤c(n,n′)+h(n′) за всяко ребро и h(цел)=0. Съгласуваността позволява стабилно обработване на затворените възли при стандартно A* графово търсене.

Алчната best-first стратегия избира най-ниската h(n). Тя може бързо да достигне цел, но игнорира платената дотук цена и няма обща гаранция за оптималност. A* избира най-ниската f(n)=g(n)+h(n). При h=0 то се свежда до UCS. При крайно разклонение, цена на всяка стъпка поне ε>0, достижима цел с крайна цена и проверка за цел при извличане от фронта, допустимата евристика дава пълнота и оптималност за стандартното дървовидно A*. При графово A* с допустима, но несъгласувана евристика може да е нужно повторно отваряне на състояние при по-добър g.

Евристика може да се получи от облекчена задача. Например разстоянието по права линия е долна граница за пътно разстояние, ако разходът действително измерва дължина и пътищата не нарушават тази геометрия. Не може същата оценка без преобразуване да се сравнява с цена в пари или време. По-информативната допустима евристика може да намали разглежданите възли, но изчисляването ѝ също има цена.

5. Самостоятелно описан пример

Нека имаме ориентирани ребра S→A с цена 2, S→B с цена 1, S→G с цена 10, A→G с цена 3 и B→G с цена 7. S е началото, G е единствената цел, други ребра няма. Избираме h(S)=3, h(A)=3, h(B)=2 и h(G)=0. Тези оценки не надценяват оставащите цени и са съгласувани по всички ребра.

BFS избира едноребрения път S→G с цена 10. Greedy също предпочита G заради h(G)=0. При A* след обработване на S фронтът съдържа B с g=1,f=3, A с g=2,f=5 и G с g=10,f=10. Обработването на B подобрява цената за G на 8. Следва A, което подобрява G на 5. Едва при извличане на G алгоритъмът приключва с път S→A→G и цена 5.

Съгласуваността тук се проверява по всички ребра: 3≤2+3, 3≤1+2, 3≤10+0, 3≤3+0 и 2≤7+0. При всяко подобрение на G запазваме новия му предшественик, затова накрая възстановяваме S→A→G, а не реда S, B, A, G на обработване.

Примерът показва защо най-близката по брой стъпки цел и целта с най-ниска евристика не са непременно най-евтини. В изпитния извод трябва да се свържат формулировката на задачата, критерият за избор на възел, необходимата памет и условията за гаранциите. Силна евристика не поправя неправилно описано състояние или пропуснати допустими действия.

Практическа връзка с учебника по структури от данни

Сверка със СУ 2: BFS/DFS: ориг. 239–243 / нов PDF 228–232; пътища и възстановяване: ориг. 244–249 / нов PDF 232–237.

Състоянията могат да се разглеждат като върхове, а допустимите действия — като дъги. При явно зададен малък граф можем да пазим списъци на съседство; при голямо пространство генерираме наследниците при нужда. Еднакво състояние, достигнато по различни пътища, не означава задължително различен връх, но пътищата и разходите до него могат да са различни.

Нека състоянията са S,A,B,G и действията S→A, S→B, A→G, B→A, всяко с цена 1. BFS от S, при ред A преди B, достига G по S→A→G с две действия. За възстановяване записваме parent[A]=S и parent[G]=A, после проследяваме назад. Редът на посещение S,A,B,G сам по себе си не е път. Маркирането още при включване във фронта предотвратява повторното добавяне на A през B.

Учебникът брои дължина на някои пътища по брой върхове; в примера това са 3 върха, но 2 ребра/действия. За непразен път разликата е единица и минимизирането дава същия избор. Това не важи за произволни тегла: ако S→A струва 8, а S→B, B→A и A→G струват по 1, пътят с повече ребра S→B→A→G струва 3 вместо 9. Тогава стандартното BFS не оптимизира цената.

Функцията за изчерпване на всички прости пътища може да намери минимум чрез сравняване на резултатите, но е различна от обикновено DFS и може да е много скъпа. Книгата е практическа опора за опашката, рекурсията и възстановяването на път. Евристиките, greedy, hill climbing и A* остават опрени на официалния учебник по изкуствен интелект и ясно отделените допълнителни източници.

СУ 2: учебник, проверен код и таблица за всички 20 теми · Допълнение по точните страници на учебника

Литературна опора и граници на сверяването

Официална библиография на СУ · Справочник с раздели и ред за четене

  • Официален източник СУ 8: Мария Нишева и Димитър Шишков, Изкуствен интелект, Интеграл, Добрич, 1995. Учебник — PDF, 179 страници. Предоставеното копие съвпада по титулни библиографски данни с конспекта. Сверени са §1.1–1.2.3, PDF/печатни стр. 16–29, до началото на §1.3 на стр. 29. Това е целева сверка за I.9, не научна редакция на цялата книга.
  • Номерация: PDF позициите и видимите печатни номера съвпадат в този диапазон. Съдържанието е с различни номера: §1.1 започва на 16, §1.2.1 на 19, §1.2.2 на 23 и §1.2.3 на 26. Връзките тук следват действителните страници. Старото кодиране затруднява копирането и търсенето на кирилица; сверяването е по визуално прочетените страници.
  • Допълнителна университетска опора, извън официалния списък: UC Berkeley CS188 §1.3 и §1.4. Запазените допълнения за UCS, сравнение на стратегиите, greedy и A* са разграничени от терминологията и изложението в СУ 8. Не приписваме целия този разширен набор на страниците от българския учебник.

Текстът, схемите и маршрутният пример са авторска учебна разработка, а не официален отговор на СУ. Източникът на първоначалното изтегляне на предоставения PDF не е установен; „официален“ тук означава включен в литературата на конспекта.

Обратно към кратката разработка и уроците