Программирование на языке Пролог для искусственного интеллекта




Предварительные понятия и примеры - часть 2


Одна из ячеек

fig11_2.gif (3837 bytes)

Рис. 11. 2.  Графическое представление задачи манипулирования

кубиками. Выделенный путь является решением задачи рис. 11.1.

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

Нетрудно построить аналогичное представление в виде графа и для других популярных головоломок. Наиболее очевидные примеры - это задача о "ханойской башне" и задача о перевозке через реку волка, козы и капусты. Во второй из этих задач предполагается, что вместе с человекам в лодке помещается только один объект и что человеку приходится охра-

fig11_3.gif (4054 bytes)

Рис. 11. 3.  "Игра в восемь" и ее представление в форме графа.

нять козу от волка и капусту от козы. С описанной парадигмой согласуются также многие задачи, имеющие практическое значение. Среди них - задача о коммивояжере, которая может служить моделью для многих практических оптимизационных задач. В задаче дается карта с n городами в указываются расстояния, которые надо преодолеть по дорогам при переезде из города в город. Необходимо найти маршрут, начинающийся в некотором городе, проходящий через все города и заканчивающиеся в том же городе. Ни один город, за исключением начального, не разрешается посещать дважды.

Давайте подытожим те понятия, которые мы ввели, рассматривая примеры. Пространство состояний некоторой задачи определяет "правила игры": вершины пространства состояния соответствуют ситуациям, а дуги - разрешенным ходам или действиям, или шагам решения задачи. Конкретная задача определяется

  • пространством состояний
  • стартовой вершиной
  • целевым условием (т.е. условием, к достижению которого следует стремиться); "целевые вершины" - это вершины, удовлетворяющие этим условиям.
  • Каждому разрешенному ходу или действию можно приписать его стоимость.


    Содержание  Назад  Вперед