모든 꼭지점을 정확히 한 번 연결하는 그래프에서 최소 가중치의 선형 경로를 찾는 알고리즘

Question

n 개의 꼭지점이있는 가중치 부여 된 무 방향성 그래프가 주어지면에있는 각 꼭지점을 연결하는 경로를 찾는 문제에 직면하게됩니다. 한 줄. 처음에 이것이 최소 스패닝 트리를 찾는 문제라고 생각했습니다 하지만이 경우는 아닙니다. 스패닝 트리 (spanning tree)의 경우 꼭지점에 분기가 이거나 차수가 2보다 클 수 있습니다. 필자가 알아야 할 것은 선형 경로입니다. 즉 끝점을 제외한 모든 꼭지점은 정확히 2도를가집니다. 시작 및 끝 정점은 n 개의 정점 중 하나 일 수 있습니다.

내 내가 출발점으로 모든 정점이 작업을 수행해야합니다

first chose any vertex, maintain a sum 
    check all its neighbors such that the cost of reaching it is 
    least among all the neighbors 
    mark this neighbor as visited 
    add the cost to sum 
repeat the procedure above until all the points have been visited. 

즉 욕심 접근했다. 이 알고리즘이 정확하고 복잡도가 높은지 확실하지 않습니다. 이 문제에 대한 더 나은 접근 방법은 무엇입니까?

Answer 1

이 문제는 이후 모든 가장자리에게 체중 1을주고 "가장 N에서 무게의 선형 경로가?"묻는 경우 Hamiltonian path problem에서 감소에 의해 NP-어려운 것으로 알려져있다 그래프에 해밀턴 경로가 포함되어 있으면 정확하게 대답은 "예"입니다. 결과적으로 P = NP가 다항식 시간 솔루션이 없기 때문에 순수한 무차별 함수보다 더 잘 작동하는 알고리즘을 찾지 못할 것입니다.

퍼레이드에 불쌍해서 죄송합니다. 도움이 되길 바랍니다.

Answer 2

@templatetypedef가 정확하고 이것은 실제로 해밀턴 경로 문제의 인스턴스라고 생각하지만, 여행 판매원 문제에 대한 검색으로 더 좋은 결과를 얻을 수 있습니다. 대부분의 (모든?) TSP 발견 적 방법 (유일한 차이점은 적어도 TSP는 처음부터 끝까지 경로를 추가하는 것으로 설명되기 때문에 그냥 선 대신 "고리"를 형성 함). 또한 TSP는 일반적으로 완전한 그래프를 가정합니다 (즉, 모든 노드는 서로 연결됩니다). 그래프가 완료되지 않은 경우 연결되지 않은 노드 사이에 무한 가중치 연결을 추가하여 일반 알고리즘을 계속 사용할 수 있습니다.

당신이 제공 한 욕심 접근법은 일반적으로 "가장 가까운 이웃"발견 적 방법으로 알려져 있습니다. 거의 모든 사람에게 발생하는 첫 번째 접근 방법입니다. 그것의 비 최적 솔루션을 생산하는 것은 1 세기 이상 알려져 왔습니다. 불행히도, 합리적인 시간에 실행되는 다른 것들도 적어도 적어도 하위 최적의 솔루션을 생성 할 가능성이 있습니다 (적어도 문제에 대한 제한이없는 경우). A *는 합리적인 시간에 합리적 (약간 차선 만)의 결과를 산출하는 가장 일반적인 알고리즘 일 것입니다.