Поиск по заданному критерию
Программа поиска по заданному критерию может быть создана как усовершенствование программы поиска в ширину. Поиск по заданному критерию также начинается от начального узла, и в процессе его происходит сопровождение информации о множестве возможных путей. При поиске в ширину для продолжения всегда выбирается кратчайший возможный путь (т.е. путь через наименее глубокие концевые узлы, достигнутые в ходе поиска), а в программе поиска по заданному критерию применяется усовершенствованный вариант этого принципа: определяется эвристическая оценка для каждого возможного узла и для продолжения пути в соответствии с этой оценкой выбирается наилучший возможный узел.
В дальнейшем предполагается, что функция стоимости определена для дуг в пространстве состояний, а с(п,п') — это стоимость перемещения от узла п к его преемнику п ' в пространстве состояний.
Допустим, что для эвристической оценки применяется функция £, такая, что для каждого узла п в пространстве состояний функция f {п} служит для оценки "сложности достижения" п. Б соответствии с этим наиболее перспективным из всех текущих возможных узлов является тот, для которого значение функции f становит-
ся минимальным. В настоящей главе применяется сформированная особым образом функция f, которая дает возможность использовать широко известный алгоритм А*. Функция f (n) будет сформирована таким образом, чтобы она оценивала стоимость наилучшего пути решения от начального узла з до целевого узла, при том условии, что этот путь пройдет через узел п. Предположим, что такой путь имеется, и целевым узлом, для которого стоимость этого пути становится минимальной, является узел t. Б таком случае оценку f (п) можно сформировать как сумму двух тернов (рис. 12.1) следующим образом: f<n)=g(n) + h(n)
где g (n) — оценка стоимости оптимального пути от s до n, a h [п.) — оценка стоимости оптимального пути от п до t.
![]() |
Рис, 12,1. Формирование эвристической оценка f(n) стоимости пути с наименьшей
стоимостью от s до t через п: f(n} = g(n) + h (n)
После обнаружения узла п в процессе поиска возникает следующая ситуация: путь от з до п уже должен быть найден и его стоимость может быть вычислена как сумма стоимости дуг в этом пути. Такой путь от s до г не обязательно должен быть оптимальным (может существовать лучший путь от s до п, еще не обнаруженный в этом процессе поиска), но стоимость найденного пути, выраженная первым термом g (n), может служить в качестве оценки минимальной стоимости пути от s до п. Задача определения второго терма, h(n! , сложнее, поскольку "мир" между узлами п и t к этому времени еще не был исследован в процессе поиска. Поэтому h \r\';. , как правило, представляет собой в полном смысле слова эвристическую гипотезу, основанную на имеющейся в распоряжении алгоритма общей информации о данной конкретной задаче. Поскольку значение h зависит от проблемной области, универсального метода формирования функции h не существует. Конкретные примеры того, как могут выдвигаться подобные эвристические гипотезы, будут приведены ниже. Но на данный момент предположим, что функция h задана, и сосредоточимся на изучении программы поиска по заданному критерию.
Работу программы поиска по заданному критерию можно представить себе следующим образом. Процесс поиска состоит и» множества конкурирующих подпроцессов, каждый из которых исследует свой собственный вариант; иными словами, исследует собственное поддерево. В поддеревьях имеются свои поддеревья; они исследуются подпроцессами подпроцессов и т.д. Среди всех этих конкурирующих процессов в любой момент времени активным является только один — тот, который имеет дело с вариантом, являющимся в данный момент наиболее перспективным; таковым называется вариант с наименьшим значением функции f (или кратко
248 Часть I!.Применение языка Prolog в области искусственного интеллекта
{■значением), Остальные процессы должны находиться в состоянии ожидания до тех пор, пока текущие f-оценки не изменятся таким образом, что более перспективным станет какой-то иной вариант. После этого активность переключается на этот вариант. Можно представить себе, что такой механизм активизации и перехода в неактивное состояние действует следующим образом: процессу, работающему над вариантом, имеющим в настоящее время наивысший приоритет, выделяются некоторые ресурсы и процесс остается активным до тех пор, пока эти ресурсы не будут исчерпаны. В этот период активности процесс продолжает развертывать свое поддерево и сообщает решение, если был обнаружен целевой узел. Ресурсы для этого этапа выполнения выделяются на основании эвристической оценки ближайшего конкурирующего варианта.
Пример такого поведения показан на рис. 12.2. Предположим, что дана некоторая дорожная карта и задача состоит в том, чтобы найти кратчайший маршрут между начальным городом з и целевым городом Z- В процессе оценки стоимости оставшегося расстояния в маршруте от города X до цели используется расстояние по прямой, обозначенное как disc ( X, t). Поэтому справедлива следующая формула: f(X) = g(X) + h(x) = g(X} + diat( X, t)
В данном примере можно представить себе, что поиск по заданному критерию состоит из двух процессов, в каждом из которых исследуется один из двух возможных путей: в процессе 1 — путь через узел а, в процессе 2 — путь через узел е. На начальных этапах процесс 1 является более активным, поскольку f-значения вдоль его пути меньше, чем вдоль другого пути. А в тот момент, когда процесс 1 находится в узле с, а процесс 2 — все еще в узле е, ситуация изменяется следующим образом:
f(c) - д(с) + h(e) = & + 4 = ",0 f(e) = g(e) + h(e) = 2 + 7 = Э
Поэтому f (e] < f <cj, и теперь процесс 2 переходит к узлу £, а процесс 1 ожидает. Но здесь возникает такая ситуация:
f(f) = 7 + 4 = 11 f(c) = 10 f(c) < f(f)
Поэтому процесс 2 останавливается, а процесс 1 получает разрешение продолжить свою работу, но только до пункта d, когда обнаруживается, что f (d) = 12 > ] 1. Теперь процесс 2, активизированный в этот момент, беспрепятственно достигает цели t.
В процессе поиска, организованном таким образом, начиная с начального узла продолжается выработка новых узлов-преемников и путь всегда продлевается в наиболее перспективном направлении в соответствии с f-значения ми. В течение этого процесса формируется дерево поиска, корнем которого является начальный узел поиска. Поэтому рассматриваемая программа поиска по заданному критерию продолжает развертывать дерево поиска до тех пор, пока не будет найдено решение. Такое дерево представлено в данной программе с помощью термов в двух описанных ниже формах.
1. Терм 1( N, »■/(.■;; представляет отдельный узел дерева (лист); где N - узел в пространстве состояний, G - значение функции g{W, (стоимость пути, пройденного от начального узла до N), F — значение функции f(N) = G + h(N).
2. Терм t ( H, F/G, Subs) представляет дерево с непустыми поддеревьями; где N — корень дерева, Subs — список его поддеревьев, G — значение функции g (N), Е - "обновленное" f-значение И (под этим подразумевается f-значение наиболее перспективного преемника К); список Subs упорядочен в соответствии с возрастающими f-зпачения ми поддеревьев.
Например, снова рассмотрим процесс поиска, проиллюстрированный на рис. 12.2. В тот момент, когда был развернут узел а, дерево поиска состояло из трех узлов: корня s и двух его дочерних узлов, а и е. В рассматриваемой программе такое дерево поиска представлено следующим термом: t( s, 7/0, [1 [а, 7/2), 1 (е,Э/2>:>
Глава 12. Эвристический поиск по заданному критерию
![]() |
■V
<M = 2 + 5 = 7 la |
4+4 = 8 |
6 + 4=1 |
9 + 3 =
<(в) = 2 + 7 = 9
7 + 4=11
9 + 2 = 11
11 +0 = 11
Рис.122 Поиск кратчайшего маршрута от s до t покарте: а) карта, на которой указаны расстояния между городами; чи-ела в квадратах указывают расстояние по прямой до I; б) порядок, в котором происходит изучение карты при поиске по заданному критерию. При определении эвристических оценок so основу взяты расстояния по прямой.Пунктирная линия показывает, как происходит переключение активности между альтернативными путями. Сплошная линия показывает упорядочение узлов о соответствии с их {значениями, иными словами, порядок, в котором узлы развертывались (а не порядок, в котором они формировались)
Здесь f-значениекорня s равно 7, т.е. соответствует f-значениюнаиболее перспективного преемника корня — узла а. Теперь дерево поиска развертывается путем
Часть И. Применение языка Prolog в области искусственного интеллекта
развертывания наиболее перспективного поддерева а. Ближайшим конкурентом узла а является е, для которого f-значение равно 9. Таким образом, узлу а разрешено развернуться, при условии, что f-значение а не будеть превышать 9. Поэтому формируются узлы b и с. Значение f (с) = 10, поэтому предел развертывания превышен и варианту а больше не разрешено расти. В данный момент дерево поиска имеет следующий вид: t( s, 9/0, [l(e,S/2), t[a, 10/2, [t<b,10/4, [He, 10/6)] > ] ) ] )
Следует отметить, что теперь f-значение узла а равно 10, а узла s — 9. Эти значения обновлены в связи с тем, что были сформированы новые узлы, о и с. В настоящее время наиболее перспективным преемником узла s является е, для которого f-значение равно 9.
Обновление 1 -значенийнеобходимо для того, чтобы программа имела возможность распознавать на каждом уровне дерева поиска наиболее перспективное поддерево (т.е. дерево, которое содержит наиболее перспективный концевой узел). Такая модификация £-оценок приводит фактически к обобщению определения функции f. В результате этого обобщения определение функции £ распространяется с узлов на деревья. Для дерева, состоящего из отдельного узла (листа), п, было принято такое первоначальное определение:
f(и) = g{n) + h(n]
А для дерева Т, корнем которого является узел г., а поддеревьями узла п — деревья S , s и т.д., имеет место следующее определение:
f (?) - min f (Si) i
Программа поиска по заданному критерию, разработанная в соответствии с этими соглашениями, приведена в листинге 12.1. Ниже даны некоторые дополнительные пояснения к этой программе.
Основной процедурой программы является процедура expand, которая имеет следующие шесть параметров: expandt ?, Tree, Bound, Treel, Solved, Solution)
Она развертывает текущее дерево (поддерево), при условии, что f-значение этого дерева остается меньшим или равным значению Bound. Ниже приведены определения параметров процедуры expand.
• Р. Путь между начальным узлом и деревом Tree.
• Tree, Текущее дерево (поддерево) поиска.
■ Bound. Текущий f-предел для развертывания дерева Tree.
• Treel. Дерево 3, развернутое л пределах Bound; следовательно, f-значение для Treel больше чем Bound (если только в процессе этого развертывания не найден целевой узел).
• Solved. Индикатор, который может принимать значение "yes", "по" или "never".
• Solution, Путь решения от начального узла "через Treel" до целевого узла в пределах Bound (если такой целевой узел существует).