mandist ( SI, S2, D)

где D — манхэттенское расстояние между клетками S1 и S2; оно измеряется как сумма расстояний между S1 и S2 в горизонтальном и вертикальном направлениях. Необходимо найти путь к решению минимальной длины. Поэтому определим стоимость всех дуг в пространстве состояний как равную 1. В программе, заданы также три примера начальных позиций, которые составлены по диаграммам, показанным на рис. 5.3. Рис. 5.3 Три начальные позиции для головоломки "игра е восемь":

а) требует. 4 хода; б) требует. 5 ходов; в) требует 18 ходов

Эвристическая функция h определяется в программе следующим образом:

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

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

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

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

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

ЗАДАНИЕ 4.5

Решите задачу о переливании для сосудов емкостью 10,7 и 3 л.

ЗАДАНИЕ 4.6

("Волк, коза и капуста"). Перевозчику нужно переправить через реку волка, козу и мешок с капустой. Лодка так мала, что кроме перевозчика может взять только один из этих объектов. Кроме того, капусту нельзя оставлять вместе с козой, а козу с волком. Как можно осуществить переправу?

Напишите программу для решения задачи "Волк, коза и капуста".

ЗАДАНИЕ 4.7

Решите одну из следующих задач, согласно порядковому номеру в группе:

1.(“Миссионеры и каннибалы”). Три миссионера и три каннибала находятся на левом берегу реки. Здесь же - лодка, вмещающая не более двух человек. Все хотят перебраться на другой берег. Если на каком-либо берегу каннибалов окажется больше, чем миссионеров, то каннибалы съедят оставшихся в меньшинстве миссионеров. Найти последовательность ездок, гарантирующих безопасную переправу на правый берег. Напишите программу для решения задачи "Миссионеры и каннибалы".

2. Решите задачу о "Миссионерах и каннибалах" для случая, когда только один миссионер и каннибал умеют грести.

3.(“Ревнивые мужья”). Три ревнивых мужа и их жены должны переправиться через реку. имеется только одна маленькая лодка, которая может выдержать одновременно только двоих. Как могут переправиться все шестеро, если никакой муж не оставит жену в присутствии других мужчин. Напишите программу для решения задачи "Ревнивые мужья".

4. Модифицируйте программу для случая пяти супружеских пар и лодки, вмещающей 3 человека.

5. (“Железнодорожная стрелка”). Два поезда с n и m вагонами смогут разминуться с помощью изображенной здесь стрелки и продолжить движение дальше вперед паровозами. Небольшой боковой тупик достаточен для того, чтобы принять либо один паровоз, либо

один вагон.

6. (“Солдаты в окопе”). На рисунке изображены 8 солдат и сержант в окопе. Сержант хочет перебраться на другой конец окопа, но так чтобы при этом все остальные солдаты остались на своих местах. Окоп слишком узок и вдвоем в нем не разойтись. (На рисунке в клеточках изображено начальное положение солдат и сержанта в окопе, а под клеточками – конечное.)

7. (“Анжелика”).

Передвигая фишки вдоль прямых на свободные места составить слово АНЖЕЛИКА.

8. (“Поссорившиеся пары”). Три супружеские пары должны перебраться через реку в маленькой лодке, которая может выдержать одновременно только двоих. Мистер С поссорился с двумя другими джентельменами, а миссис С перестала разговаривать с остальными леди. Как могут переправиться все шестеро, если ни одна из женщин не умеет грести и никакие два человека, находящихся в ссоре, не переправляются одновременно и даже не находятся одновременно на одном берегу.

9. (“Игра в пятнадцать”) На рисунке перед Вами знаменитая головоломка - игра в 15, в которой требовалось, передвигая фишки в коробке, расположить 14 и 15 в правильном порядке.

10. (“Четные и нечетные фишки”). Стопка из 8 фишек помещена в центральный квадрат, как показано на рисунке.

Фишки перенумерованы, таким образом, чтобы сверху вниз номера шли по порядку от 1 до 8. Требуется поместить фишки 1, 3, 5, 7 в квадрат с надписью НЕЧЕТ, а 2, 4, 6, 8 - в квадрат с надписью ЧЕТ. За один раз разрешается перемещать из квадрата в квадрат лишь одну фишку, причем больший номер нельзя класть на меньший, запрещается также помещать фишки с номерами разной четности одновременно в один и тот же квадрат.

11. (“Перемещение фишек”). Игральная доска разделена на 6 квадратов, как показано на рисунке.

В квадрате A помещена стопка из 15 фишек с номерами 1, 2, 3,..., 15, идущими сверху вниз. Надо поместить всю стопку в квадрат F. Перемещать можно по одной фишке за ход в любой квадрат, но больший номер нельзя класть на меньший.

12. (“Китайская головоломка”).Измените расположение слова РАСПОЛОЖЕНИЕ, буквы могут передвигаться только по двум желобам.

13. ("Упрощенный солитер") На игральной доске помещены 16 пронумерованных фишек, как показано на рисунке.

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