Процедуры для головоломки
Рисунок 12. 6. Процедуры для головоломки "игра в восемь",
предназначенные для использования программой поиска
с предпочтением Рисунок 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: расстояния по горизонтали и расстояния по вертикали.
