我实现了A*算法(实际上是对它的修改…)来计算电路板上的布线。虽然查找路径相当快，但查找no需要很长时间(>100ms)。路径。
从我所遇到的算法大纲来看，很明显，只有当未访问节点队列为空时，它才会终止。
是否有任何启发式方法来提前终止对路径的搜索——可能在添加额外假设时?
我将只是定义一个最大成本限制和终止，如果没有候选人+lowerBoundOfEstimatedCosts仍然小于这个限制。
在电路板上，我认为任何路径都不应该超过曼哈顿距离的5倍(只是我的猜测)
另一个想法:
也许确定是否有路径(使用某种"洪水填充")可能是个好主意。它避免了计算每个点的启发式，因此应该比用A*-Search搜索洞的速度快得多。
在多线程环境中，您可以在第二个线程(可能是低优先级)中运行此操作，并在填充方法发现根本没有路径时立即终止a *-Search。