A * 매우 큰 그래프를위한 알고리즘, 캐싱 단축키에 대한 생각이 있으십니까?

A * 매우 큰 그래프를위한 알고리즘, 캐싱 단축키에 대한 생각이 있으십니까?

---

저는 OpenStreetMap지도에 택배 / 물류 시뮬레이션을 작성하고 있으며 아래 그림과 같이 기본 A * 알고리즘이 대형지도 (예 : Greater London)에 충분히 빠르지 않을 것임을 깨달았습니다.

녹색 노드는 공개 세트 / 우선 순위 대기열에 넣은 노드에 해당하며 막대한 수 (전체 맵은 1-2 백만 정도 임)로 인해 그림에 표시된 경로를 찾는 데 5 초 정도 걸립니다. 불행히도 경로당 100ms는 내 절대 제한에 관한 것입니다.

현재 노드는 인접 목록과 공간 100x100 2D 배열 모두에 저장됩니다.

빠른 쿼리를 위해 전처리 시간, 공간 및 필요한 경우 경로의 최적 성을 절충 할 수있는 방법을 찾고 있습니다. 휴리스틱 비용에 대한 직선 Haversine 공식은 프로파일 러에 따르면 가장 비용이 많이 드는 함수입니다. 기본 A *를 최대한 최적화했습니다.

예를 들어, 2D 어레이의 각 사분면에서 임의의 노드 X를 선택하고 각 사분면 사이에서 A *를 실행하면 후속 시뮬레이션을 위해 경로를 디스크에 저장할 수 있다고 생각했습니다. 쿼리 할 때 사분면에서만 A * 검색을 실행하여 미리 계산 된 경로와 X 사이를 이동할 수 있습니다.

위에서 설명한 것보다 더 정제 된 버전이 있습니까 아니면 내가 추구해야 할 다른 방법이 있습니까? 감사합니다!

기록을 위해, 휴리스틱 비용에 임의로 가중치를 부여하고 무작위로 선택한 노드 10 쌍 사이의 경로를 계산 한 벤치 마크 결과는 다음과 같습니다.

Weight // AvgDist% // Time (ms)
1       1       1461.2
1.05    1       1327.2
1.1     1       900.7
1.2     1.019658848     196.4
1.3     1.027619169     53.6
1.4     1.044714394     33.6
1.5     1.063963413     25.5
1.6     1.071694171     24.1
1.7     1.084093229     24.3
1.8     1.092208509     22
1.9     1.109188175     22.5
2       1.122856792     18.2
2.2     1.131574742     16.9
2.4     1.139104895     15.4
2.6     1.140021962     16
2.8     1.14088128      15.5
3       1.156303676     16
4       1.20256964      13
5       1.19610861      12.9

놀랍게도 계수를 1.1로 늘리면 동일한 경로를 유지하면서 실행 시간이 거의 절반으로 단축되었습니다.

---

최적 성을 거래함으로써 훨씬 더 빠르게 만들 수 있어야합니다. wikipedia의 허용 성 및 최적 성 을 참조하십시오 .

아이디어는 최적 경로의 배 epsilon보다 나쁘지 않은 솔루션으로 이어지는 값 을 사용 1 + epsilon하지만 알고리즘에서 고려할 노드 수를 줄이는 것입니다. 이것이 반환 된 솔루션이 항상 1 + epsilon최적 경로의 시간 이라는 것을 의미하지는 않습니다 . 이것은 최악의 경우입니다. 나는 그것이 당신의 문제에 대해 실제로 어떻게 행동할지 정확히 알지 못하지만 탐구 할 가치가 있다고 생각합니다.

위키 백과에서이 아이디어에 의존하는 여러 알고리즘이 제공됩니다. 나는 이것이 알고리즘을 개선하기위한 최선의 방법이라고 믿으며 여전히 좋은 경로를 반환하면서 시간 제한에 실행할 가능성이 있다고 생각합니다.

