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

Таким способом немонотонность может быть всегда устранена, и критерий ДЬ) никогда не будет уменьшаться вдоль одного и того же пути при условии, что h(b) допустимое. Если же f(b) никогда не уменьшается вдоль одного и того же пути, начинающегося от корневой вершины, то на пространство состояний можно наложить контуры, каждый из которых охватывает множество вершин Ь, для которых значение критерия ДЬ) меньше определенной величины с. Процесс поиска можно представить как переход 149 6. Стратегии поиска от просмотра еще не просмотренных вершин какого-либо внутреннего контура, для всех вершин А, которого имеет место /(6,) < с,, к просмотру вершин некоторого внешнего контура, для всех вершин Ь2 которого имеет место f(b2) < с2 и с, < с2. Это продолжается до тех пор, пока внутри очередного контура не окажется целевая вершина с h(b) = 0. При удачном выборе критерия fib) контуры как бы растягиваются в сторону целевой вершины, фокусируясь вокруг оптимального пути. Обозначим с* цену оптимального пути. Тогда можно утверждать следующее: