Лекция: H( Роs, H)

где Pos — позиция на доске, Н — сочетание двух описанных ниже критериев;

1. totdist — суммарное расстояние восьми фишек в позиции Pos от клеток, в которых должны находиться фишки в целевом состоянии. Например, в начальной позиции головоломки, приведенной на рисунке а), totdist = 4.

2. seq — оценка упорядоченности, определяющая ту степень, в какой фишки, стоящие в текущей позиции, уже упорядочены по отношению к той последовательности, которая должна быть достигнута в целевой конфигурации. Значение seq вычисляется как сумма оценок для каждой фишки в соответствии со следующими правилами:

• фишка в центре имеет оценку 1;

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

•если за фишкой не следует соответствующий ей преемник, то такая фишка имеет оценку 2.

Например, для начальной позиции головоломки, приведенной на рис.5.3 а) seq = 6.

Эвристическая оценка, Н, вычисляется как H = totdist + 3 * seq.

Эта эвристическая функция действует успешно в том смысле, что очень эффективно направляет поиск к цели. Например, при решении задач, показанных на рис. 5.3 а), б), не происходило даже развертывание ни одного узла, выходящего за пределы кратчайшего пути решения, до того, как было найдено первое решение. Это означает, что в таких случаях кратчайшие пути решения отыскиваются непосредственно, без какого-либо перебора с возвратами. Почти сразу же решается даже трудная задача, приведенная на рис.5.3 в). Но недостаток этой эвристики состоит в том, что она не является допустимой: она не гарантирует, что кратчайший путь решения всегда будет найден до обнаружения какого-либо более длинного решения. Дело в том, что данная функция h не удовлетворяет условию допустимости, при котором h < h* для всех узлов. Например, для начальной позиции, приведенной на рис. 5.3 а), имеет место следующее:

h = <4 + 3*6 = 2 2, h* = 4

С другой стороны, допустимым является отдельно взятый критерий «суммарного расстояния», поскольку для всех позиций имеет место следующее:

totdist < h*

Допустимость этого отношения можно легко проверить с помощью таких рассуждений: если условия этой головоломки будут упрощены таким образом, что фишки можно будет переносить друг над другом, то каждая фишка сможет переходить к своей исходной клетке по траектории, длина которой точно равна манхэттенскому расстоянию между начальной клеткой фишки и ее исходной клеткой. Поэтому оптимальное решение в упрощенной головоломке будет точно равно длине totdist. Но в первоначальном варианте задачи фишки могут мешать друг другу и одна из них может находиться на пути другой, что препятствует движению фишек по кратчайшим траекториям, а это гарантирует, что длина оптимального решения равна или больше чем totdist .

 

ЗАДАНИЕ 4.3

Построить граф пространства состояний для задачи переупорядочевания кубиков, поставленных друг на друга, как показано на рисунке.

Начальная Конечная

ситуация ситуация

 

На каждом шагу разрешается переставлять только один кубик. Кубик можно взять только, если он лежит сверху. Кубик можно поставить либо на стол, либо на другой кубик. Напишите программу переупорядочивания кубиков.

еще рефераты
Еще работы по информатике