알고리즘이 5 초 동안 수백만 개의 노드를 처리하므로 구현을 위해 바이너리 힙도 사용한다고 가정합니다. 맞습니까? 수동으로 구현 한 경우 단순 배열로 구현되고 이진 힙인지 확인하십시오.

---

많은 사전 계산을 수행하는이 문제에 대한 전문 알고리즘이 있습니다. 메모리에서 사전 계산은 A *가 직선 거리보다 훨씬 더 정확한 휴리스틱을 생성하는 데 사용하는 그래프에 정보를 추가합니다. Wikipedia는 http://en.wikipedia.org/wiki/Shortest_path_problem#Road_networks 에서 여러 메소드의 이름을 제공하며 Hub Labeling이 선두 주자라고 말합니다. 이에 대한 빠른 검색은 http://research.microsoft.com/pubs/142356/HL-TR.pdf로 표시 됩니다. A *를 사용하는 이전 버전은 http://research.microsoft.com/pubs/64505/goldberg-sp-wea07.pdf 에 있습니다 .

정말로 Haversine을 사용해야합니까? 런던을 다루기 위해 평평한 지구를 가정하고 피타고라스를 사용하거나 각 링크의 길이를 그래프에 저장할 수 있다고 생각했을 것입니다.

---

Microsoft Research가이 주제에 대해 썼던 정말 훌륭한 기사가 있습니다.

http://research.microsoft.com/en-us/news/features/shortestpath-070709.aspx

원본 논문은 여기에서 호스팅됩니다 (PDF) :

http://www.cc.gatech.edu/~thad/6601-gradAI-fall2012/02-search-Gutman04siam.pdf

기본적으로 몇 가지 시도 할 수 있습니다.

1. 소스와 목적지 모두에서 시작하십시오. 이렇게하면 소스에서 대상으로 이동할 때 수행하는 낭비되는 작업의 양을 최소화하는 데 도움이됩니다.
2. Use landmarks and highways. Essentially, find some positions in each map that are commonly taken paths and perform some pre-calculation to determine how to navigate efficiently between those points. If you can find a path from your source to a landmark, then to other landmarks, then to your destination, you can quickly find a viable route and optimize from there.
3. Explore algorithms like the "reach" algorithm. This helps to minimize the amount of work that you'll do when traversing the graph by minimizing the number of vertices that need to be considered in order to find a valid route.

---

