我面临一个优化问题：
我有一个带有很多节点（10^5）的图，它们代表平面上的点。
我需要在图表上找到最短路径才能到达“结束节点”，从“开始节点”开始。
任何一对节点都可以连接或不连接。检查它们是否已连接是一项非常昂贵的操作。如果它们是连接的，则与链接相关的权重是两个节点之间的欧几里德距离。
目前我只检查从“当前节点”到每个其他节点的所有链接，以填充 A* 的“打开列表”。我选择了 A*，因为它似乎是寻路中最好的算法，而且我对节点 J 有一个快速、可接受且简单的启发式 H（H = 到目标的距离），但我不确定它是否对我的问题有好处。
预先构建图表是无法管理的，需要检查 N^2 个链接，它太慢了。目前（几乎）只有在没有解决方案、没有从开始到结束的路径的情况下才会构建整个图。
我想要一个更好的解决方案的提示......谢谢！
这真的是两个问题合而为一。我不熟悉 Bresenham 算法，所以我只能建议您查看Wikipedia中给出的优化以及那里的链接。
至于 A*：正如我之前所说，它构建几乎整个图表几乎是不可避免的。您可以尝试使用诸如递归最佳优先搜索或 IDA*（Russell & Norvig，第 2 版中的第 4 章）之类的变体来节省一些内存，如果您的内存很慢，也许还可以节省一些时间。
根据您的图形结构，实现双向搜索也可能是值得的。最简单的 bidir 算法将在一个线程中从 A 到 B 并在另一个线程中从 B 到 A 运行 A* 搜索，直到它们中的任何一个找到解决方案或发现它被卡住了。然后可以杀死另一个线程。（这样做的一个问题是，如果有一个解决方案，你就浪费了很多时间，所以它只有在你有一个空闲的处理器核心时才有用。）
更复杂的算法还将检查两者是否在图中找到相同的点，然后终止线程并组合它们的结果。这可以通过交叉两个搜索中的步骤来实现；并行版本可能相当复杂。
除非您可以处理无法保证最佳解决方案的贪心算法，否则这种 A* 方法可能与您将获得的一样好。如果没有允许修剪某些顶点的额外信息的路径不存在，则没有算法可以避免检查每个顶点。也许 CheckLink 操作可以优化？链接信息是否可以以访问速度更快的格式缓存，或者每次运行时“类似图像”的数据是否会发生变化？