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

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

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

L is J+1,

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

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

/* в позицию a(I, J) можно попасть при

/* условии, что там нет стены и мы

/* не побывали в ней прежде

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

отсутств_стена(I, J),

not (принадлежит (a (I, J), Были)).

Для того чтобы понять, каким образом процедура ищет путь к выходу, рассмотрим процесс согласования запроса с описанием лаби­ринта, описанного выше:

?-путь(а(4,2), Р, [а(4.2)]).

Выходом из лабиринта является позиция выход (3,1).

Выбор первого утверждения не приводит к согласованию целево­го утверждения, поскольку а (4,2) - не выход. Во втором утверждении делается попытка найти путь в северном направлении, т.е. согласовать целевое утверждение

путь(а(3, 2), Р2, [а(3, 2), а(4, 2)]).

Целевое утверждение не удается согласовать с первым утвержде­нием

путь(а(3, 2), Р2, [а(3, 2), а(4, 2)])

так как а (3,2) не является выходом. Во втором утверждении пред­принимается попытка найти путь, двигаясь на север, т.е. согласовать целевое утверждение

путь(а(2,2), РЗ, [а(2, 2), а(3, 2), а(4, 2)]).

Ни одно из утверждений не может согласовать

путь(а(2, 2), РЗ, [а(2, 2), а(3, 2), а(4, 2)]).

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

Неудача в согласовании

путь(а(2, 2), РЗ, [а(2, 2), а(3, 2), а(4, 2)])

заставляет Пролог-систему вернуться в ту точку, где было выбрано второе утверждение при попытке согласовать

путь(а(3, 2), Р2, [а(3, 2), а(4, 2)]).

Решение пересматривается и выбирается третье утверждение.

В третьем утверждении осуществляется попытка найти путь, двигаясь на юг, но она оказывается неудачной, поскольку мы уже по­бывали в позиции а (4, 2). Тогда, чтобы согласовать

путь(а(3, 2), Р2, [а(3, 2), а(4, 2)]),

выбирается четвертое утверждение. Мы успешно находим путь, дви­гаясь в западном направлении к позиции а(3,1), которая и является выходом. Рекурсия сворачивается, и в результате полу­чается путь

Р=[а(4, 2),а(3, 2), а(3,1)]

другие решения(да/нет)? да

Других решений нет

Альтернативный путь

[a(4,2), a(3,2), a(2,2), a(3,2), a(3,1)]

мы получить не можем, потому что не разрешается дважды бывать в одной и той же позиции.

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

Дата добавления: 2015-07-14