GraphHopper does two things more to get fast, none-heuristic and flexible routing (note: I'm the author and you can try it online here)

1. A not so obvious optimization is to avoid 1:1 mapping of OSM nodes to internal nodes. Instead GraphHopper uses only junctions as nodes and saves roughly 1/8th of traversed nodes.
2. It has efficient implements for A*, Dijkstra or e.g. one-to-many Dijkstra. Which makes a route in under 1s possible through entire Germany. The (none-heuristical) bidirectional version of A* makes this even faster.

So it should be possible to get you fast routes for greater London.

Additionally the default mode is the speed mode which makes everything an order of magnitudes faster (e.g. 30ms for European wide routes) but less flexible, as it requires preprocessing (Contraction Hierarchies). If you don't like this, just disable it and also further fine-tune the included streets for car or probably better create a new profile for trucks - e.g. exclude service streets and tracks which should give you a further 30% boost. And as with any bidirectional algorithm you could easily implement a parallel search.

---

I think it's worth to work-out your idea with "quadrants". More strictly, I'd call it a low-resolution route search.

You may pick X connected nodes that are close enough, and treat them as a single low-resolution node. Divide your whole graph into such groups, and you get a low-resolution graph. This is a preparation stage.

In order to compute a route from source to target, first identify the low-res nodes they belong to, and find the low-resolution route. Then improve your result by finding the route on high-resolution graph, however restricting the algorithm only to nodes that belong to hte low-resolution nodes of the low-resolution route (optionally you may also consider neighbor low-resolution nodes up to some depth).

This may also be generalized to multiple resolutions, not just high/low.

At the end you should get a route that is close enough to optimal. It's locally optimal, but may be somewhat worse than optimal globally by some extent, which depends on the resolution jump (i.e. the approximation you make when a group of nodes is defined as a single node).

---

There are dozens of A* variations that may fit the bill here. You have to think about your use cases, though.

• Are you memory- (and also cache-) constrained?
• Can you parallelize the search?
• Will your algorithm implementation be used in one location only (e.g. Greater London and not NYC or Mumbai or wherever)?

There's no way for us to know all the details that you and your employer are privy to. Your first stop thus should be CiteSeer or Google Scholar: look for papers that treat pathfinding with the same general set of constraints as you.

Then downselect to three or four algorithms, do the prototyping, test how they scale up and finetune them. You should bear in mind you can combine various algorithms in the same grand pathfinding routine based on distance between the points, time remaining, or any other factors.

As has already been said, based on the small scale of your target area dropping Haversine is probably your first step saving precious time on expensive trig evaluations. NOTE: I do not recommend using Euclidean distance in lat, lon coordinates - reproject your map into a e.g. transverse Mercator near the center and use Cartesian coordinates in yards or meters!

Precomputing is the second one, and changing compilers may be an obvious third idea (switch to C or C++ - see https://benchmarksgame.alioth.debian.org/ for details).

Extra optimization steps may include getting rid of dynamic memory allocation, and using efficient indexing for search among the nodes (think R-tree and its derivatives/alternatives).

---

I worked at a major Navigation company, so I can say with confidence that 100 ms should get you a route from London to Athens even on an embedded device. Greater London would be a test map for us, as it's conveniently small (easily fits in RAM - this isn't actually necessary)

First off, A* is entirely outdated. Its main benefit is that it "technically" doesn't require preprocessing. In practice, you need to pre-process an OSM map anyway so that's a pointless benefit.

The main technique to give you a huge speed boost is arc flags. If you divide the map in say 5x6 sections, you can allocate 1 bit position in a 32 bits integer for each section. You can now determine for each edge whether it's ever useful when traveling to section {X,Y} from another section. Quite often, roads are bidirectional and this means only one of the two directions is useful. So one of the two directions has that bit set, and the other has it cleared. This may not appear to be a real benefit, but it means that on many intersections you reduce the number of choices to consider from 2 to just 1, and this takes just a single bit operation.

---

Usually A* comes along with too much memory consumption rather than time stuggles.

However I think it could be useful to first only compute with nodes that are part of "big streets" you would choose a highway over a tiny alley usually.

I guess you may already use this for your weight function but you can be faster if you use some priority Queue to decide which node to test next for further travelling.

Also you could try reducing the graph to only nodes that are part of low cost edges and then find a way from to start/end to the closest of these nodes. So you have 2 paths from start to the "big street" and the "big street" to end. You can now compute the best path between the two nodes that are part of the "big streets" in a reduced graph.

---

Old question, but yet:

"이진 힙"인 다른 힙을 사용해보십시오. 'Best asymptotic complex heap'은 분명히 피보나치 힙이며 위키 페이지에 멋진 개요가 있습니다.

https://en.wikipedia.org/wiki/Fibonacci_heap#Summary_of_running_times

이진 힙은 더 간단한 코드를 가지고 있으며 배열을 통해 구현되고 배열의 순회가 예측 가능하므로 최신 CPU는 이진 힙 작업을 훨씬 빠르게 실행 합니다.

그러나 데이터 세트가 충분히 크면 복잡성 때문에 다른 힙이 이진 힙보다 우위를 차지합니다.

이 질문은 충분히 큰 데이터 세트처럼 보입니다.

참고 URL : https://stackoverflow.com/questions/29656932/a-algorithm-for-very-large-graphs-any-thoughts-on-caching-shortcuts