Философские аспекты проблемы систем ИИ



         

Пример: задача поиска пути в лабиринте


В качестве примера использования механизма возврата напишем процедуру для поиска пути в лабиринте. Лабиринт представлен фактами вида:

стена(I, J) для позиции в I-м ряду и J-й колонке, где есть стена

отсутств_стена(I, J) для позиции в I-м ряду и J-й колонке, где нет стены

выход (I, J) для позиции в 1-м ряду и J-й колонке, являющейся выходом

Рассмотрим небольшой лабиринт:

Стена

Стена

Стена

Стена

Стена

Стена

Стена

Стена

Стена

Выход

Стена

Стена

Стена

Стена

Стена

Стена

Стена

Последний ряд лабиринта описывается фактами:

стена(4,1).

стена(4,3).

стена(4,4).

отсутств_стена(4,2).

Если задана исходная позиция, путь к выходу можно найти следующим образом.

Граничное условие:

Если исходная позиция является выходом, то путь найден.

Рекурсивные условия:

Ищем путь из исходной позиции в северном направлении. Если пути нет, идем на юг. Если пути нет, идем на запад. Если нельзя, идем на восток. Если соседняя позиция на севере (юге, западе, востоке) является стеной, то нет смысла искать путь из начальной позиции к выходу. Чтобы не ходить кругами, будем вести список позиций, в которых мы побывали.

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

/* Терм a(I, J) представляет позицию в

/* I-м ряду и J-й колонке.

/* Нашли путь ?

путь(а(I, J),[а(I, J)], Были) :- выход(I, J).

/* Пытаемся идти на север

путь(а(I, J),[а(I, J) | Р], Были) :-

К is I-1,

можем_идти(a (K, J), Были),

путь(а(I, J) ,Р, [a(K, J) | Были]).

/* Пытаемся идти на юг

путь(а(I, J),[а(I, J) | Р], Были) :-

К is I+1,

можем_идти(a (K, J), Были),

путь(а(I, J) ,Р, [a(K, J) | Были]).

/* Пытаемся идти на запад

путь(а (I, J), [a (I, J) | P], Были) :-

L is J-1,

можем_идти(а(I, L), Были),

путь(а(I, L), Р, [а(I, L)| Были]).

/* Пытаемся идти на восток

путь(а (I, J), [a (I, J) | P], Были) :-




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