0
나는 무향 그래프를 가지고 있으며 주어진 집합의 모든 노드를 연결하는 모든 가능한 경로를 찾고 싶습니다. NP 문제입니까? 알고리즘을 수행하는 알고리즘이 있습니까?이를 수행하는 좋은 방법이 있습니까? 각 경로가 세트의 노드에 닿는 순서는 신경 쓰지 않고 각 노드를 통과해야합니다.주어진 집합의 모든 노드를 건드린 무향 그래프의 모든 경로를 찾는 방법
A
답변
0
해밀턴 경로 문제라고하며 NP 완료입니다. 자세한 정보에 대한
처음에는, 나는이 해밀턴 경로 문제에 대해 생각했다,하지만 내 시나리오를 정확하게 맞지 않는, 또는 어떻게 할 수 적어도 내가 볼 수없는, 그래프는 주어진 집합에있는 노드뿐만 아니라 다른 노드를 가지고 있습니다. 나는 각 경로가 모든 것을 만지길 원합니다. 그러나 경로에서 가로 지르며 집합에없는 그래프의 노드에도 관심이 있습니다. –