그래프에서 해밀턴 워크를 찾기 위한 다항식 시간 알고리즘

Question

그래프에서 해밀턴 워크를 찾는 다항식 시간 알고리즘이 있습니까?

내 알고리즘은 N 계승이며 정말 느립니다.

Answer 1

방금 물어보셨어요 백만 달러짜리 질문.해밀턴 경로를 찾는 것은 NP-완전 문제입니다.일부 NP-하드 문제는 동적 프로그래밍을 사용하여 다항식 시간에 풀 수 있지만 (내가 아는 한) 이것은 그중 하나가 아닙니다.

Answer 2

일반적으로 해밀턴 경로 문제의 결정 버전은 NP-완전이므로 해밀턴 경로를 찾기 위한 다항식 시간 알고리즘을 얻을 수는 없습니다.평소 N을 사용하면 속도를 약간 높일 수 있습니다!→ N²2^N 동적 프로그래밍 트릭(hp[v][w][S] 계산 = "DP를 사용하여 모든 하위 집합 S와 모든 두 정점 v 및 w에 대해 끝점 v 및 w가 있고 정점이 하위 집합 S인 경로가 있습니까?" ), 하지만 이는 여전히 기하급수적입니다.

그러나 해밀턴 경로가 항상 존재하고 쉽게 찾을 수 있는 특별한 종류의 그래프가 많이 있습니다(Posa, Dirac, Ore 등의 작업 참조).

예를 들어, 다음은 사실입니다: 그래프의 모든 꼭지점에 최소 n/2의 차수가 있는 경우, 이면 그래프는 해밀턴 경로를 갖습니다.실제로 O(n)에서 하나를 찾을 수 있습니다.²) 또는 더 영리하게 수행하면 IIRC도 O(n log n)입니다.
[대략적인 스케치:먼저, 일부 "해밀턴" 주기의 모든 정점을 연결하고 가장자리가 실제로 그래프에 있는지는 신경 쓰지 마십시오.이제 실제로 그래프에 없는 주기의 모든 간선(v,w)에 대해 주기의 나머지 부분을 고려하세요.v...w.deg(v)+deg(w)>=n과 같이 w는 x의 이웃이고 v는 y의 이웃이 되는 연속적인 x,y가 목록에 존재합니다(순서대로).[증거:{w의 모든 이웃 집합}과 {v의 이웃 목록에 있는 모든 후속 집합}을 고려하세요.그들은 교차해야 합니다.] 이제 사이클 [v...xy...wv]를 [vy...wx...v]로 변경하십시오. 대신 유효하지 않은 가장자리가 하나 이상 적으므로 최대 2개가 필요합니다. n번 반복하여 진정한 해밀턴 사이클을 얻습니다.자세한 내용은 여기.]

지금:당신이 찾고 있는 것이 단지 모든 것을 포함하는 산책이라면 가장자리 한 번은 오일러 워크(Eulerian Walk)라고 하며 이를 포함하는 그래프(홀수 차수의 정점 수는 0 또는 2임)의 경우 다항식 시간(빠름)에서 매우 쉽게 찾을 수 있습니다.

Answer 3

NP완료입니다.하지만 만약 당신이 좋은 방법을 찾았다면, 나에게 알려주세요. 그러면 부자가 되는 방법을 알려드리겠습니다.

Answer 4

NP가 어렵기 때문에 가장 짧은 것에 대해 더 나은 알고리즘을 찾는 것은 거의 불가능합니다.그러나 시도해 볼 수 있는 몇 가지 경험적 방법이 있으며 아마도 이에 대한 강의 노트를 참조할 수도 있습니다.)

복잡성을 덜기 위해 탐욕 알고리즘을 사용하여 짧은(같은) 걷기를 찾을 수 있습니다.

Answer 5

흠..이는 귀하의 정의가 무엇인지에 따라 다릅니다.해밀턴 경로는 확실히 NP-완전 경로입니다.그러나 가장자리와 정점을 두 번 이상 방문할 수 있는 해밀토니안 워크(예, 끝에 워크 비트를 추가하는 한 여전히 해밀토니안이라고 함)는 O(p^2logp) 또는 O(max(c^2plogp)로 계산할 수 있습니다. , |E|)) 귀하의 그래프가 Dirac이 처음 추측하고 Takamizawa가 증명한 특정 조건을 충족하는 한.Takamizawa(1980) "그래프에서 짧은 폐쇄 스패닝 워크를 찾는 알고리즘"을 참조하세요.

폴

Answer 6

작업 중인 그래프가 생성되는 방식에 따라 욕심 많은 경로 확장을 수행한 다음 중단될 때 임의의 에지 교환을 수행하여 임의 인스턴스에 대해 예상 다항식 시간을 얻을 수 있습니다.

이는 해밀턴 워크(Hamiltonian Walk)가 보장되는 무작위로 생성된 상대적으로 희박한 그래프에 대해 잘 작동합니다.

Answer 7

내 쿼리:그래프 G에서 해밀턴주기를 찾기위한 검색 문제 RHAM이 자체적으로 축소 가능하다는 것을 보여주십시오. 검색 문제 r은 의사 결정 문제에 대한 요리가 가능한 경우 자체적으로 축소 가능합니다.
SR={ x : R(x) ≠ ∅ }