스캐너의 최단 경로 찾기

Question

nearfieldscanner에서 작업 중이며 scannerhead의 최단 경로를 찾는 방법을 찾아야합니다.

한번에 13 포인트를 사용한다고 가정 해 보겠습니다.

• 그런 다음 스캐너에서 현재 위치 (point0)를 가져와 가장 가까운 지점 (Point1)을 찾습니다.
• 이제 Point1이 현재 위치가되고 point1 - (point2)에 가장 가까운 지점을 찾습니다.
• 지금 POINT2는 현재 지점이됩니다 등등 ...

는 Offcourse이 정말 최단 경로가 아닙니다.

스캐너는 25 포인트 이상을 즉시 처리 할 수 ​​있어야하므로 순열은 옵션이 아닙니다. 1cm를 주행하는 데 0.45 초가 소요되고 표면은 대부분 10x15cm입니다.

주요 목표는 시간을두고 스캔 속도를 높이는 것입니다.

이 작업은 C# 또는 Matlab에서 수행해야합니다.

이것이 가능합니까?

Answer 1

짐작할 수있는 모든 조합을 제외하고는 수학적 "해결책"이 없습니다.
http://en.wikipedia.org/wiki/Travelling_salesman_problem

당신은 "좋은"솔루션 (유전자 알고리즘 등)을 찾기 위해 다른 알고리즘을 시도 할 수 있습니다,하지만 당신은 당신이 최고의 해결책을 발견하는 경우, 말할 수 없을 것입니다.

SO 예를

편집에 대한 What is an NP-complete in computer science? 볼에 당신이 (모든 시도 후 제외) BEST 솔루션을 때로는 당신이 결정할 수 있습니다. 그러나 이것들은 드물게 특별한 경우입니다. 경로의 길이가 각 점의 최단 거리의 합계와 같으면 최적을 찾았습니다. 라인에 누워있는 모든 포인트와 마찬가지로 1-2-3-n으로 가십시오. 그러나 일반적으로 더 나은 솔루션이 있는지를 모른 채 최상의 솔루션이 아닌 것을 찾을 수 있습니다. 주요 목표는 "낭비"언제든지, 나는 이런 식으로 그것을 할 것하지 않는 경우 : 아이디어로

EDIT2

은 첫 번째 점을 선택, 당신은으로 이동 스캐너를 원한다. 스캐너를 움직이기 시작하십시오. 스캐너가 움직이는 동안 (다른 스레드), NN 알고리즘으로 경로를 계산하십시오. 이제 경로에서 몬테 카를로 알 고를 실행하여 더 나은 것을 찾습니다. 스캐너가 첫 번째 점에 도달하면 MC 알고리즘을 중지합니다 (스캐너가 MoveCompletetion에 신호를 보내야 함). 경로에서 첫 번째 점을 새 스캐너 대상으로 가져옵니다. 마지막 단계에 도달 할 때까지 이전 단계를 반복하십시오.
이로써 스캐너를 이동하는 데 필요한 시간을 계산할 때만 사용하고 있습니다. 그리고 항상 NN 경로를 기본으로 사용하기 때문에 결코 더 나 빠지지 않을 수 있지만 때로는 (때로는?) 더 좋습니다. 이 알고리즘은 병렬로 쉽게 수행 할 수 있으므로 멀티 코어 컴퓨터에서 더 나은 결과를 얻을 수 있습니다.