Назад | Содержание| Вперёд 2. 5. Пример: обезьяна и банан Задача ...

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

2. 5. Пример: обезьяна и банан

Задача об обезьяне и банане часто используетсяв качестве простого примера задачи из областиискуственного интеллекта. Наша пролог-программа,способная ее решить, показывает, как механизмысопоставления и автоматических возвратов могутприменяться для подобных целей. Мы сначаласоставим программу, не принимая во вниманиепроцедурную семантику, а затем детально изучимее процедурное поведение. Программа будеткомпактной и наглядной.

Рассмотрим следующий вариант данной задачи.Возле двери комнаты стоит обезьяна. В серединеэтой комнаты к потолку подвешен банан. Обезьянаголодна и хочет съесть банан, однако она не можетдотянуться до него, находясь на полу. Около окнаэтой же комнаты на полу лежит ящик, которымобезьяна может воспользоваться. Обезьяна можетпредпринимать следующие действия: ходить пополу, залезать на ящик, двигать ящик (если она уженаходится около него) и схватить банан, если онастоит на ящике прямо под бананом. Может лиобезьяна добраться до банана?

Одна из важных проблем при программированиисостоит в выборе (адекватного) представлениярешаемой задачи в терминах понятийиспользуемого языка программирования. В нашемслучае мы можем считать, что "обезьяний мир"всегда находится в некотором состоянии, ионо может изменяться со временем. Текущеесостояние определяется взаиморасположениемобъектов. Например, исходное состояние мираопределяется так:

(1) Обезьяна у двери.

(2) Обезьяна на полу.

(3) Ящик у окна.

(4) Обезьяна не имеетбанана.

Удобно объединить все эти четыреинформационных фрагмента в один структурныйобъект. Давайте в качестве такого объединяющегофунктора выберем слово "состояние". На рис.2.12 в виде структурного объекта изображеноисходное состояние.

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

состояние( -,-, -, имеет)

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

(1) схватить банан,

(2) залезть на ящик,

(3) подвинуть ящик,

(4) перейти в другое место.

Рис. 2. 15. Поиск бананаобезьяной. Перебор начинается в верхнем узле ираспространяется вниз, как показано.Альтернативные ходы перебираются слева направо.Возврат произошел только один раз.

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

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

Оглавление