A*算法速度改进

Question

目前，我有一个非常通用的A*算法，它是我在https://github.com/kd7uiy/AStar上作为开源提交的。在过去的一个多月里，我一直在努力加快速度，虽然我正在取得稳步的进步，但在这个时候，我很难看到我能做些什么来加快速度。虽然我相信它是通用的C#代码，但我使用它是为了统一。作为参考，我已经包含了下面的分析器输出的一个困难的路径，即大约50个节点，涉及到一些复杂性。

我相当肯定，我可以通过预先计算瓷砖内部的一些距离并提供“邻居”输入来提高速度，从而在一定程度上减少迭代次数，但如果可能的话，我想为库部分提供一个最优的解决方案。

我的地图是不均匀的非对称地图。在确定航速时，它试图模拟风对帆船的影响。这大大减少了我可以使用的算法，但是通用的A*似乎仍然工作得相当好。

这里不包括我所有的代码，但这里是主要的路径查找类。其余的可以在我上面的git存储库中看到。

using Priority_Queue;
using System;
using System.Collections.Generic;

public class AStarPathfinder<T> where T : class, IAstarNode<T>
{

    private FastPriorityQueue<DataSet<T>> orderedTestList;
    private static AStarPathfinder<T> _instance;
    private List<T> visited;
    private DataSet<T>[] fullDataTraveled=null;

    private IComparer<DataSet<T>> Comparer;

    /// <summary>
    /// Get an instance of the pathfinder. The tile should be passed as a function
    /// </summary>
    public static AStarPathfinder<T> Instance
    {
        get{
            if (_instance== null)
            {
                _instance = new AStarPathfinder<T>();
            }
            return _instance;
        }
    }

    private AStarPathfinder()
    {
        orderedTestList = new FastPriorityQueue<DataSet<T>>(16);
        visited = new List<T>();
        Comparer = Comparer<DataSet<T>>.Default;
    }

    /// <summary>
    /// Finds the distance to a given tile, given A* processing
    /// </summary>
    /// <param name="cur">The start tile</param>
    /// <param name="dest">The end tile</param>
    /// <returns></returns>
    public int DistanceTo(T cur, T dest, float tweakParam)
    {
        return PopulatePath(cur, dest, tweakParam).distTraveled;
    }

    /// <summary>
    /// Find a path from the current tile to the destination. Assumes there is a path to the destination
    /// </summary>
    /// <param name="cur">The start tile</param>
    /// <param name="dest">The end tile</param>
    /// <returns></returns>
    public List<T> FindPath(T cur, T dest,float tweakParam)
    {
        DataSet<T> curTest = PopulatePath(cur, dest, tweakParam);
        List<T> ret = new List<T>();
        while (curTest.prev != null)
        {
            ret.Insert(0, curTest.current);
            curTest = fullDataTraveled[curTest.prev.AStarIndex()];
        }
        return ret;
    }


    int[] heuristics=new int[0];
    int[] blankHeuristics;
    DataSet<T>[] blankTraveled;
    private DataSet<T> PopulatePath(T cur, T dest, float tweakParam)
    {
        orderedTestList.Clear();
        visited.Clear();
        if (heuristics.Length != cur.MaxAStarIndex())
        {
            fullDataTraveled = new DataSet<T>[cur.MaxAStarIndex()];
            blankTraveled = new DataSet<T>[cur.MaxAStarIndex()];
        } else
        {
            Array.Copy(blankTraveled, fullDataTraveled, cur.MaxAStarIndex());
        }

            Tuple<T, int>[] set;
        if (heuristics.Length != cur.MaxAStarIndex())
        {
            heuristics = new int[cur.MaxAStarIndex()];
            blankHeuristics = new int[cur.MaxAStarIndex()];
        } else
        {
            Array.Copy(blankHeuristics, heuristics, cur.MaxAStarIndex());
        }
        DataSet<T> curTest = new DataSet<T>(cur, null, 0, 0);
        fullDataTraveled[cur.AStarIndex()]= curTest;

        while (curTest.current != dest)
        {
            visited.Add(curTest.current);
            set = curTest.current.GetNeighborsAstarDistance(tweakParam);
            foreach (Tuple<T,int> neighbor in set)
            {
                int distanceTo = curTest.distTraveled + neighbor.Second;
                int heuristic = 0;
                if (heuristics[neighbor.First.AStarIndex()]>0)
                {
                    heuristic = heuristics[neighbor.First.AStarIndex()];
                }
                else
                {
                    heuristic = neighbor.First.GetAstarHeuristic(dest, tweakParam);
                    heuristics[neighbor.First.AStarIndex()]= heuristic;
                }

                DataSet<T> ds = new DataSet<T>(neighbor.First, curTest.current, distanceTo, distanceTo + heuristic);
                if (fullDataTraveled[neighbor.First.AStarIndex()]!=null)
                {
                    //A quicker path was found to the tile
                    if (Comparer.Compare(ds, fullDataTraveled[neighbor.First.AStarIndex()]) < 0)
                    {
                        orderedTestList.Remove(fullDataTraveled[neighbor.First.AStarIndex()]);
                        fullDataTraveled[neighbor.First.AStarIndex()] = ds;
                        Enqueue(ds);
                    }
                }
                else
                {
                    fullDataTraveled[neighbor.First.AStarIndex()] = ds;
                    Enqueue(ds);
                }

            }
            try
            {
                curTest = orderedTestList.Dequeue();
            }
            catch (InvalidOperationException)
            {
                curTest = fullDataTraveled[dest.AStarIndex()];
                break;
            }
        }

        return curTest;
    }

    private void Enqueue(DataSet<T> ds)
    {
        if (orderedTestList.Count==orderedTestList.MaxSize)
        {
            orderedTestList.Resize(orderedTestList.MaxSize * 2);
        }
        orderedTestList.Enqueue(ds, ds.Priority);
    }
}

Answer 1

FindPath

您可以通过使用LinkedList而不是List来提高该方法的性能，因为您要在第一个项目之前插入项目，对于列表，它是一个O(n)操作。LinkedList.AddFirst可以作为O(1).^来完成

或者，您也可以将其添加到列表的末尾，然后Reverse列表。

我不能再多说这个了。在循环中调用的许多方法不在您提供的源代码中。