무작위로 방향이 바뀌지 않은 소셜 그래프가 있습니다.해밀턴 경로 및 소셜 그래프 알고리즘
가능한 경우 해밀턴 경로를 찾고 싶습니다. 또는 가능하지 않은 경우 (또는 가능한 경우 다항 시간으로 알 수없는 경우) 일련의 경로가 있습니다. 이 "일련의 경로"(모든 N 노드가 정확히 한 번 사용됨)에서 은 경로의 수를 최소화합니다. 및 은 경로의 평균 길이 인을 최대화합니다. (그래서 단일 노드의 N 개의 경로에 대한 간단한 해결책은 아님).
나는 이미 노드와 가장자리에 대한 인접성 매트릭스를 생성했습니다.
제안 사항? 올바른 방향의 포인터? 문제의 NP 완성 (?) 특성 때문에 경험적 방법이 필요하다는 것을 알았습니다. 그리고 나는 "충분히 좋은"대답으로도 괜찮습니다. 또한 나는 자바에서 이것을하고 싶다.
감사합니다.
유전자 알고리즘을 사용하여 (크로스 오버없이) 각 개체는 노드의 순열입니다. 이렇게하면 각 세대마다 "일련의 경로"가 생겨 최소 경로 수 (1)와 최대 평균값으로 진화합니다. 길이 (N).
질문을 올바르게 해석하는 경우 "다중 경로"문제에 대한 최선의 해결책은 해밀턴 경로가 될 수 있고 그 중 하나가 존재하는지 확인하기 때문에 여전히 NP 하드입니다. NP 하드. 더욱이, 해밀턴 경로가 존재하지 않는다고 보장한다고하더라도, 공간에 떠있는 하나의 단절된 노드를 가진 그래프를 줄 수 있기 때문에이 문제를 해결하는 것이 NP 하드 일 수 있습니다. 가장 좋은 솔루션은 다음과 같습니다. 그 노드를 포함하는 사소한 경로와 나머지 그래프의 해밀턴 경로. 결과적으로, P = NP가 아니면, 다항식 시간 알고리즘이 문제가되지 않습니다.
호프가 도움이 되었기를 바랍니다. 부정적인 결과로 불편을 끼쳐 드려 죄송합니다.
다항식 시간에 정확한 해결책이 없다는 것을 깨달으 셨습니다. 어떤 무작위 검색 방법을 사용해 볼 수도 있습니다. 내 추천, 유전자 알고리즘을 시작하고 금기 검색을 시도하십시오.
Angluin과 Valiant는 거의 항상 충분히 조밀 한 Erdos-Renyi 임의 그래프에서 거의 작동하는 선형 선형 시간 법칙을 사용했습니다. 그것은 Wilf, on page 121에 의해 설명됩니다. 아마도 무작위 그래프는 이 아니며 Erdos-Renyi가 아니지만 휴리스틱은 어쨌든 작동 할 수 있습니다 ("실패"하면 길게 (희망을 갖고) 긴 경로를 제공하고 탐욕스럽고 A-V를 다시 실행합니다).
아니요, 한 두 가지 간단한 경로를 갖는 것이 실제 문제가 아님을 의미합니다. 그리고 나는 완전한 대답, 단지 더러운 "단지 충분한"휴리스틱을 찾는 것이 아닙니다. 어떤 아이디어? – lollercoaster