Пролог - поиск всех вариантов пути

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

Вот что у меня есть на данный момент:

findAllRoutes(Start, End, Path) :-
     findAllRoutes(Start, _, End, Path),
     print('Successful route: '), print(Route).

findAllRoutes(End, _, End, [End]). %route was successfully finished

 findAllRoutes(Start, Temp, End, [Start|Rest_of_List]) :-
     path(Start, Temp),
     findAllRoutes(Temp, _, End, Rest).

Вот данные для чтения:

%path(Start, End).
path(1, 4). %find all the possible paths from location 1 to location 4.

%paths_in_place[[Start, End, Distance]].
paths_in_place[[1, 2, 250], [2, 4, 250], [1, 3, 400], [3, 4, 300]].

Мой вопрос: является ли это точным способом циклического перехода через paths_in_place, сохраняя при этом порядок точек, достигнутых на пути от начальной точки до конечной точки?

Кроме того, что происходит с Distance, когда findAllRoutes вызывается без какого-либо упоминания поля Distance? Законно ли в Прологе передавать параметры Start, End, Route, даже если в paths_in_place поля равны Start, End, Distance?

Любая помощь очень ценится. Дайте мне знать, если мне нужно что-то уточнить.


parameter-passing path-finding prolog
person user1462294    schedule 26.10.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Данные пролога являются символическими. Вы можете пройти расстояние в метрах и рассматривать его как расстояние в футах. Вот так одна из марсианских миссий потерпела крах, хотя они использовали другой язык. Так что все зависит от вас.

Что касается вашего кода,

findAllRoutes(Start, End, Path) :-
     findAllRoutes(Start, _, End, Path),
     print('Successful route: '), print(Route).

Route? Что Route? Это неустановленная переменная-одиночка. SWI Prolog предупреждает нас об этом. Возможно, вы имели в виду Path.

findAllRoutes(End, _, End, [End]).  % route was successfully finished

findAllRoutes(Start, Temp, End, [Start|Rest_of_List]) :-
     path(Start, Temp),
     findAllRoutes(Temp, _, End, Rest).

опять же, Rest_of_List и Rest, вероятно, должны иметь одно и то же имя (быть одной и той же логической переменной).

В противном случае он выглядит нормально, за исключением своего имени: он находит один путь, а не «AllRoutes», при каждом вызове / возврате. Название «AllRoutes» предполагает, что он находит их все и возвращает их все в своем аргументе результата; это не.

Затем идут ваши данные, и они не синхронизируются с вашим кодом:

%path(Start, End).
path(1, 4). %find all the possible paths from location 1 to location 4.

%paths_in_place[[Start, End, Distance]].
paths_in_place([[1, 2, 250], [2, 4, 250], [1, 3, 400], [3, 4, 300]]).
  % ! must be in parentheses !

Ваш path(Start, Temp) вызов в вашем коде предполагает, что Temp является непосредственным преемником Start. По этим данным, это не так. Плюс отсутствует определение path/2. Но вы можете просто иметь набор фактов вместо списка для определения данных.

person Will Ness    schedule 26.10.2013