Головоломка "Восьмерка"

В отличие от задачи о миссионерах и каннибалах, эту головоломку можно решить за приемлемое время методом "слепого" поиска. Дело в том, что головоломка имеет только 9! состояний и, следовательно, можно использовать для поиска очередного хода оценочную функцию по методике "восхождения на гору".

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

II) Какая из предложенных выше оценочных функций является более чувствительной? Можете ли вы предложить лучший способ управления поиском?

III) Как будет работать ваша программа, если увеличить количество фишек до 15, а размер игрового поля до 4x4? В этом случае придется исследовать 16! состояний.

Эту головоломку с точки зрения методов искусственного интеллекта рассматривал Нильсон (см. [Nilsson, 1980, Chapter 1].

8. Просмотрите описание алгоритма А во врезке 2.2 и выполните следующее.

I) Реализуйте алгоритм А на любом известном вам языке программирования.

II) С помощью созданной программы попробуйте решить головоломки "о миссионерах и каннибалах" и "Восьмерку". (Придется придумать оценочную функцию для головоломки "о миссионерах и каннибалах". Воспользуйтесь оценочной функцией из упр. 7.)

III) Попробуйте с помощью этого алгоритма решить криптоарифметическую головоломку, описанную ниже:


BEST	SEND	DONALD	CROSS
+MADE	+MORE	+GERALD	+ROADS
MASTER	MONEY	ROBERT	DANGER

Термин "криптоарифметическая" означает использование цифр, зашифрованных буквами, и соответственно чисел, зашифрованных словами. Задача состоит в том, чтобы найти, какие цифры нужно подставить вместо букв, чтобы представленные арифметические операции над расшифрованными числами давали верный результат. Такая задача рассматривается во многих классических работах по искусственному интеллекту (см., например, [Raphael, 1976, Chapter 3].

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

Содержание раздела