С++ - язык, подходящий как нельзя лучше разработчику систем искусст венного интеллекта, так как он обладает хорошо разработанными про> граммными элементами, обычно используемыми в подобных системах: ре. курсией, списками и стеками. Как известно, рекурсия на С++ выполняется легко и эффективно. Добавьте к этому возможности контейнеров библиотеки STL, и вы получите среду профаммирования, облегчающую разработку систем искусственного интеллекта.

Общее представление и терминология

Представим себе, что вы потеряли ключи от вашей машины. Вы знаете, что они где-то в доме, план которого показан на рис. 7.1.

Рис. 7.1. План дома, в котором ведется поиск ключей

Вы стоите перед входной дверью (на рис. 7.1 - позиция знака X) и начинаете искать ключи в гостиной. Затем вы пойдете по коридору в первую спальню, снова по коридору во вторую спальню, вернетесь в коридор и зайдете в главную спальню. Не найдя ключей, вы измените направление поиска, пройдя снова через гостиную. Наконец, ключи обнаружатся в кухне. Подобную ситуацию легко представить в виде фафа, показанного на рис. 7.2-Графическое представление задач поиска очень полезно, так как предлагает удобный способ изображения пути поиска решения. В табл. 7.1 приведены некоторые термины, используемые в данной главе. В примере с потерянными ключами каждая комната в доме - это узе- весь дом - пространство поиска, цель, как выяснилось, - кухня, а путЬ ведущий к решению, показан на рис. 7.2.

Таблица 7.1. Термины, применяющиеся при описании поиска решения задачи

(Название термина

Назначение термина

узел (Node)

Конечный узел (Terminal node)

Пространство (или область) поиска (Search space)

Цель (Goal)

Эвристика (Heuristics)

Отдельная точка

Узел, завершающий путь

Множество всех узлов

Узел - объект поиска

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

Путь, ведущий к решению (Solution path) Напра

л граф из узлов, которые

посещались по пути к цели

Начало поиска Гостиная

Спальня 1

Кухня

Коридор (Ключи

V найдены)

Главная спальня

Спальня 2

Рис. 7.2. Путь, ведущий к решению, при поиске потерянных ключей

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

Познакомившись с предыдущим примером, вы можете подумать, что искать решение легко - вы стартуете в начальной точке и движетесь к финалу. ° Крайне простом случае потери ключей это неплохой подход, так как про-анство поиска очень мало. Но у большинства задач (особенно таких, для Решения которых нам захочется использовать компьютер) количество узлов пространстве поиска велико, и по мере роста области поиска растет и Исло возможных путей, ведущих к цели. К несчастью, очень часто включе-**Ие еще одного узла в пространство поиска добавляет несколько новых путей.

248 Ойва7

ведущих к цели. Таким образом, при увеличении пространства поиска число возможных путей к цели часто растет нелинейно. При нелинейном росте ко-личество путей, ведущих к цели, может быстро стать очень большим.

Например, определим количество комбинаций трех объектов: А, В и с Возможны 6 следующих перестановок:

1 2 3 4 5 6 7

Рис. 7.3. Комбинаторный взрыв для фактори