4 차원 데이터를 통한 길 찾기

Question

문제는 4 차원 바람 (높이가 다른 바람과 여행 할 때 변화하는 바람 (예측 풍 모델))을 통해 평면에 대한 최적의 경로를 찾는 것입니다.

저는 전통적인 A * 검색 알고리즘을 사용하여 3 차원 및 바람 벡터에서 작동하도록 해킹했습니다.

많은 경우에 작동하지만 매우 느립니다 (엄청난 양의 데이터 노드 처리) 일부 가장자리의 경우에는 작동하지 않습니다.

나는 "잘"작동한다고 생각하지만, 그 느낌은 매우 해킹 된 것 같습니다.

이 같은 데이터 (아마도 유전자 알고리즘 또는 신경망)를 통해 경로를 찾는 더 효율적인 방법이 있습니까? 아니면 내가 고려하지 않은 것도 있습니다. 유체 역학인가요? 나 몰라?

편집 : 추가 세부 사항.

데이터는 바람 벡터 (방향, 크기)입니다. 데이터는 25 개의 다른 높이에서 15x15km 간격으로 배치됩니다.

"doesnt always work"라는 말은 경로 무게가 다른 경로와 같기 때문에 항공기에 대한 어리석은 경로를 선택한다는 의미입니다. 경로 찾기에 적합하지만 비행기에 적합하지 않습니다.

나는 각 노드 변경에 대한 계정에 많은 물건을 가지고 : 내림차순 이상 높이의

• 비용.
• 바람 저항.
• 너무 높은 저항을 가진 노드를 무시합니다. 직선 대 등의 대각선의 Tavel
• 비용

내 경험적 또는 H 값으로 유클리드 거리를 사용한다. 나는 체중이나 G 값 (위의 목록)에 대해 다양한 요소를 사용합니다.

감사합니다.

Answer 1

언제든지 weighted A*을 사용하여 시간 최적화를 수행 할 수 있습니다.

가중치 A * [또는 A * ε]는 A *보다 빠른 경로를 찾을 것으로 예상되지만 경로는 최적이되지 않습니다. [그러나이 경로는 최적의 경계를 제공합니다. 엡실론/무게].

Answer 2

A *는 가장 빠른 검색 알고리즘으로 광고되지 않습니다. 발견 한 첫 번째 솔루션이 최고가 될 것이라고 보장합니다 (허용 가능한 추론을 제공한다고 가정). 일부 경우에 작동하지 않는 경우 구현의 일부 측면에 문제가있는 것입니다 (어쩌면 A *의 메커니즘, 아마도 도메인 관련 항목 일 수도 있습니다. 사용자가 세부 정보를 제공하지 않았다면 말할 수 없음) 그 이상).

너무 느린 경우 사용중인 추론을 재고하는 것이 좋습니다.

최적의 솔루션이 필요하지 않은 경우 다른 기술이 더 적합 할 수 있습니다. 다시 말하지만, 문제에 관해 제공 한 것이 거의 없으므로 그 이상의 것을 말하기는 어렵습니다.

Answer 3

오프라인이나 온라인으로 계획하고 계십니까?

일반적으로 이러한 문제의 경우 실제로 바람이 날 때까지 바람이 무엇인지 알 수 없습니다. 이것이 실제로 온라인 문제라면 가장 최적의 정책을 세우는 것을 고려하는 것이 좋습니다. 이 분야에 대한 많은 연구가 이미 있습니다. 가장 좋은 방법은 "보강 학습을 통한 급상승 항공기의 자율 제어" John Wharington입니다.