A * 알고리즘에 대한 추론

Question

A *로 해결해야 할 문제가 있지만 좋은 경험적 방법을 설계하기가 어렵습니다.

내 문제는 다음과 같습니다

부하를 극대화하고 이동 시간을 최소화하고자 알려진지도에 이동하는 도시에서 쓰레기 수거 트럭에 의해 달성하기 위해 최적의 경로를 결정합니다.

저는 네 가지 유형의 노드가 있습니다 : 제럴 노드, 덤프 노드, 가비지 노드 및 가스 노드.

쓰레기 수거 트럭에 가스가 없을 수 있으며 차량을 다시 채울 수 있습니다. 또한 1 개 이상의 쓰레기 수거통이 배달 될 수 있습니다.

이 문제를 해결하기위한 가장 좋은 방법은 무엇입니까?

감사합니다.

Answer 1

좋은 첫 번째 검색 경험적 탐구는 욕심 많은 알고리즘을 사용하는 것입니다. 예를 들어 일반적인 경로 계획 알고리즘 (도시 간 최단 경로 찾기)에서는 까마귀가 울리는 목적지와 가장 가까운 다음 도시로 항상 이동하는 탐욕스러운 알고리즘을 사용합니다. 이는 선형 시간 경험적 방법이므로 솔루션을 과대 평가하지 않습니다. 귀하의 경우에는 쓰레기 트럭이 항상 가장 가까운 쓰레기 노드 또는 가장 쓰레기가 많은 쓰레기 노드로가는 탐욕스러운 알고리즘을 사용할 수 있습니다. 내가 사용하고있는 네 개의 노드에 대한 세부 사항을 알지 못해서 더 자세한 정보를 얻을 수는 없지만 아이디어를 얻을 수 있습니다. 솔루션을 과대 평가하지 않는 선형 시간 알고리즘을 사용하면 다음 단계에서 조정할 수 있습니다. (nlog (n) 추론도 대부분의 경우 허용되며, n^2는 매우 비쌉니다.)

Answer 2

A *는 2 포인트 사이의 가장 빠른/가장 짧은 경로를 찾는 데 유용합니다.

그러나 쓰레기 트럭 문제는 아마도 완전히 다른 문제 일 수 있습니다. 점 집합을 주문하여 가장 빠른/최단 경로를 찾아야합니다. 그것은 기본적으로 Traveling Salesman Problem (TSP)이거나 큰 형제 인 Vehicle Routing Problem (VRP)입니다. 둘 다 NP- 완료입니다.

A *는 NP 완전 문제를 처리 할 수 ​​없습니다, 당신은 (this video에 표시됩니다) 예를 the TSP and VRP example in OptaPlanner (java, open source)를 들어, TSP 및 VRP 문제에 대한 해결책을 찾으 등 메타 휴리스틱 같은 알고리즘이 필요합니다.