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



              

Процедуры для головоломки "игра в восемь",



  Процедуры для головоломки "игра в восемь",


предназначенные для использования программой поиска
с предпочтением рис. 12.3.

Существуют три отношения, отражающих специфику конкретной задачи:

        после( Верш, Верш1, Ст)

Это отношение истинно, когда в пространстве состояний существует дуга стоимостью Ст между вершинами Верш и Верш1.

        цель( Верш)

Это отношение истинно, если Верш - целевая вершина.

        h( Верш, Н)

Здесь Н - эвристическая оценка стоимости самого дешевого пути из вершины Верш в целевую вершину.

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

Отношения для "игры в восемь" показаны на рис. 12.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: расстояния по горизонтали и расстояния по вертикали.









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