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




Поиск c предпочтением применительно к головоломке "игра в восемь" - часть 6


В программе она задается списком текущих положений фишек. Каждое положение определяется парой координат X/Y. Элементы списка располагаются в следующем порядке:

(1)        текущее положение пустой клетки,

(2)        текущее положение фишки 1,

(3)        текущее положение фишки 2,

...

Целевая ситуация (см. рис. 11.3) определяется при помощи предложения

        цель( [2/2, 1/3, 2/3, 3/3, 3/2, 3/1, 2/1, 1/1, 1/2] ).

Имеется вспомогательное отношение

        расст( K1, K2, Р)

Р - это "манхеттеновское расстояние" между клетками Kl и K2, равное сумме двух расстояний между Kl и K2: расстояния по горизонтали и расстояния по вертикали.

fig12_7.gif (1512 bytes)

Рис. 12. 7.  Три стартовых позиции для "игры в восемь":  (а)   решение требует
4 шага; (b)  решение требует 5 шагов;  (с)   решение требует 18 шагов.

Наша задача - минимизировать длину решения, поэтому мы положим стоимости всех дуг пространства состояний равными 1. В программе рис. 12. 6. даны также определения трех начальных позиций (см. рис. 12.7).

Эвристическая функция  h,   запрограммирована как отношение

        h( Поз, Н)

Поз - позиция на доске; Н вычисляется как комбинация из двух оценок:

(1)        сумрасст - "суммарное расстояние" восьми фишек, находящихся в позиции Поз, от их положений в целевой позиции. Например, для начальной позиции, показанной на рис. 12.7(а), сумрасст = 4.

(2)        упоряд - степень упорядоченности фишек в текущей позиции по отношению к тому порядку, в котором они должны находиться в целевой позиции. Величина упоряд вычисляется как сумма очков, приписываемых фишкам, согласно следующим правилам:

  • фишка в центральной позиции - 1 очко;
  • фишка не в центральной позиции, и непосредственно за ней следует (по часовой стрелке) та фишка, какая и должна за ней следовать в целевой позиции - 0 очков.
  • то же самое, но за фишкой следует "не та" фишка - 2 очка.

Например, для начальной позиции рис.12.7(а),



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