В этой главе показано, как можно с помощью информации о пространстве состояний не дать алгоритмам заблудиться в темноте.

В главе 3 показано, что неинформированные стратегии поиска позволяют находить решения задач путем систематической выработки новых состояний и их проверки применительно к цели. К сожалению, в большинстве случаев эти стратегии являются чрезвычайно неэффективными. Как показано в настоящей главе, информированные стратегии поиска (в которых используются знания, относящиеся к конкретной задаче) обеспечивают более эффективный поиск решения. В разделе 4.1 описаны информированные версии алгоритмов главы 3, а в разделе 4.2 показано, как может быть получена необходимая информация, относящаяся к конкретной задаче. В разделах 4.3 и 4.4 представлены алгоритмы, которые выполняют исключительно локальный поиск в пространстве состояний, оценивая и модифицируя одно или несколько текущих состояний вместо систематического исследования путей из начального состояния. Эти алгоритмы применимы для решения задач, в которых стоимость пути не представляет интереса и требуется лишь найти состояние, соответствующее решению. К этому семейству алгоритмов локального поиска относятся методы, созданные под влиянием исследований в области статистической физики (моделируемый отжиг) и эволюционной биологии (генетические алгоритмы). Наконец, в разделе 4.5 рассматривается поиск в оперативном режиме, в котором агент сталкивается с полностью неизвестным пространством состояний.