Искусственный интеллект

6.3.2. Поиск по критерию цены пути (А* - поиск) Обозначим g(b) — критерий цены пути из корневой вершины в вершину Ь, аЫр) — уже рассмотренный критерий близости к цели. Пусть оба критерия имеют одну и ту же размерность. Функцию/(6) = g(b) + h(b) можно считать критерием цеНы пути из корневой вершины в целевую. С помощью этого критерия можно находить пути с минимальной ценой. Рассмотрим стратегию поиска на основе этого критерия и покажем, что она будет полна и оптимальна, если ввести небольшие ограничения на критерий h(b). Идея этого ограничения состоит в том, чтобы выбирать критерий h{b) таким образом, чтобы не переоценивать близость к цели, т.е. не выбирать значение h{b) меньше, чем оно есть на самом деле. Критерий h(b), выбираемый таким образом, называется допустимым. Стратегия поиска, использующая критерий f(b) и допустимый критерий h(b), известна как А* - поиск. Критерий близости цели h(b), использованный в примере с поиском маршрута из Иванова в Москву, является типичным примером допустимого критерия, поскольку не может быть пути из одного населенного пункта в другой короче, чем кратчайший путь. На рис. 6. 6 показаны первые четыре шага поиска пути из Иванова в Москву с использованием критерия f(b) в А*- поиске. Заметим, что в результате этого поиска, в отличие от поиска только по критерию близости к цели, рассмотренного в предыдущем разделе, выбран путь к Москве не через Юрьев-Польский, а через Владимир, хотя Юрьев-Польский ближе к Москве, чем Владимир. Такой выбор объясняется тем, что цена пути g(b) от Иванова до Юрьева-Польского выше, чем до Владимира вследствие очень плохой дороги. Дальнейший выбор маршрута можно проследить по рисунку, где на любом пути от корневой вершины значение критерия f(b) нигде не уменьшается при переходе к рассмотрению очередной вершины. Это не случайность и справедливо