Стратегия эвристического поиска

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

Один из путей использования эвристической информации о задаче - это получение численных эвристических оценок для вершин пространства состояния. Оценка вершины указывает нам, насколько данная вершина перспективна с точки зрения достижения цели. Идея состоит в том, чтобы всегда продолжать поиск, начиная с наиболее перспективной вершины, выбранной из всего множества кандидатов.

Существует целый ряд эвристических методов. Простейший из них носит название «взбирание на гору». Его принцип:

- если есть приемлемые варианты выбора, выберете наилучший из них, используя любой критерий рассуждения;

- если попали в тупик, вернитесь в последнее место, где имеются альтернативные варианты выбора, и сделайте следующий наилучший выбор.

Чтобы программа поиска маршрута выполняла эвристический поиск, она должна располагать базой для осуществления выбора. Предположим, в качестве базы программа примет соответствующее направления каждой дороги определенному азимуту: предпочтение будет отдаваться той дороге, которая более всего совпадает по направлению с прямой, соединяющей стартовую и целевую вершины (рис. 8.6).

Такой подход не всегда действенен, но это хорошая стратегия. В нашем примере программа исследует маршрут A ® B ® C и найдет тупик, затем вернется назад, в то место, где существует альтернатива выбору, т.е. в «В», а затем сразу отправится по маршруту B ® E ® F, который приведет к цели.

Рис. 6. Метод «Взбирание на гору»

Мы рассмотрели разные варианты поиска, но возникает вопрос: откуда взялось само дерево поиска??? Обычно машина создает дерево поиска сама на основе предлагаемых ей начальных сведений, причем делает это постепенно в процессе самого поиска.