두 개의 서로 다른 알고리즘을 사용하는 undirected unweighted 그래프에서 해밀턴 경로를 찾아야하는 프로젝트가 있습니다. 나는 이미 백 트랙킹 (backtracking)을 사용하여 휴리스틱 알고리즘을 구현했지만, 나는 다른 것을 찾고 있었고 그것을 찾을 수없는 것처럼 보였다.해밀턴 경로 알고리즘
내 질문에 어떤 알고리즘을 사용하면 백 트랙킹을 사용하는 것보다 해밀턴 경로를 알 수 있습니까?
EDIT : 다른 게시물을 살펴본 후 가장 긴 경로 알고리즘을 사용하여 경로의 길이가 꼭지점 수 -1과 같은지 확인하여 해밀턴 경로를 찾을 수 있음을 발견했습니다. if if 이것은 사실이거나 그렇지 않습니다.
미리 감사드립니다.
hamiltonian 경로가 NP 완성이므로 일부 형태의 백 트랙킹으로 끝날 수 있습니다. 스택을 사용하든 전체 목록을 사용하여 지수 상승을 달성 하느냐는 대부분 당신에게 달려 있습니다.
공식을 찾으면 다양한 TSP 알고리즘을 볼 수 있습니다 (실제로는 해밀턴 경로 기술을 알지 못합니다). 가중치가 모두 유효하고 무한대 (모서리가 존재하지 않음)이기 때문에 삼각형 부등식을 이용하는 사람은 적용되지 않습니다.
삼각형 부등식을 필요로하지 않는 TSP 분기 및 절단 공식을 찾습니다. Branch and Cut은 TSP에 대해 입증할만한 최적의 솔루션을 제공하는 최첨단 기법 인 것 같습니다.
최소 스패닝 트리로 분기 및 바인딩하는 것이 좋으며 (구현하기 쉽습니다.) 노드의 가중치를 반복적으로 (분기 사이에서) 노드의 분리 방법으로 확장 할 수 있습니다 > 2를 결과 2의 노드로 변환합니다. 나는 기술 이름을 기억할 수 없다. (그리고 나는 일하고있어, 그것을 찾을 수 없다.) 그러나 MST의 새로운 거리 측정 기준은 다음과 같습니다.
비용 [i, j] = (존재 (i, j)? 1 : 무한대) + 노드 확대 [i] + 노드 확대 [j].
괜찮은 컨버전스를 위해 증가를 변경하는 규칙은 좀 더 복잡합니다 (degree [i]> 2이면 증가, degree [i]이면 < 2이면 줄입니다.). 그러나 나는 다시 생각할 수 없습니다. Held-Karp일지도 모르지만 나는 벗어날 수 있습니다.)
진부한 답변을 드려 죄송합니다. 접근 방법을 찾는 데 도움이 되었길 바랍니다. TSP 기술이 hamiltonian 경로 기술에 얼마나 잘 적용되는지를 알지 못하기 때문에 도움이되지 않을 수 있습니다.