Я бы хотел найти кратчайший маршрут от станции A к станции B в прологе на двунаправленном графике (если A подключен к B, а B подключен к A), график не имеет весов на ветвях. Вопрос опубликован следующим образом
решить (начало, конец, путь).
Стартовая пусковая станция.
Станция конечного пункта назначения.
Путь-Список всех станций, пройденных по кратчайшему маршруту. Расстояние между любыми двумя напрямую связанными станциями на графике равно.
Факты в базе таковы:
факт ("Staion1", "metroline", "Station2", "metroline").
линия метро - это номер линии, которая соединяет две станции напрямую. Если 2-й и 4-й аргументы совпадают, станции подключаются напрямую.
строка («Abbesses», «12», «Pigalle», «12»).
линия («Abbesses», «12», «Lamarck Caulaincourt», «12»).
линия ("Ale'sia", "4", "Mouton Duvernet", "4").
линия ("Ale'sia", "4", "Porte d'Orle'ans", "4").
линия («Александр Дюма», «2», «Филипп Огюст», «2»).
линия («Александр Дюма», «2», «Аврон», «2»).
линия («Альма Марчесу», «9», «Иена», «9»).
EDIT:
Я попытался решить проблему и понял, что она будет работать быстрее, если использовать BFS.
вот решение, которое я написал:
решить (начало, конец, путь): - решить1 ([начало], конец, [начало], путь).
solve1 ([P | O], End, Visited, [End |?]): - дети (P, S), член (End, S),!.
решить1 ([P | O], конец, посещение, путь): -
(не (участник (P, посещение)), дети (P, S), добавить (O, S, O1), решить 1 (O1 , Конец, Посещенный, Путь));
(решить1 (О, Конец, Посещенный, Путь)).
? - должен быть список с путем к узлу назначения
Единственная проблема в том, что я не знаю, как вернуть путь к узлу назначения.
Спасибо вперед.