여행 세일즈맨 솔버를 사용하여 해밀턴 경로를 결정합니다

Question

이것은 여행 판매원 최적화 문제와 해밀턴 경로 또는 사이클 결정 문제에 대한 휴리스틱을 구현하도록 요청하는 프로젝트를위한 것입니다. 구현 자체에 대한 도움이 필요하지 않지만 내가가는 방향에 대한 질문이 있습니다.

나는 이미 유전자 알고리즘을 기반으로 한 TSP 휴리스틱을 가지고 있습니다. 완전한 그래프를 가정하고, 인구로서의 무작위 솔루션 세트로 시작하며, 여러 세대의 인구를 개선하기 위해 노력합니다. 해밀턴 경로 또는 사이클 문제를 해결하는 데 사용될 수 있습니까? 가장 짧은 경로를 얻기 위해 최적화하는 대신 경로가 있는지 확인하고 싶습니다.

이제 완전한 그래프에는 해밀턴 경로가 있으므로 TSP 휴리스틱은 모든 그래프로 확장되어야합니다. 두 도시 사이에 경로가없는 경우 가장자리를 일부 무한대 값으로 설정하고 유효한 해밀턴 경로 인 첫 번째 경로를 반환하여이를 수행 할 수 있습니다.

그것이 접근하는 올바른 방법입니까? 아니면 해밀턴 길에 다른 휴리스틱을 사용해야합니까? 저의 주요 관심사는 TSP 최적화가 작동하여 솔루션으로 시작하여 개선하기 때문에 다소 확신 할 수 있기 때문에 실행 가능한 접근 방식인지 여부입니다. 그러나 Hamiltonian Path 결정자가 고정 된 세대에서 경로를 찾을 수는 없습니다.

나는 최선의 접근 방식이 그것을 직접 테스트하는 것이라고 가정하지만, 시간에 제약을 받고이 경로를 내려 가기 전에 물어볼 것이라고 생각했습니다 ... (대신 해밀턴 경로를위한 다른 휴리스틱을 찾을 수 있습니다)

Answer 1

당신이 이것에 대한 답을 얻은 적이 있는지 모르겠습니다. 간단한 요령은 다른 모든 지점에 0이있는 더미 지점을 추가하는 것입니다. TSP를 해결하고 더미 지점을 제거하십시오. 남아있는 것은 해밀턴 경로입니다. 단순한 !

Answer 2

둘 다 NP 완전한 문제이므로 정의상 입력을 변환하고 동일한 알고리즘을 사용할 수 있습니다 .-)

그러나 기본 아이디어는 작동해야합니다. 물론 새로운 경로 생성과 성공 기준을 변경해야 할 수도 있습니다.

편집 : BTW : 무작위 알고리즘에 대한 제안이 있습니다.http://en.wikipedia.org/wiki/hamiltonian_path_problem