Информиран метод за търсене
Информирано търсене(същоевристично търсене, англ. informed search, heuristic search ) е стратегия за търсене на решения в пространството на състоянията, която използва знания, свързани с конкретна задача. Информираните методи обикновено осигуряват по-ефективни търсения от неинформираните методи.
Информацията за конкретна задача се формулира катоевристична функция. Евристичната функция на всяка стъпка от търсенето оценява алтернативите въз основа на допълнителна информация, за да реши в коя посока да продължи търсенето [1] .
Съдържание
В контекста на търсенето в пространството на състоянието,евристична функция(на английски heuristic function )h(n) се дефинира на възлитена дървото за изброяванекакто следва:
h(n) = оценка на разходите за най-евтиния път от възелnдо целевия възел.
Акоnе целевият възел, тогаваh(n) = 0.
Възелът, който ще бъде разгърнат, се избира въз основа нафункция за оценка(функция за оценка на английски)
f(n) = оценка на разходите за най-евтиния път на решение, минаващ през възелn,f(n) =g(n) +h(n),
където функциятаg(n) определя цената на вече преминатия път от началния възел до възелаn.
Ако евристична функцияh(n) никога не надценява действителната минимална цена за постигане на целта (т.е. това е по-ниската оценка на действителната цена), тогава такава функция се наричадопустима(на английски admissible ).
Ако евристична функцияh(n) удовлетворява условието
къдетоbе дете наa, тогава такава функция се наричапоследователна(англ.последователен).
Акоf(n) =g(n) +h(n) е функцията за оценка,h(n) е функцията наследник, тогава функциятаf(n) е монотонно ненамаляваща по всеки изследван път. Следователно последователните функции се наричат ощемонотонни(на английски monotonic ).
Всяка приемна функция е допустима, но не всяка допустима функция е наследник.
Акоh1(n),h2(n) са валидни евристики иh1(n) ≥h2(n), тогаваh1 епо-информиранаевристика илидоминиранадh2.
Ако проблемът има допустими евристикиh1 иh2, тогава евристикатаh(n) = max(h1,h2) е допустима и доминира над всяка от оригиналните евристики [1] [2] .
Сравнение на евристични функции
Когато се сравняват допустимите евристики, степента на информираност и пространствената и времева сложност на изчисляването на всяка от евристиките имат значение. По-информираната евристика може да намали броя на разгърнатите възли, въпреки че цената за това може да бъде времето, необходимо за изчисляване на евристика за всеки възел.
Коефициентът на ефективно разклоняванее средният брой приемници на възли в дървото за изброяване след прилагане на евристични методи за съкращаване [1] [2] . По ефективния коефициент на разклоняване може да се прецени качеството на използваната евристична функция.
Една идеална евристична функция (напримертаблица за търсене) винаги връща точната дължина на най-краткото решение, така че дървото на итерациите съдържа само оптималните решения. Ефективен фактор на разклоняванеидеалната евристична функция е близка до 1 [1] .
Примери за задачи за търсене
Пермутационните пъзели често се използват като модели за тестване на алгоритми за търсене и евристични функции - Петнадесет пъзела 3 × 3 [3] [4] , 4 × 4 [5] [6] [7] , 5 × 5 [8] [9] [10] , 6 × 6 [11] , Кубът на Рубик [9] [12] , Ханойската кула с четири пръта [11] [1 3] .
Евристикатаhm, базирана на разстоянието Манхатън, може да се приложи в пъзела 15. По-конкретно, за всяка плочка се изчислява разстоянието Манхатън между текущата и първоначалната й позиция; получените стойности се обобщават.
Може да се покаже, че тази евристика е допустима и последователна: нейната стойност не може да се промени с повече от ±1 за един ход.
Конструиране на евристични функции
Спокойна задача
Евристичната функцияhm, използвана за решаване на пъзела "Петнадесет", е долна граница на дължината на оптималното решение. В допълнение,hm(n) е точната дължина на оптималното решение наопростената версияна пъзела, в която плочките могат да се местят на техните позиции. В оригиналния пъзел има ограничение "не трябва да има две или повече плочки в една клетка", което го няма в опростената версия. Проблем с по-малко ограничения върху възможните действия се наричаотпуснат проблем(англ. relaxed problem); цената на решаването на облекчения проблем е валидна евристика за първоначалния проблем [1], тъй като всяко решение на първоначалния проблем също е решение на облекчения проблем.
Допустимата евристика може да се основава на цената на решаването наподпроблема(англ. subproblem ) на първоначалния проблем. Всяко основно решениезадачата е едновременно решение на всяка своя подзадача [1] .
Подзадача на задачата за решаване на пъзела "Петнадесет" може да бъде задачата за преместване на плочки 1, 2, 3 и 4 на местата им. Цената на решаването на тази подзадача е валидна евристика за първоначалния проблем.
Шаблонни бази данни
Шаблонни бази данни [1] (англ. Pattern databases) е вид валидна евристика, която се основава на идеята за съхраняване на точната стойност на цената на решението за всеки възможен екземпляр на подзадача [1] [6] [12] .
Търсене по първо най-добро съвпадение
първо най-доброто търсенее подход, при който възел за разгръщане се избира въз основа на функцията за оценкаf(n). Възелът с най-нисък резултат се избира за внедряване.
Търсене A*е най-известният тип търсене за най-доброто първо съвпадение. Той използва оценкатаf(n) на цената на най-евтиния път на решение, минаващ през възелаn:
f(n) =g(n) +h(n), къдетоg(n) е цената на пътя от началния възел до възелn,h(n) е прогнозната цена на пътя от възелnдо дестинацията.
Акоh(n) никога не надценява цената за достигане на целта (т.е. е достъпно), тогава търсенето на A* е оптимално.
Алгоритъм A* с итеративно задълбочаване(итеративно задълбочаване A*,IDA*) е приложение на идеята за итеративно задълбочаване в контекста на евристичното търсене.
Алгоритъмът за неинформирано итеративно задълбочаване спира разширяването, когато дълбочината на търсенеdнадвиши текущото ограничение на дълбочинатаl. Информираният IDA* алгоритъм спира внедряването при оценкаf(n) цената на пътя през текущия възелnнадвишава текущия лимит на цената на пътясвързан.
Алгоритъмът IDA* се характеризира с минимално натоварване на паметта в сравнение с A* и относително малък (в случай на успешен избор на евристика) брой разгърнати възли в сравнение с IDDFS.