유향 그래프의 최단 경로 인쇄

가중치가없는 지시 된 순환 그래프가 있습니다. A와 B 사이의 최단 경로 (즉, 최소 홉을 가진 경로)를 찾고 싶습니다. 발견 한 모든 경로에 대해 한 번,유향 그래프의 최단 경로 인쇄

path(A,B) :- walk(A,B,[]). 

walk(A,B,V) :- edge(A,X), not(member(X,V)), (B=X); walk(X,B,[A|V]). 

edge(a, b). 
edge(b, c). 
edge(a, d). 
edge(c, a).

이 코드 인쇄 진실 :

이

내가 지금까지 가지고 코드입니다. 어떻게 경로를 인쇄 할 수 있습니까? 최소한의 홉으로 경로를 찾으려면 어떻게해야합니까?

출처

2016-09-29 user2393256

당신은 당신이 당신의 종료 조건에 도달하면 당신은 V에 축적 한 것과 추가 인수를 통합해야합니다

path(A,B,P) :- walk(A,B,[],P). 

walk(B,B,V,P) :- reverse(V,P). 
walk(A,B,V,P) :- dif(A,B), edge(A,X), maplist(dif(X),V), walk(X,B,[A|V],P).

A 번과 B가 동일을, 우리가 걸을 필요가 없습니다 것을 의미합니다 더 이상 그래프. 이 경우 V에 누적 된 경로를 P으로 바꿔 path/3에서 "returned"됩니다.

참고 : ; 대신에 별도의 규칙으로 재귀 종료를 확인하는 코드를 넣는 것이 거의 항상 명확합니다.

은 최소 홉 경로를 찾으려면, 당신은 당신이 원하는 두 지점에서 모든 경로를 찾은 다음 가장 작은 취할 수 있습니다

shortest_path(A,B,S) :- 
    findall(P, path(A,B,P), Ps), 
    maplist(prepend_length, Ps, Ls), 
    sort(Ls, [[_,S]|_]). 

prepend_length(P, [L,P]) :- 
    length(P,L).

출처

2016-09-29 14:06:38 Fatalize

's의 (X)를'DIF/2''에 대한 ! '\ + member ... '대신'maplist (dif (X), V)'를 사용하면 훨씬 더 일반적입니다! 그리고 : 가장 짧은 홉 * 첫 번째 경로를 찾으려면,''- length (Ps, _), path (A, B, Ps) '' – mat

@mat '길이/2'를 가진 당신의 솔루션은 작동하지 않습니다. 실제로 존재하는 경로가없는 경우. 비록 하나가 있다면 그것은 더 빠르고 더 적은 메모리를 필요로합니다. 그것은 상처를 필요로 할 것이다. – Fatalize

네, 맞습니다.하지만 잘라내기를 요구하지는 않습니다. 실제로, 상처를 추가하면 가장 짧은 대안을 잘못 잘라 버릴 수 있습니다. 실제로 하나의 솔루션 만 필요하면 쿼리를 게시 할 때'once/1'을 사용하십시오. 그러나 불필요하게 술어를 특수화하지 마십시오. – mat

경로를 생성하려면 추적을 유지하기 위해 인수를 추가해야합니다. 예를 들면 :

이

path(A,B,P) :- walk(A,B,[],P). 
walk(A,B,V,[A,B]) :- edge(A,X), not(member(X,V)), (B=X).

(. 내가 운동으로 재귀 사건을 떠날거야)

가 최단 경로를 찾으려면, 당신은 그들이 모두 (findall) & 짧은을 골라 찾을 수 있습니다.

출처

2016-09-29 14:02:16

유향 그래프의 최단 경로 인쇄

답변

관련 문제