0
나는 유향 그래프의 SCC를가집니다. 이 SCC의 모든 꼭지점을 최소한 한 번 방문하는 경로를 찾기를 원합니다. NP 문제 일 수 있습니다. 어쨌든 어떻게 해결할 수 있습니까?유향 그래프의 모든 정점을 방문하는 경로를 찾는 알고리즘 최소 한 번
A
답변
0
경로가 필요하면 (단순하지 않아도 됨) 1에서 2까지의 경로를 찾은 다음 2에서 3까지의 경로를 찾을 수 있습니다. (1, 2, 3, ...은 SCC의 정점). 그리고 만약 간단한 경로가 필요하다면 gilleain은 NP- 완전한 해밀턴 경로 문제라는 것을 정확히 알게됩니다.
해밀턴 경로 (https://en.wikipedia.org/wiki/Hamiltonian_path)는 각 정점 *을 정확히 한 번 방문하여 NPC인지 여부를 결정합니다. 그러나 적어도 * 한번 방문하는 것이 더 쉬운 것처럼 보입니다 - 더 이상 경로가 아닐 수도 있다는 것을 제외하면 ... – gilleain
_any_ 경로가 필요하면 (간단하지 않은 경우) _some_ 경로를 1에서 2로 찾은 다음 _some_ path를 찾을 수 있습니다 2에서 3까지 등등 (1, 2, 3, ...은 SCC의 정점 수). 그리고 간단한 경로가 필요하다면 @gilleain은 이것이 NP 완전 해밀턴 경로 문제라는 것을 올바르게 인식합니다. –
@IvanSmirnov 감사합니다! 나는 어떤 길을 필요로했다 (걷는다). 단순한 경로가 아닙니다. 이것은 도움이되었습니다. –