직사각형 바다가 있다고 가정 해 봅시다. 그것은 매우 큽니다 - 10000x20000.선박 이동 알고리즘
우리는 섬도 가지고 있습니다. 간단히하기 위해, 그것도 직사각형이라고 가정 해 봅시다. 우리는 정확한 위치 (좌표)를 알고 있습니다.
우리가 우주선을 가지고 있다면 (x1, y1), 어떤 섬을 거치지 않고지도 (x2, y2)에서 다른 점까지 최단 경로를 찾을 수 있습니까?
업데이트 : 우주선이나 바다에 대한 제약이 없습니다. 몇 가지를 추가하여 단순화하고 (속도를 높일 수 있다면), 이는 환영 할만한 것입니다.
경로가 최상일 필요는 없습니다. 예를 들어 10 % 할인 될 수 있습니다. 완벽하게 수용 할 수 있습니다.
이러한 그래프
업데이트 : 만약 섬 s는 크지 않다. 왼쪽 또는 오른쪽 경계에서 끝점 및 우회 섬 방향으로 배를 움직일 수있다.
나는 더 관리하기 쉬운 검색 공간으로 그리드를 나눌 때의 접근 방식에 동의합니다. 둥근 섬으로가는 객체 회피를 구현하는 것. – Kylotan
와우, 그래프의 꼭지점을 사용한이 아이디어는 꽤 좋은 것처럼 보입니다. 결과를 시도하고보고 할 것입니다. –
한 가지 더 신경 쓰이는 점은 섬을 횡단하지 않고 정점과 점을 어떻게 연결해야합니까? –
그리드를 그래프로 나타내고 Dijkstra 알고리즘을 실행하려고합니다.
그래프는 아마도 1G 이상을 필요로하지만 모든 최신 컴퓨터의 RAM에 적합합니다.
알고리즘 복잡도는 O (E + V * log (V)), 즉 O (그리드 크기)입니다. ~ 10^8 개의 노드가 있기 때문에 가능해야합니다. 노드 당 ~ 1000 CPU 틱이 있다고 가정 해 봅시다. 4G CPU를 사용하는 경우 틱은 2.5 * 10^-10 초, 즉 2.5 * 10-7 초입니다. 노드 당. 2 * 10^8 노드의 경우 ~ 1 분이 걸립니다. 차원 poligons와
이 알고리즘은 초당 여러 번 호출됩니다. 빨리 처리해야합니다. –
그리드가 변경되지 않으면 모든 노드 쌍의 최단 경로를 사전에 미리 계산할 수 있습니다. 노드 쌍에 의해 경로를 선택하는 것은 확실히 지칠 것입니다 :) – Michael
하지만 40 조의 노드 쌍이 있습니다 ... –
큰 섬에서는 섬이 상대적으로 희박한 경우 작년에 로봇을 쫓는 알고리즘을 사용할 수있다 피할 수있는 물체가있는 환경에서 움직이는 공.
내가 한 것은 로봇, 공 및 장애물 주변의 격자 점을 정의하고 전체 환경에 스파 스 균일 한 격자를 추가하는 것입니다. 두 개의 격자 점 사이의 모서리 비용은이 모서리에 얼마나 가까운 장애물이 있는지에 달려 있습니다 (모서리가 장애물 비용을 통과하면 무한 할 것입니다). 그런 다음 A *를 사용하여 최상의 경로를 계산하십시오. 이것은 Java로 프로그래밍 된 오래된 노트북에서 초당 40 회 수행됩니다.
Tiendil의 제안과 관련하여 LaValle의 Planning Algorithms에서는 섬이 2D 폴리곤 인 경우 graphs for shortest-path searches에 포함 할 가장자리를 논의합니다.
점 사이에 경로가 없도록 섬을 배치 할 수 있습니다. 그러면 어떻게 될까요? –
Paul : 경로를 찾을 때 알아야합니다. –
인쇄 회로 기판 (PCBs)을 라우팅하는 데 사용되는 알고리즘을 보길 원할 것입니다. (예를 들어, 흔적이 교차 할 수없는 등 선박 문제에 비해 추가적인 제약이 있기는하지만) 비슷한 문제입니다. –