나는 비교적 작은 (40-80 노드) 큐빅 (3- 규칙) 평면 그래프를 가지고 있으며, 나는 그들의 해밀턴 성을 결정해야한다. 나는이 작업은 NP-완료되었다는 사실을 알고,하지만 난 그럼에도 불구하고 나는에 관심이 그래프의 크기가 매우 빠르다 점근 지수 시간 알고리즘에 대한 희망 http://mathworld.wolfram.com/HamiltonianCycle.html에서큐빅 평면 그래프에서 해밀턴 사이클을 찾는 것
40 노드가 행할 것 같다. 포함 할 40 개의 가장자리 중 40 개를 선택합니다.
깊이 우선 검색을 시도해 봅시다.
시작하려면 꼭지점 V를 선택하십시오. 세 개의 입사 에지 중 하나를 제외해야합니다. 한 번에 하나씩이 세 가지 가능성을 시도하십시오. 제외 할 모서리를 선택하면 4 개의 모서리가 포함됩니다. 그런 다음 제외 된 가장자리의 꼭짓점을 "사용됨"이라고합니다.
이 프로세스를 10 회 반복 할 수있는 경우 모든 40 개 가장자리를 선택하여 3^10 (59049) 개의 가능성 만 검색하면됩니다. 물론, 충분한 엣지가 결정된 후에는 "분리 된"꼭지점이 부족할 것입니다.
하지만 이제 알고리즘에 대한 아이디어가 있습니다. 각 단계에서 "사용 된"이웃이 가장 적은 버텍스를 선택하십시오. 사실, 사용 된 모서리가 강제되기 때문에 2 개의 이웃이있는 버텍스를 선택하는 것이 가장 좋습니다. 1 또는 0으로 이웃을 사용하는 버텍스를 선택하는 것이 차선책인지 잘 모르겠습니다. 두 가지 방법을 시도해보십시오! (그리고 사용 된 이웃 3 개는 검색 실패를 나타냅니다.)
가장자리 선택이 완료되면 단일주기를 형성하는지 확인하십시오.
몇 가지 샘플 그래프가 있습니까? 간단한 구현을 시도해 볼 수 있습니다.
:. 는 "루빈 (1974)에 대해 설명 백 트랙킹과 추측을 크게 감소시키는 공제를 사용하여 해밀턴 경로 및 회로의 일부 또는 전부를 그래프로 찾을 수있는 효율적인 검색 절차 "라고 말했습니다.
용지가 여기에 판매를위한 것입니다 http://portal.acm.org/citation.cfm?id=321850.321854