그래프에서 '긴'단순한 비순환 경로를 모두 찾는 방법은 무엇입니까?

Question

완전 연결된 방향 그래프 G이 있다고 가정 해 봅시다. 정점은 [a,b,c]입니다. 각 꼭지점 사이에는 양방향으로 가장자리가 있습니다.

시작점이 a 인 경우 모든 방향으로 그래프를 탐색하고 이미 경로에있는 정점을 칠 때만 경로를 저장하고 싶습니다.

그래서, 기능 full_paths(a,G) 반환해야합니다

- [{a,b}, {b,c}, {c,d}] 
- [{a,b}, {b,d}, {d,c}] 
- [{a,c}, {c,b}, {b,d}] 
- [{a,c}, {c,d}, {d,b}] 
- [{a,d}, {d,c}, {c,b}] 
- [{a,d}, {d,b}, {b,c}] 

내가 [{a,b}] 또는 [{a,b}, {b,c}] 같은 '불완전한'결과를 필요가 없습니다를, 이미 첫 번째 결과에 포함되기 때문이다.

G의 powerset을 생성하고 특정 크기의 결과를 필터링하는 것 외에는 다른 방법이 있습니까?

어떻게 계산할 수 있습니까?

편집 : 에단이 지적한 바와 같이, 이것은이 백 트럭 전에 경로를 저장하고, 깊이 우선 탐색 방법으로 해결 될 수 있지만, 불행하게도 나는 그것을 수정하는 방법을 이해하지 않습니다 (I 구현 루비 Gratr를 사용 내 알고리즘)

Answer 1

depth first search 또는 유사 콘텐츠를 살펴 보셨습니까? 깊이 우선 검색은 가능한 멀리 이동 한 다음 역 추적합니다. 역 추적해야 할 때마다 경로를 기록 할 수 있습니다.

Answer 2

당신이 G이 N 그래프 G에서 정점의 수입니다 길이 N의 N! 경로가 완전히 연결되어 그래프 알고 있다면. 이런 방법으로 쉽게 계산할 수 있습니다. N 시작점을 선택할 수있는 가능성이 있습니다. 각 시작점에 대해 N-1 정점을 경로의 두 번째 정점으로 선택할 수 있으며, 각 경로에서 마지막으로 방문하지 않은 정점 만 선택할 수 있습니다. 따라서 N*(N-1)*...*2*1 = N! 경로가 있습니다. 시작점을 선택할 수 없다면, 그것은 그래프 G'과 N-1 정점으로 경로를 찾는 것과 같습니다. 모든 가능한 경로는 모든 꼭지점의 집합 즉, 시작점을 제외한 모든 꼭지점의 순열입니다. 당신이 순열이있을 때 당신이에 의해 경로를 생성 할 수 있습니다 : 순열을 생성하는 방법을

perm_to_path([A|[B|_]=T]) -> [{A,B}|perm_to_path(T)]; 
perm_to_path(_) -> []. 

간단한 방법은 귀하의 경우

permutations([]) -> []; 
permutations(L) -> 
    [[H|T] || H <- L, T <- permutations(L--[H])]. 

그래서입니다 : GV이의 정점의 목록입니다

paths(A, GV) -> [perm_to_path([A|P]) || P <- permutations(GV--[A])]. 

그래프 G.

좀 더 효율적인 버전을 원한다면 좀 더 속임수가 필요합니다.