Лекция 4: Методи за евристично търсене на път до определена цел



Дата13.09.2016
Размер38.52 Kb.
Лекция 4:Методи за евристично търсене на път до определена цел

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

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



Програмна реализация: чрез използване на работна памет (списък Open/frontier/fringe на т. нар. открити възли или списък от натрупани/изминати пътища, започващи от началния възел – фронт на търсенето).

Примерна задача: търсене на път между две селища. Пътна карта на Румъния:

Ще използваме данните от тази карта с цел илюстриране на работата на някои алгоритми за евристично търсене при намиране на път от Arad до Bucharest. Евристичната оценяваща функция ще връща като резултат разстоянието по права линия (straight-line distance) между текущо достигнатия град и целта (Bucharest).



1.Метод на най-доброто спускане (търсене на най-добър път, best-first search) - сортиране на списъка Open/fringe в съответствие с евристичната функция (например h(node) = <оценка на цената на пътя от node до целта>).
Построяване на пътя като списък от последователни състояния

• Фронтът на търсенето е сортиран отношение на стойностите на евристичната функция списък от пътища (отначало е списък от един път, който включва само началното състояние).

• Ако фронтът има вида [p1, p2, … , pn], то:

- Избира се p1. Ако p1 е довел до целта, край.

-Пътищата p11, p12, … , p1k, които разширяват p1, се добавят към фронта и новополученият фронт се сортира в нарастващ ред на оценките на пътищата, в резултат на което придобива вида [q1, q2, … , qn+k-1].

- На следващата стъпка се обработва пътят от фронта, който има най-добра евристична оценка, т.е. q1.



Пример: работа на алгоритъма best-first search при намиране на път върху картата на Румъния

Оценка на метода best-first search:

Методът е ефективен, но не е нито пълен (има опасност от зацикляне), нито оптимален.

Времевата сложност на метода е O(b^m), но използването на подходяща евристика може да доведе до съществено подобрение.

Пространствената сложност на метода е O(b^m), тъй като се съхраняват всички достигнати състояния.



2. Търсене с ограничена широчина (търсене в лъч, beam search) - ограничаване на списъка Open/fringe до първите n най-добри възела от него (в съответствие с евристиката). При n=1 се доближава до метода на най-бързото изкачване.

3. Метод на най-бързото изкачване (hill climbing) - списъкът Open/fringe се ограничава до най-добрия му елемент (в съответствие с евристиката), и то само ако той е по-добър от своя родител. Търсенето е еднопосочно, без възможност за възврат.

Възможни проблеми:

- локален екстремум – състоянието е по-добро от съседните (наследниците си), но не е най-доброто в цялото ПС;

- плато – съседните състояния (наследниците на текущото състояние) изглеждат също толкова добри, колкото и текущото;

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





4. Търсене с минимизиране на общата цена на пътя (A*) -комбинира търсене с равномерна цена на пътя с търсене на най-добър път. Списъкът Open/fringe се сортира в съответствие с функцията f(node) = g(node) + h(node). Тук функцията g връща като резултат цената на изминатия път от началния възел до node, а евристичната функция h връща като резултат приблизителна стойност на цената на оставащата част от пътя от node до целта.

Построяване на пътя като списък от последователни състояния

Фронтът на търсенето е сортиран по отношение на стойностите на функцията f списък от пътища (отначало е списък от един път, който включва само началното състояние).

Ако фронтът има вида [p1, p2, … , pn], то:

o Избира се p1. Ако p1 е довел до целта, край.

o Ацикличните пътища p11, p12, … , p1k, които разширяват (продължават) p1, се добавят към фронта и новополученият фронт се сортира в нарастващ ред на оценките на пътищата, в резултат на което придобива вида

[q1, q2, … , qn+k-1].

o На следващата стъпка се обработва пътят от фронта, който има най-добра оценка (най-добра стойност на функцията f), т.е. q1.


Пример: работа на алгоритъма A* при намиране на път върху картата на Румъния

Оценка на метода A*:

Стратегията е пълна, ако разклоненията (наследниците) на всеки възел от ГС са краен брой и цената на преходите е положителна, и оптимална, ако евристиката е приемлива (оптимистична), т.е. никога не надценява стойността (цената) h* на оставащия път (ако h*(node) ≥ h(node) за всеки възел node).

Времевата и пространствената сложност на метода са експоненциални.
Примери за приемливи (оптимистични) евристики

При задачата за 8-те плъзгащи се плочки (the 8-puzzle problem):

• h1(S) = броя на плочките, чиято текуща позиция е различна от позицията им в целевото състояние

• h2(S) = тоталното (сумарното) Манхатънско разстояние

Манхатънско разстояние (Manhattan Distance) между точките (Xi,Yi) и (Xj,Yj): D = |Xi-Xj| + |Yi-Yj|.
Пример

h1 (Start) = 8



h2(Start) = 3+1+2+2+2+3+3+2 = 18


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница