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

Я просмотрел похожие вопросы, но не могу найти ничего, что имело бы отношение к моей проблеме. Я изо всех сил пытаюсь найти алгоритм или набор «циклов», которые найдут путь от 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).

backtracking traveling-salesman prolog prolog-dif
person g.a.kilby    schedule 29.11.2011    source источник

Ответы (3)


arrow_upward
8
arrow_downward

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

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(intermediate, 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.

Я надеюсь, что это будет полезно для вас.

person m09    schedule 29.11.2011
comment
Вы, сэр, превзошли зов долга! Это невероятно, это прекрасно, и это действительно имеет смысл! Извините, я такой болван, я действительно новичок в прологе, и хотя многое из этого пришло очень естественно, я действительно боролся с этой задачей. Спасибо вам огромное так ооооочень большое :] - person g.a.kilby; 30.11.2011
comment
не стесняйтесь задавать дополнительные вопросы, если вам снова будет сложно понять этот код, я или другие отвечу на них в комментариях :) - person m09; 30.11.2011
comment
@ m09 Мне очень понравился ваш подход к этой проблеме, но я хотел знать, как бы вы справились с ней, если бы вместо начальной и конечной точек продавец должен был пройти через набор городов внутри полного набора городов и вернуться в место, где он начал. - person nunojmb99; 30.11.2020

arrow_upward
4
arrow_downward

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

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

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

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

person false    schedule 29.11.2011
comment
После того, как город был использован, его нельзя использовать снова на том же пути. Итак, ациклический. Кроме того, что вы подразумеваете под чистым и нечистым? - person g.a.kilby; 30.11.2011
comment
Я добавил объяснение выше. - person false; 30.11.2011

arrow_upward
1
arrow_downward

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

person projectshave    schedule 29.11.2011