Программирование на языке ПРОЛОГ для искуственного интеллекта




Поиск с предпочтением - часть 2


Когда в процессе поиска мы попадаем в вершину   n,  мы оказываемся в следующей ситуация: путь из  s  в  n  уже найден, и его стоимость может быть вычислена как сумма стоимостей составляющих его дуг. Этот путь не обязательно оптимален (возможно, существует более дешевый, еще не найденный путь из  s   в  n),  однако стоимость этого пути можно использовать в качестве оценки  g(n)   минимальной стоимости пути из  s  в   n.  Что же касается второго слагаемого   h(n),  то о нем трудно что-либо сказать, поскольку к этому моменту область пространства состояний, лежащая между  n  и  t,   еще не "изучена" программой поиска. Поэтому, как правило, о значении  h(n)   можно только строить догадки на основании эвристических соображений, т.е. на основании тех знаний о конкретной задаче, которыми обладает алгоритм. Поскольку значение  h   зависит от предметной области, универсального метода для его вычисления не существует. Конкретные примеры того, как строят эти "эвристические догадки", мы приведем позже. Сейчас же будем считать, что тем или иным способом функция  h  задана, и сосредоточим свое внимание на деталях нашей программы поиска с предпочтением.

Можно представлять себе поиск с предпочтением следующим образом. Процесс поиска состоит из некоторого числа конкурирующих между собой подпроцессов, каждый из которых занимается своей альтерна-

fig12_2.gif (4971 bytes)

Рис. 12. 2.  Поиск кратчайшего маршрута из  s  в  t.   (а)  Карта со
связями между городами; связи помечены своими длинами; в
квадратиках указаны расстояния по прямой до цели  t.
(b)  Порядок, в котором при поиске с предпочтением происходит
обход городов. Эвристические оценки основаны на расстояниях
по прямой. Пунктирной линией показано переключение активности
между альтернативными путями. Эта линия задает тот порядок, в
котором вершины принимаются для продолжения пути, а не тот



Содержание  Назад  Вперед