Иллюстрированный самоучитель по введению в экспертные системы



              

Упражнения - часть 3


С разными способами формализации этой

задачи можно познакомиться в работе Амарела [Amarel, 1968]. Обратите внимание на то, что существуют способы представления состояний, которые позволяют более экономно использовать вычислительные ресурсы при решении задачи.

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

III) Обобщите программу как в части количества пассажиров в лодке, так и в части количества миссионеров/каннибалов. Сделайте их параметрами программы, задаваемыми извне. Если вы начнете проводить эксперименты с такой программой, то убедитесь, что, во-первых, эти параметры нельзя варьировать независимо, поскольку при некоторых комбинациях задача не имеет решения, а во-вторых, увеличение значений любого из параметров существенно расширяет пространство поиска.

7. Другая классическая головоломка, знакомая в несколько ином виде многим еще со школьной скамьи, — "Восьмерка". В головоломке принимает участие восемь пронумерованных фишек, которые могут перемещаться по игровому полю 3x3. Цель состоит в том, чтобы из некоторого случайного расположения фишек перейти к упорядоченному (рис. 2.9).

Мы несколько модифицируем ограничения, сформулировав их в терминах перемещения единственного "пустого поля".

Рис. 2.9. Головоломка "Восьмерка"

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

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



Содержание  Назад  Вперед