A는 * 검색 자바 - TSP는

Question

는

가능한 중복 :
Implementation of A Star (A*) Algorithm in Java

내가 외판원 문제를 해결하기 위해 일부 검색 알고리즘을 구현해야 할 과제에 대한

, 내가 문제를 이해 나는 알고리즘이 어떻게 작동 하는지를 이해하고, 구현 방법을 모른다. (자바는 훌륭하지 않다.)하지만 이것은 정말 쉬운 부분이다.하지만 불행히도 자바 지식은 내가 아는 것을 적용하기에 충분하지 않다. 알고리즘에 대해서.

누군가가 이것을 읽는 방법에 대한 힌트 나 팁을 제공 할 수 있는지 궁금합니다. 시작하기 쉬운 다른 알고리즘이 있다면 다른 알고리즘도 구현해야합니다. 이드와 함께 가서 행복하게 지내라! 여기에 이미 살펴 봤지만 관련성이있는 항목을 찾을 수없는 것 같습니다./

도움이 되었습니까? 고마워요

Answer 1

저는 전문가는 아니지만 A *를 사용하여 여행 판매원 문제를 해결할 수 있다고 생각하지 않습니다. TSP가 NP 하드라는 것을 알고 계실 것입니다. 정확한 솔루션은 매우 복잡하며 모든 경우에 존재하지 않습니다. 솔루션을 대략적으로 알고있는 가장 쉬운 방법은 '시뮬레이션 된 어닐링 (Simulated Annealing)'입니다.이 방법은 확률 론적 방법입니다 (즉, 무작위!).

아이디어는 매우 간단합니다. 포인트를 목록으로 구성하면 모든 노드 사이의 경로를 나타냅니다 ('둘러보기'라고 함). 둘러보기의 길이를 계산하고 길이를 저장하십시오. 그런 다음 임의의 하위 목록을 선택하고 간단히 되돌립니다. 새로운 길이를 계산하십시오. 새 목록이 더 짧으면 유지하거나 그렇지 않으면 버립니다. 단순히 100/1,000/10,000,000 번 (포인트 수에 따라)이 단계를 반복하면 합리적인 근사치를 얻을 수 있습니다.

예

List tour = [e, b, a, d, c] 
int len = tourLength(tour) 
List newTour = [e, b] + [d, a] + [c] // a and d have been reversed 
int newLen = tourLength(newTour) 
if(newLen < len) { 
    tour = newTour 
} 

10 점 (100)의 반복이 좋은 결과를 얻을 수 있어야 ... 5 점 (의사)가 상상.