Самый быстрый путь между двумя городами

Question

Мне нужно найти самый быстрый способ путешествовать из одного города в другой. У меня есть что-то вроде

way(madrid, barcelona, 4). 
way(barcelona, paris, 5). 
way(madrid, londres, 3). 
way(londres,paris,1). 

я пришел с предикативного shortway (A, B, C, D), где C список городов между А и В и D расстояние.

поэтому у меня есть

shortway(A,B,C,D):- 
    way(A,B,_,_) , (A,_,C,D). D<C. 
    shortway(A,_,C). 

Я стараюсь изо всех сил, но я действительно не могу заставить его работать!

Answer 1

У вас возникли проблемы с кодом! Прежде всего, way/3 имеет arity 3, а не 4, поэтому вызов way(A,B,_,_,) явно не собирается делать то, что вы думаете. Во-вторых, я понятия не имею, что вы пытаетесь сделать с (A,_,C,D). Период после этого означает конец предиката! Итак, следующая строка, D<C. - это просто свободный запрос, который не может быть выполнен. И тогда shortway(A,_,C) в основном является фактом, с тремя синглтонами, но он будет определять предложение shortway/3, когда предыдущий является предложением shortway/4.

На самом деле этого недостаточно, чтобы найти правильный путь здесь, чтобы попытаться восстановиться. Похоже, вы очень смущены даже основами Пролога. Я настоятельно призываю вас вернуться к началу и начать все заново. Вы не можете спешить с Прологом! И этот код выглядит так, будто вы пытаетесь сделать двигатель внутреннего сгорания, собирая камни вместе.

Answer 2

Я написал несколько строк кода, которые помогут вам, но, как сказал https://stackoverflow.com/users/812818/daniel-lyons, это лучше, чем вы раньше узнали.

Чтобы решить вашу проблему, я советую вам прочитать, по крайней мере, первые 3 главы этой книги: http://www.learnprolognow.org/lpnpage.php?pageid=online и выполните практическую сессию в пункте 3.4.

Тогда вы могли бы взглянуть на мой код (вы можете найти некоторые explenation его здесь:. Out of local stack error in Prolog route planner

Вот код

way(madrid, barcelona, 4). 
way(barcelona, paris, 5). 
way(madrid, londres, 3). 
way(londres,paris,1). 


shortway(From, To):- findall(Journey, travel(From, To, Journey, _) , Travels_list), 
        findall(Total_distance, travel(From, To, _, Total_distance) , Distances_list), 
        min_member(Y, Distances_list), find_minimum_index(Y, Distance_list, 1, Distance_index), 
        find_journey(Distance_index, Travels_list, 0, Shortest_path), 
        format('The shortest path is ~w', [Shortest_path]). 


travel(From, To, Journey, Total_distance) :- dif(From, To), 
              AccDistance is 0, 
              path(From, To, [From], Journey, AccDistance, Total_distance). 


path(From, To, Passed_cities, go(From, To), AccDistance, Total_distance) :- way(From, To, Way_distance),                   
                      Total_distance is AccDistance + Way_distance. 


path(From, To, Passed_cities, go(From, Intermediate, GO), AccDistance, Total_distance) :- way(From, Intermediate, Way_distance), 
                  dif(Intermediate, To), 
                  \+  member(Intermediate, Passed_cities), 
                  NewAccDistance is AccDistance + Way_distance, 
                  path(Intermediate, To, [Intermediate|Passed_cities], GO, NewAccDistance, Total_distance). 


min_member(Min, [H|T]) :- min_member_(T, H, Min). 
min_member_([], Min, Min). 
min_member_([H|T], Min0, Min) :- 
          ( H >= Min0 
          -> min_member_(T, Min0, Min) 
          ; min_member_(T, H, Min) 
          ). 

find_minimum_index(X, [], N, I) :- fail. 
find_minimum_index(X, [X|T], N, I) :- I is N, !. 
find_minimum_index(X, [H|T], N, I) :- H \= X, increment(N, N1), find_minimum_index(X, T, N1, I). 

find_journey(I, [H|T], N, Elemento) :- N = I, Elemento = H, !. 
find_journey(I, [H|T], N, Elemento) :- N \= I, increment(N, N1), find_journey(I, T, N1, Elemento). 

increment(X, X1) :- X1 is X+1. 

Затем вы вызываете, например

?: - короткий (мадрид, париж).

и он вернется

"The shortest path is go(madrid, londres, go(londres,paris))" 

который расстояние, 4 , а не

go(madrid, barcelona, go(barcelona, madrid) 

который расстояние 9.

Резюмируя: вызов shortway/2, с предикатами FindAll/3 вы обнаружите, списки всех возможных патчей и их относительные расстояния соответственно, то вы просмотрите список расстояний, чтобы найти индекс минимального элемента, и, таким образом, используя его, чтобы найти кратчайший путь из списка всех найденных ранее патчей.