Ищет ускорения для поиска A *

Question

У меня есть следующий работая A * код в C#:

static bool AStar(
    IGraphNode start, 
    Func<IGraphNode, bool> check, 
    out List<IGraphNode> path) 
{ 
    // Closed list. Hashset because O(1). 
    var closed = 
     new HashSet<IGraphNode>(); 
    // Binary heap which accepts multiple equivalent items. 
    var frontier = 
     new MultiHeap<IGraphNode>(
      (a, b) => 
      { return Math.Sign(a.TotalDistance - b.TotalDistance); } 
      ); 
    // Some way to know how many multiple equivalent items there are. 
    var references = 
     new Dictionary<IGraphNode, int>(); 
    // Some way to know which parent a graph node has. 
    var parents = 
     new Dictionary<IGraphNode, IGraphNode>(); 

    // One new graph node in the frontier, 
    frontier.Insert(start); 
    // Count the reference. 
    references[start] = 1; 

    IGraphNode current = start; 

    do 
    { 

     do 
     { 
      frontier.Get(out current); 
      // If it's in the closed list or 
      // there's other instances of it in the frontier, 
      // and there's still nodes left in the frontier, 
      // then that's not the best node. 
     } while (
      (closed.Contains(current) || 
      (--references[current]) > 0) && 
      frontier.Count > 0 
      ); 

     // If we have run out of options, 
     if (closed.Contains(current) && frontier.Count == 0) 
     { 
      // then there's no path. 
      path = null; 
      return false; 
     } 


     closed.Add(current); 
     foreach (var edge in current.Edges) 
     { 
      // If there's a chance of a better path 
      // to this node, 
      if (!closed.Contains(edge.End)) 
      { 
       int count; 
       // If the frontier doesn't contain this node, 
       if (!references.TryGetValue(edge.End, out count) || 
        count == 0) 
       { 
        // Initialize it and insert it. 
        edge.End.PathDistance = 
         current.PathDistance + edge.Distance; 
        edge.End.EstimatedDistance = CalcDistance(edge.End); 
        parents[edge.End] = current; 
        frontier.Insert(edge.End); 
        references[edge.End] = 1; 
       } 
       else 
       { 
        // If this path is better than the existing path, 
        if (current.PathDistance + edge.Distance < 
         edge.End.PathDistance) 
        { 
         // Use this path. 
         edge.End.PathDistance = current.PathDistance + 
          edge.Distance; 
         parents[edge.End] = current; 
         frontier.Insert(edge.End); 
         // Keeping track of multiples equivalent items. 
         ++references[edge.End]; 
        } 
       } 
      } 
     } 
    } while (!check(current) && frontier.Count > 0); 

    if (check(current)) 
    { 
     path = new List<IGraphNode>(); 
     path.Add(current); 
     while (current.PathDistance != 0) 
     { 
      current = parents[current]; 
      path.Add(current); 
     } 
     path.Reverse(); 
     return true; 
    } 

    // Yep, no path. 
    path = null; 
    return false; 
} 

Как сделать это быстрее? Никаких примеров кода, пожалуйста; это вызов, который я поставил перед собой.

Редактировать: Чтобы уточнить, я ищу любые советы, предложения, ссылки и т. Д., Которые относятся к A * в целом. Код является лишь примером. Я попросил не использовать образцы кода, потому что они упрощают реализацию описанной техники (ов).

Спасибо.

Answer 1

Вы смотрели this page или this page? У них есть много полезных советов по оптимизации, а также отличная информация об A * в целом.

Answer 2

Переход к использованию случайной Meldable Queue для структуры кучи. Поскольку вам нужен вызов программирования, я не буду показывать вам, как я изменил рекурсивный метод Meld, чтобы он не был рекурсивным. Это трюк, чтобы получить скорость из этой структуры. Дополнительная информация в газете «Гамбинов» «Рандомизированные очереди с первичным приоритетом» (поиск в Интернете для этого).