Логическое программирование на языке Visual Prolog. Солдатова О.П - 71 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

71
каждой фишки до ёё «целевой клетки» плюс утроенное значение «оценки
упорядоченности». Оценка упорядоченности определяет степень
упорядоченности фишек текущей позиции по отношению к целевой позиции
и высчитывается по следующим правилам:
• Фишка в центре имеет оценку 1;
• Фишка в другой позиции имеет оценку 0, если за ней в
направлении по часовой стрелке
следует соответствующий ей
преемник;
• Фишка в другой позиции имеет оценку 2, если за ней в
направлении по часовой стрелке не следует соответствующий ей
преемник.
Стратегия выбора следующей вершины в пространстве состояний –
минимальное значение оценочной функции.
Формулировка алгоритма:
1. Рассматриваем все варианты перемещения пустой фишки за один шаг и
выбираем вариант
с минимальной оценкой h(n).
2. Переходим в новое состояние.
3. Создаём вершины следующего уровня иерархии.
4. Выбираем состояние с минимальной оценкой h(n).
5. Повторяем до тех пор, пока не достигнем цели.
Цель не будет достигнута до тех пор, пока число перемещений меньше
числа фишек, находящихся не на своих местах.
Для задачи
, изображённой на рисунке, алгоритм находит решение за
два шага. От начальной вершины возможен переход в два состояния с
оценочной стоимостью f(1)=n+h(1)=1+4+3*(1+2)=14 и
f(2)=1+3+3*(1+2+2)=19. Выбираем минимальную стоимость и переходим в
состояние 1. Далее генерируем вершины 3 и 4 с оценочными стоимостями
соответственно f(3)=2+2+3*(1+2+2)=19 и f(4)=2+0=2. Последняя вершина
является целевой.
В соответствии с модифицированным алгоритмом оценочные
стоимости вершин на
первом шаге равны f(1)=n+h(1)=1+2=3 и f(2)=1+3=4
3.3 Сведение задачи к подзадачам и И/ИЛИ графы.
Для некоторых категорий задач более естественным решением
является разбиение задачи на подзадачи. Разбиение на подзадачи дает
преимущество в том случае, когда подзадачи взаимно независимы, и,
следовательно, решать их можно независимо друг от друга.
Проиллюстрируем это на примере решения
задачи поиска на карте дорог
маршрута между заданными городами как показано на рисунке.

Страницы