Основы проектирования систем искусственного интеллекта



         

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


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

стена(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], Были) :-




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