Самостоятельная работа По предмету: искусственный интеллект

Рис. 11.1. Задача перестановки кубиков.
Ясно, что альтернативу "поставить С на стол" не имело смысла рассматривать всерьез, так как этот ход никак не влияет на ситуацию.
Как показывает рассмотренный пример, с задачами такого рода связано два типа понятий:
(1) Проблемные ситуации.
(2) Разрешенные ходы или действия, преобразующие одни проблемные ситуации в другие.
Проблемные ситуации вместе с возможными ходами образуют направленный граф, называемый пространством состояний. Пространство состояний для только что рассмотренного примера дано на рис. 11.2. Вершины графа соответствуют проблемным ситуациям, дуги — разрешенным переходам из одних состояний в другие. Задача отыскания плана решения задачи эквивалентна задаче построения пути между заданной начальной ситуацией ("стартовой" вершиной) и некоторой указанной заранее конечной ситуацией, называемой также целевой вершиной.
На рис. 11.3 показан еще один пример задачи: головоломка "игра в восемь" в ее представление в виде задачи поиска пути. В головоломке используется восемь перемещаемых фишек, пронумерованных цифрами от 1 до 8. Фишки располагаются в девяти ячейках, образующих матрицу 3 на 3. Одна из ячеек всегда пуста, и любая смежная с ней фишка может быть передвинута в эту пустую ячейку. Можно сказать и по-другому, что пустой ячейке разрешается перемещаться, меняясь местами с любой из смежных с ней фишек. Конечная ситуация — это некоторая заранее заданная конфигурация фишек, как показано на рис. 11.3.

Рис. 11.2. Графическое представление задачи манипулирования кубиками. Выделенный путь является решением задачи рис. 11.1.
Нетрудно построить аналогичное представление в виде графа и для других популярных головоломок. Наиболее очевидные примеры — это задача о "ханойской башне" и задача о перевозке через реку волка, козы и капусты. Во второй из этих задач предполагается, что вместе с человекам в лодке помещается только один объект и что человеку приходится охранять козу от волка и капусту от козы. С описанной парадигмой согласуются также многие задачи, имеющие практическое значение. Среди них — задача о коммивояжере, которая может служить моделью для многих практических оптимизационных задач. В задаче дается карта с n городами в указываются расстояния, которые надо преодолеть по дорогам при переезде из города в город. Необходимо найти маршрут, начинающийся в некотором городе, проходящий через все города и заканчивающиеся в том же городе. Ни один город, за исключением начального, не разрешается посещать дважды.