Проектирование систем искусственного интеллекта



         

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


?-путь(а(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)]

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

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




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