A-Star 알고리즘 최적화

Question

Wikipedia 구현에 따른 A * 알고리즘을 here 에 구현했습니다. 그러나 모바일 장치에서 실행하기에는 너무 느립니다. 데스크톱 컴퓨터에서 제대로 실행되지만 기능을 끝내기 위해 끝없는 시간을 기다려야합니다. 알고리즘을 최적화하기 위해 할 수있는 일이 있습니까?

여기에 A * 좋은 휴리스틱 알고리즘,하지만 당신은 아마 너무 최적화를 필요로하는 실제 코드를

public DriveRoute findroute(routenode from, routenode to) 
     { 
      Dictionary<int, routenode> openlist = new Dictionary<int, routenode>(); 
      openlist.Add(from.nodeid, from); 
      Dictionary<int, routenode> closedlist = new Dictionary<int, routenode>(); 
      Dictionary<int, double> gscores = new Dictionary<int, double>(); 
      gscores.Add(from.nodeid, 0); 
      Dictionary<int, double> hscores = new Dictionary<int, double>(); 
      hscores.Add(from.nodeid, distanceForRouting(from.latlon, to.latlon)); 
      Dictionary<int, double> fscores = new Dictionary<int, double>(); 
      fscores.Add(from.nodeid, gscores[from.nodeid] + hscores[from.nodeid]); 
      Dictionary<int, routenode> came_from = new Dictionary<int, routenode>(); 
      while (openlist.Values.Count > 0) 
      { 
       routenode x = getLowestFscore(openlist, fscores); 
       if (x.latlon.Equals(to.latlon)) 
       { 
        return rebuildPathWay(came_from, to); 
       } 
       openlist.Remove(x.nodeid); 
       closedlist.Add(x.nodeid, x); 
       foreach (routearc arc in x.outgoingarcs) 
       { 
        if (closedlist.Keys.Contains(arc.endnode)) 
         continue; 
        double tentative_g_score = gscores[x.nodeid] + arc.time; 
        bool tentative_is_better = false; 
        if (!openlist.Keys.Contains(arc.endnode)) 
        { 
         openlist.Add(arc.endnode, map.routenodes[arc.endnode]); 
         tentative_is_better = true; 
        } 
        else if (tentative_g_score < gscores[arc.endnode]) 
        { 
         tentative_is_better = true; 
        } 
        if (tentative_is_better) 
        { 
         if (came_from.ContainsKey(arc.endnode)) 
          came_from[arc.endnode] = x; 
         else 
          came_from.Add(arc.endnode, x); 
         gscores[arc.endnode] = tentative_g_score; 
         hscores[arc.endnode] = distanceForRouting(arc.endlatlon, to.latlon); 
         fscores[arc.endnode] = gscores[arc.endnode] + hscores[arc.endnode]; 
        } 
       } 
      } 
      return null; 
     } 

Answer 1

전체 코드를 보지 않고 어떤 힌트를 줄 어렵다, 그러나 나는 몇 가지 힌트를 줄 수 있습니다

이

당신이 사전에 할 주요 작업은 가장 낮은 비용으로 뭔가를 발견하는 것입니다. 데이터 구조 뒤의 사전은이 작업을 위해 최적화되어야합니다. 고전적인 데이터 구조는 힙 (new/delete malloc/free와 관련된 것은 아니지만 데이터 구조 : http://en.wikipedia.org/wiki/Heap_%28data_structure%29)입니다.

fibonacci-heaps와 같은 데이터 구조의 하위 유형을 찾을 수 있습니다. . 그것들을 시험해 볼 가치가 있습니다. 혹시 A *를 구현하지 않고서도 splay-tree를 시도해보십시오 (위키에 대한 검색은 여러분에게 히트를 줄 것입니다).

두 번째 : 알고리즘 실행 중에 노드를 삽입하고 제거합니까? 그렇다면 미리 할당 된 노드 풀을 만들고 new/delete 또는 malloc/free를 호출하는 대신에 이것을 사용하십시오. 메모리 할당은 매우 일 수 있습니다.

Answer 2

을합니다.

내가 수행 한 최적화는 모든 노드 대신 노드 그룹을 사용하여 "최상의"경로를 찾는 것입니다. 1,000 개의 도시가 있다고 가정 해보십시오.이 두 그룹을 그룹화하고보다 글로벌 차원에서 최상의 경로를 찾은 다음 경로를 최적화하십시오.

나는이 최적화가 아닌 일반적인 A *를 구현하려고 시도했습니다. 왜 시도하지 않으시겠습니까?)

Answer 3

우선 순위 대기열에서 각 노드의 점수를 캐시해야합니다. 그렇게하면 getLowestFscore를 호출 할 필요없이 새 노드가 필요할 때마다 우선 순위 큐에서 첫 번째 노드를 튕겨 내야합니다. PriorityQueue를 구현할 때는 SortedDictionary<int, List<routenode>>을 사용하십시오. 당신의 삶을 편하게하기 위해서 SetDefault (예 : here을보십시오)를 사용하십시오.

또한 모바일 장치에서 문제가 발생하기 때문에 메모리 문제 일 수 있습니다. BeamSearch를 사용하는 것이 좋습니다. 매번 최상의 결과를 얻을 수는 없지만 더 빨리 실행해야합니다.

Answer 4

for 루프를 병렬 처리 할 수 ​​있습니까? 여러 개의 코어가있는 특정 모바일 장치로 작업하고 있습니까? 그렇다면 Tasks.Parallel.For (....) 또는 Foreach를 살펴보십시오.

또한 가능한 모든 정보를 캐싱하는 것이 좋습니다.

Djikstra의 알고리즘 대신 A *를 사용하는 이유는 무엇입니까?

Answer 5

A *의 대부분의 최적화는 열린 목록과 닫힌 목록의 구현에 들어갑니다. 특히, 다음 네 가지 방법 : 추가, 제거, 가장 작은 값의 항목 가져 오기 및 특정 노드와 관련된 항목 찾기. 개인적으로, Complete Binary Heap을 사용하여 공개 목록을 구조화하면 Python으로 작성된 A * 코드의 속도가 상당히 빨라진다는 사실을 발견했습니다. 희망이 도움이!