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


         

Для того чтобы понять, каким


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)]
мы получить не можем, потому что не разрешается дважды бывать в одной и той же позиции.
Описанная процедура не обязательно находит кратчайший путь к выходу. Кратчайший путь можно найти, генерируя альтернативные пути с помощью вызова состояния неудачи и запоминая кратчайший из них.

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