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



              

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


Таким образом, дозволены следующие варианты шагов (переправ):

К-> одного каннибала с левого берега на правый

КК-> двух каннибалов с левого берега на правый

МК-> одного миссионера и одного каннибала с левого берега на правый

ММ-> двух миссионеров с левого берега на правый

М-> одного миссионера с левого берега на правый

К этому нужно добавить такие же варианты переправы с правого берега на левый. Но есть еще одно обстоятельство, существенно влияющее на весь процесс: если окажется, что каннибалов на любом из берегов больше, чем миссионеров, то несчастных просто съедят. Решение головоломки — это последовательность шагов с учетом описанных ограничений, переводящая систему в заданное конечное состояние.

Конечно, эту головоломку можно решить и простым перебором и испытанием всех возможных состояний, поскольку пространство поиска не так уж велико. На рис. 2.7 показано, как образуется пространство поиска рекурсивным применением дозволенных операторов, причем на графе состояний особо выделены узлы, приводящие к образованию петель, и узлы, соответствующие недозволенным состояниям (когда кто-либо из миссионеров обречен).

Рис. 2.7. Построение пространства поиска в головоломке "миссионеры и каннибалы"

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

Рис. 2.8. Законченное пространство поиска в головоломке "миссионеры и каннибалы ", сформированное алгоритмом поиска в глубину

В процессе поиска было развернуто 22 узла, а путь, приводящий к успеху, содержит 11 узлов. Таким образом, оценка проницательности поиска равна 11/22=0.5. Грубо говоря, проницательность поиска говорит нам о том, насколько данный алгоритм позволил избежать выполнения ненужной работы в процессе Поиска решения. Чем выше значение проницательности поиска для того или иного алгоритма, тем лучше.

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


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