我正在尝试使用计算耗时的成本函数来执行 A*。成本函数是单线程的，可能需要几秒钟，并且无法优化。
我想并行计算尽可能多的成本。
如果重要的话，我有一个计算成本低廉的可接受的启发式方法。
最佳答案
答案中有两件事需要讨论。首先是算法效率。第二个是并行性。
有一个research paper研究此案例并创建 A* 变体 DEA*。它对边缘成本使用廉价的可接受启发式来获得后继者成本的下限，然后仅在表明后继者可能位于最佳路径上时才计算边缘的实际成本。
通常，A* 通过 (1) 生成具有新 f 成本的后继节点，以及 (2) 将它们置于开放状态来扩展节点。 DEA* 算法 (1) 生成具有估计的 f 成本(下限)的后继者，并且 (2) 将它们置于开放状态。如果仅使用 f 成本估计将状态从开放状态移除，则会计算精确的边缘/f 成本并将状态放回开放状态。
这是 Partial Expansion 总体思路的变体，和other work还探讨了昂贵的边缘问题。
在此模型中，您可以避免计算许多昂贵的边，这很有帮助。但是，并行计算剩余边缘仍然有用。根据具体的成本，有很多方法可以做到这一点。如果您的打开列表是多线程的，则每次将状态添加到打开时，它都可以计算边缘成本。但是，本质上有两个优先级队列会更有效。
一个优先级队列将包含已计算边缘成本的状态，另一个优先级队列将包含需要完成计算的状态。可以编写并行代码来从第二优先级队列获取状态并计算它们的边缘成本，并在完成时将它们添加到第一个队列。然后，常规程序可以按常规优先级顺序处理第一个队列中的状态。
关键点在于，并行部分可以专注于计算接下来要扩展的状态的边缘成本，而不是在将状态添加到队列时计算所有状态。
请注意，这样的过程可能会导致在发现较短路径之前先探索较长路径。因此，您需要跟踪何时找到通往某个状态的更短路径(打开或关闭)，并确保在发现更短路径时将状态从关闭状态移回打开状态。
与此相关的是，一旦找到解决方案就无法终止 - 它不一定是最佳解决方案。您需要完成 f 成本低于您找到的解决方案的所有状态的扩展。 (您可以丢弃解决方案成本大于或等于您找到的解决方案的任何状态。) [请注意，我在这里给出了良好方法的总体方向；如果您对具体细节感到困惑，可以要求澄清。]
关于algorithm - 并行化 A* 以进行昂贵的成本计算，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56760674/