나는 C++ 프로그램을하려고 애 쓰고있다. 나는 많은 점수를 갖고있는 문제를 해결하려고 노력 중이다. 이제 모든 점을 통과하는 경로를 찾아야합니다. 이것은 TSP에 관한 나의 지식에 따라 모든 포인트에서 다른 모든 포인트로 이동할 수 있기 때문에 실제로 TSP가 아닙니다. 그러나 제 경우에는 점 사이의 경로 네트워크가 고정되어 있으며 모든 점이 모든 다른 점에 연결되지 않을 수도있는 모든 점을 통과하는 적합한 경로를 찾아야합니다. 따라서 어떤 알고리즘을 따르겠습니까?적합한 알고리즘은 무엇입니까?
그래프를 탐색 할 방법을 찾고 계신 것 같습니까? 그렇다면 폭 넓은 검색을 시도한 http://en.wikipedia.org/wiki/Breadth-first_search 또는 깊이 우선 검색 http://en.wikipedia.org/wiki/Depth-first_search을 사용하여 그래프를 탐색하십시오.
질문자의 말씨에 따라이 경우 일 수 있습니다. +1 –
그래프에 대해 Hamiltonian path을 찾고 싶습니다. 그래프 이론의 수학적 필드
는 해밀턴 경로 (또는 경로 추적 ) 회만 각 정점 방문 무향 그래프의 경로이다. 해밀 토니안주기 (또는 해밀턴 회로)는 사이클 인 해밀턴 경로 인 입니다. 이러한 경로와 주기가 그래프에 존재하는지 여부를 결정하는 것은 해밀턴 경로 문제이며 NP 완료입니다.
일부 techniques 존재하는 :
가 N있다! 주어진 n-vertex 그래프에서 Hamiltonian 경로가 될 수있는 다른 일련의 정점들 (완전한 그래프에서)이므로 가능한 모든 시퀀스를 테스트하는 무차별 검색 알고리즘 은 매우 느립니다. 몇 가지 더 빠른 접근법이 있습니다. 프랭크 루빈 (Frank Rubin)의 검색 절차 은 그래프의 가장자리를 세 개의 클래스로 나눕니다. 경로에 있어야하는 것, 경로에있을 수없는 것, 미정입니다. 검색이 진행됨에 따라 결정 규칙 세트는 미정의 경계를 분류하고 검색을 중지할지 또는 계속할지 여부를 결정합니다. 알고리즘은 그래프를 별도로 해결 된 수있는 구성 요소로 나눕니다. 또한 Bellman, Held 및 Karp의 동적 프로그래밍 알고리즘을 사용하여 시간 O (n2 2n)의 문제를 해결할 수 있습니다. 에서이 방법은 정점의 각 집합 S와 S의 각 정점 v에 대해 정확히 정점을 다루고 v로 끝나는 경로가 있는지 여부를 결정합니다. S 및 v의 각 선택 항목에 대해 경로 v가 동적 프로그램에서 이미 계산 된 정보로부터 검색 될 수있는 (S - v, w)에 대해 에 대해 경로가 존재하는 이웃 w를 갖는 경우에만 (S, v)에 대해 이 존재합니다.
안드레아스 Björklund 컴퓨팅 특정 매트릭스 에 의해 해결 될 수 사이클 커버 카운팅으로, 단순한 계산 문제 해밀 토니안 사이클 수를 카운트하는 문제를 줄일 포함 - 배제의 원리를 사용하는 다른 방법을 제공하는 결정 요인. 이 방법을 사용하여 그는 Monte Carlo 알고리즘으로 시간 O (1.657n)에서 임의의 n- 꼭지점 그래프에서 해밀턴 순환 문제를 해결하는 방법을 보여주었습니다. bipartite 그래프의 경우이 알고리즘 을 O 시간 (1.414n)까지 추가로 향상시킬 수 있습니다.
최대 차수 3의 그래프의 경우, 신중한 역 추적 검색은 시간 (O) (1.251n)에 해밀 토니안주기 (있는 경우)를 찾을 수 있습니다.
네트워크가 해밀턴 경로로 구성되어야합니까? – user1869698
@ user1869698 아니요, 그렇지 않습니다. – asheeshr
TSP는 여전히 관련이 있습니다. 노드를 다시 방문 할 수 없더라도 여전히 (비 메트릭) TSP입니다. –
또한,'C++ '는이 질문에 대한 좋은 태그가 아닙니다. 알고리즘을 시도하십시오 –