Prolog - поиск всех вариантов пути

Question

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

Вот то, что я до сих пор:

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? Является ли законным в Prolog передавать параметры Start, End, Route, хотя в paths_in_place поля Start, End, Distance?

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

Answer 1

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

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

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

Route? Что Route? Это неосвещенная переменная «singleton». 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 отсутствует. Но вы можете просто иметь кучу фактов вместо списка, чтобы определить данные.