Упрощенный коммивояжёр в Прологе - PullRequest
Новая
       43

Упрощенный коммивояжёр в Прологе

9 голосов
/ 30 ноября 2011

Я просматривал подобные вопросы, но не могу найти ничего, что имеет отношение к моей проблеме. Я изо всех сил пытаюсь найти алгоритм или набор «петель», которые найдут путь от CityA до CityB, используя базу данных 

distance(City1,City2,Distance)

факты. То, что мне удалось сделать до сих пор, приведено ниже, но оно всегда возвращается на write(X),, а затем завершается с последней итерацией, что я и хочу, но только в определенной степени.

Например, я не хочу, чтобы он выводил названия городов, которые являются тупиками, или использовал последнюю итерацию. Я хочу, чтобы он в основном делал путь от CityA до CityB, записывая названия городов, по которым он идет по пути.

Надеюсь, кто-нибудь сможет мне помочь! 

all_possible_paths(CityA, CityB) :-
    write(CityA),
    nl,
    loop_process(CityA, CityB).

loop_process(CityA, CityB) :- 
    CityA == CityB.
loop_process(CityA, CityB) :-
    CityA \== CityB,
    distance(CityA, X, _),
    write(X),
    nl,
    loop_process(X, CityB).

Ответы [ 3 ]

7 голосов
/ 30 ноября 2011

Я пытался продемонстрировать, как вы можете добиться того, над чем работаете, чтобы лучше понять, как это работает. Так как ваш ОП не был очень полным, я взял на себя смелость! Вот факты, с которыми я работаю: 

road(birmingham,bristol, 9).
road(london,birmingham, 3).
road(london,bristol, 6).
road(london,plymouth, 5).
road(plymouth,london, 5).
road(portsmouth,london, 4).
road(portsmouth,plymouth, 8).

Вот предикат, который мы будем вызывать, чтобы найти наши пути, get_road / 4 . Он в основном вызывает рабочий предикат, который имеет два аккумулятора (один для уже посещенных точек и один для пройденного нами расстояния). 

get_road(Start, End, Visited, Result) :-
    get_road(Start, End, [Start], 0, Visited, Result).

Вот рабочий предикат,
get_road / 6 : get_road (+ Start, + End, + Waypoints, + DistanceAcc, -Visited, -TotalDistance):
Первый пункт говорит о том, что если между нашей первой точкой и нашей последней точкой есть дорога, мы можем закончить здесь. 

get_road(Start, End, Waypoints, DistanceAcc, Visited, TotalDistance) :-
    road(Start, End, Distance),
    reverse([End|Waypoints], Visited),
    TotalDistance is DistanceAcc + Distance.

Второе предложение говорит о том, что если между нашей первой точкой и промежуточной точкой есть дорога, мы можем взять ее и затем решить get_road (middle, end). 

get_road(Start, End, Waypoints, DistanceAcc, Visited, TotalDistance) :-
    road(Start, Waypoint, Distance),
    \+ member(Waypoint, Waypoints),
    NewDistanceAcc is DistanceAcc + Distance,
    get_road(Waypoint, End, [Waypoint|Waypoints], NewDistanceAcc, Visited, TotalDistance).

Использование выглядит следующим образом: 

?- get_road(portsmouth, plymouth, Visited, Distance).

И урожайность: 

Visited = [portsmouth, plymouth],
Distance = 8 ;
Visited = [portsmouth, london, plymouth],
Distance = 9 ;
Visited = [portsmouth, plymouth, london, plymouth],
Distance = 18 ;
false.

Надеюсь, это будет вам полезно.

4 голосов
/ 30 ноября 2011

Пожалуйста, отделите чистую часть от нечистой (I / O, как write/1, nl/0, но также (==)/2 и (\==)/2).Пока они полностью переплетаются с вашим чистым кодом, вы не можете ожидать многого.

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

Если этот путьбыть ациклическим или вы разрешаете циклы ?

Чтобы элемент X не присутствовал в списке Xs используйте цель maplist(dif(X),Xs). Вам не нужны никакие дополнительные вспомогательные средствапредикаты, чтобы сделать это хорошее отношение!

1 голос
/ 30 ноября 2011

Вы должны вернуть успешный список как переменную Out в all_possible_paths. Затем запишите этот список. Не делайте оба в одной и той же процедуре.

...