Prolog의 여행자 세일즈맨

Question

비슷한 질문을 검토했지만 내 문제와 관련이있는 것은 없습니다. 나는

distance(City1,City2,Distance) 

사실의 데이터베이스를 사용하여, CityA에서 CityB의 경로를 찾을 수 '루프'의 알고리즘 또는 세트를 찾기 위해 사투를 벌인거야. 지금까지 내가 해왔 던 일은 아래에 나와 있지만, 항상 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). 

Answer 1

나는 당신이 일하는 방식을 달성 할 수있는 방법을 보여줌으로써 어떻게 작동하는지 더 잘 이해할 수 있도록 노력했습니다. 그래서 당신의 작전이 아주 완전하지 않았기 때문에, 나는 자유를 택했습니다! 여기

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 우리의 경로를 찾기 위해 호출 술어입니다 : 여기에 내가 함께 일하고 있어요 사실이다. 기본적으로 두 개의 누적기를 가진 작업 술어를 호출합니다 (이미 방문한 점과 우리가 통과 한 거리를 하나씩). (+ 시작 + 엔드, + 웨이 포인트, + DistanceAcc, -Visited, -TotalDistance) get_road : 여기

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) :- 
    road(Start, End, Distance), 
    reverse([End|Waypoints], Visited), 
    TotalDistance is DistanceAcc + Distance. 

두 번째 절은 첫 번째 점과 중간 점 사이에 도로가있는 경우, 우리는 그것을 받아 다음 get_road (중간, 끝을) 해결할 수 있음을 알려줍니다.

?- 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. 

을 다음과 같이

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). 

사용이다.

Answer 2

당신은 all_possible_paths의 출력 변수로 성공적인 목록을 반환해야합니다. 그런 다음 그 목록을 작성하십시오. 동일한 절차에서 두 가지를 모두 수행하지 마십시오.

Answer 3

불순한에서 순수한 부분을 분리하십시오 (I/O, write/1, nl/0뿐만 아니라 (==)/2 및 (\==)/2 같은). 그것들이 당신의 순수한 코드와 완전히 인터레이스되는 한 많이 기대할 수는 없습니다.

아마도 출발점, 종점 및 중간 경로 사이의 관계가 필요합니다.

경로가 비순환 적이어야합니까? 또는주기 을 허용 하시겠습니까?

는 목표 maplist(dif(X),Xs). 를 사용하는 요소 X이 목록 Xs 발생하지 않도록하려면이 편안한 관계를 만들기 위해 더 보조 술어가 필요하지 않습니다!