我面临优化问题:
我有一个包含很多节点 (10^5) 的图表，代表平面上的点。
我需要找到图上的最短路径以到达“结束节点”，从“开始节点”开始。
任何一对节点都可以连接或不连接。检查它们是否连接是一项非常昂贵的操作。如果它们是连接的，则与链接关联的权重是两个节点之间的欧氏距离。
目前我只检查从“当前节点”到每个其他节点的所有链接，以便为 A* 填充“开放列表”。我选择了 A*，因为它似乎是寻路中最好的算法，而且我对节点 J 有一个快速、可接受且简单的启发式 H(H = 到目标的距离)，但我不确定它是否适合我的问题。
预先构建图表是难以管理的，需要检查 N^2 个链接，它太慢了。目前(几乎)只有在没有解决方案，没有从头到尾的路径时才构建整个图。
我想要一个更好的解决方案的提示......谢谢!
最佳答案
这真的是两个问题合二为一。我不熟悉 Bresenham 算法，所以我只能建议您查看 Wikipedia 中给出的优化。以及那里的链接。
至于 A*:正如我之前所说，构建几乎整个图几乎是不可避免的。您可以尝试递归最佳优先搜索或 IDA*(Russell & Norvig，第 2 版第 4 章)等变体，以节省一些内存，如果您的内存较慢，也许还可以节省一些时间。
根据您的图形结构，实现双向搜索可能也是值得的。最简单的 bidir 算法会在一个线程中运行 A* 搜索，从 A 到 B，然后在另一个线程中从 B 到 A，直到它们中的任何一个找到解决方案或发现它被卡住了。然后可以杀死另一个线程。 (这样做的一个问题是，如果有解决方案，您已经浪费了很多时间，因此它只有在您有一个空闲的处理器核心时才有用。)
更复杂的算法还会检查两者是否在图中找到相同的点，然后终止线程并合并它们的结果。这可以通过交错两个搜索的步骤来实现；并行版本可能相当复杂。
关于algorithm - 星搜索 : a lot of nodes and a "slow" CheckLink between nodes. .. 有什么建议吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5368610/