Отметим, что свойства этих алгоритмов существенно отличаются.

Алгоритм поиска в ширину отыскивает решение, путь к которому на графе — кратчайший, если таковое существует. Другими словами, он находит кратчайший путь между исходным состоянием и решением. Алгоритмы, обладающие таким свойством, называются разрешимыми (admissible).

Алгоритм поиска в глубину может быстрее найти решение, особенно, если при его выполнении используются эвристики для выбора очередной ветви. Но этот алгоритм может никогда не закончиться, если пространство состояний бесконечно.

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

В игровых программах также используется поиск в пространстве состояний, но стратегия поиска более избирательна, чем в случае прямого применения алгоритма generate-and-test. Кроме того, нужно принимать во внимание и то, что в игре, как правило, принимают участие две противоборствующие стороны. Были разработаны довольно неплохие программы для игры в шашки, нарды и шахматы. Созданные программы игры в шахматы нельзя отнести к классу систем, основанных на знаниях, а скорее к классу программ, обладающих способностью избирательно анализировать пространство состояний, что значительно повышает скорость и эффективность анализа. Методы и алгоритмы этого класса в данной книге рассматриваться не будут.

Другая задача, которая занимала умы исследователей в области искусственного интеллекта в середине 50-х годов, — доказательство теорем. Смысл задачи доказательства состоит в том, чтобы показать, как некоторое утверждение, которое требуется доказать (теорема), логически следует из декларированного множества других утверждений или аксиом (которые полагаются истинными или являются такими априори).

Комбинаторный взрыв

Исследованием вычислительной обозримости (или необозримости) проблем занимается теория сложности. Для начала нам потребуется только знать, что существуют классы проблем, решение которых требует ресурсов, экспоненциально возрастающих при линейном увеличении размерности задачи. Например, время, необходимое для отыскания пути в лабиринте, экспоненциально увеличивается при увеличении количества разветвлений в лабиринте. Аналогично, время, необходимое для поиска доказательства теоремы исчислением утверждений, растет экспоненциально по отношению к количеству переменных. Такие проблемы являются в общем случае необозримыми и называются NP-hard. Читателей, которые ими заинтересуются, мы отсылаем к специальной литературе, в частности книге Хопкрофта и Ульмана [Hopcroft and Ullman, 1979].

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

Прекрасное изложение теории вычислительной сложности, рассчитанное на читателя, несклонного к излишнему теоретизированию, можно найти в работе Паунд-стоуна [Poundstone, 1988, Chapter 9].

Рассмотрим такой пример. Пусть имеются две аксиомы, представленные на некотором формальном языке:

"Если компьютер может ошибаться, он ошибется" и

"Мой компьютер может ошибаться".