非常大图的 A* 算法，对缓存快捷方式有什么想法吗？
A* Algorithm for very large graphs, any thoughts on caching shortcuts?
我正在 OpenStreetMap 地图上编写 courier/logistics 模拟，我意识到如下图所示的基本 A* 算法对于大型地图（如大伦敦）来说不够快。
绿色节点对应的是开放set/priority队列中的节点，由于数量庞大（整张地图大概1-2百万），需要5秒左右的时间才能找到图中的路线。不幸的是，每条路线 100 毫秒大约是我的绝对极限。
目前，节点存储在邻接列表和空间 100x100 二维数组中。
我正在寻找可以权衡预处理时间的方法，space，如果需要优化路由，以实现更快的查询。根据分析器，启发式成本的直线 Haversine 公式是最昂贵的函数 - 我已经尽可能地优化了我的基本 A*。
例如，我在想如果我从二维数组的每个象限中选择一个任意节点 X 并且在每个象限之间选择 运行 A*，我可以将路径存储到磁盘以供后续模拟。查询时，我可以运行只在象限内进行A*搜索，在预先计算好的路线和X之间。
是否有比我上面描述的更精确的版本，或者我应该采用的不同方法。非常感谢！
作为记录，这里有一些基准测试结果，用于任意加权启发式成本并计算 10 对随机选择的节点之间的路径：
Weight // AvgDist% // Time (ms)
1 1 1461.2
1.05 1 1327.2
1.1 1 900.7
1.2 1.019658848 196.4
1.3 1.027619169 53.6
1.4 1.044714394 33.6
1.5 1.063963413 25.5
1.6 1.071694171 24.1
1.7 1.084093229 24.3
1.8 1.092208509 22
1.9 1.109188175 22.5
2 1.122856792 18.2
2.2 1.131574742 16.9
2.4 1.139104895 15.4
2.6 1.140021962 16
2.8 1.14088128 15.5
3 1.156303676 16
4 1.20256964 13
5 1.19610861 12.9
令人惊讶的是，将系数增加到 1.1 几乎使执行时间减半，同时保持相同的路线。
您应该能够通过权衡最优性使其更快。请参阅维基百科上的 Admissibility and optimality。
想法是使用 epsilon 值，这将导致解决方案不比最佳路径的 1 + epsilon 倍差，但会导致算法考虑的节点更少。请注意，这并不意味着返回的解决方案将始终是最佳路径的 1 + epsilon 倍。这只是最坏的情况。我不知道它在实践中如何解决你的问题，但我认为值得探索。
你在维基百科上得到了许多依赖于这个想法的算法。我相信这是您改进算法的最佳选择，它有可能在您的时间限制内 运行，同时仍然返回良好的路径。
由于您的算法确实在 5 秒内处理了数百万个节点，我假设您也使用二叉堆来实现，对吗？如果您手动实现它们，请确保它们被实现为简单数组并且它们是二进制堆。
这个问题有专门的算法可以进行大量的预计算。从内存中，预计算将信息添加到 A* 用来产生比直线距离更准确的启发式的图形。维基百科在 http://en.wikipedia.org/wiki/Shortest_path_problem#Road_networks and says that Hub Labelling is the leader. A quick search on this turns up http://research.microsoft.com/pubs/142356/HL-TR.pdf. An older one, using A*, is at http://research.microsoft.com/pubs/64505/goldberg-sp-wea07.pdf.
处给出了许多方法的名称
你真的需要使用半正弦吗？为了覆盖伦敦，我本以为你可以假设地球是平坦的并使用毕达哥拉斯，或者在图中存储每个 link 的长度。
Microsoft Research 就此主题撰写了一篇非常棒的文章：
http://research.microsoft.com/en-us/news/features/shortestpath-070709.aspx
原始论文在这里托管（PDF）：
http://www.cc.gatech.edu/~thad/6601-gradAI-fall2012/02-search-Gutman04siam.pdf
基本上有几件事你可以尝试：
- 从源头和目的地开始。这有助于最大程度地减少从源向外遍历目标时执行的无用工作量。
- 使用地标和高速公路。本质上，在每张地图中找到一些通常采用的路径的位置，并执行一些预计算以确定如何在这些点之间有效导航。如果您可以找到一条从源头到地标，然后到其他地标，然后到目的地的路径，您可以快速找到可行的路线并从那里进行优化。
- 探索算法，例如 "reach" 算法。这有助于通过最小化需要考虑的顶点数来找到有效路径，从而最大程度地减少遍历图形时的工作量。
我认为用 "quadrants" 来实现你的想法是值得的。更严格地说，我称之为低分辨率路线搜索。
您可以选择 X 个足够接近的连接节点，并将它们视为单个低分辨率节点。将你的整个图表分成这样的组，你会得到一个低分辨率的图表。这是准备阶段。
为了计算从源到目标的路由，首先识别它们所属的低分辨率节点，并找到低分辨率路由。然后通过在高分辨率图上查找路线来改进您的结果，但是将算法限制为仅属于低分辨率路线的低分辨率节点的节点（可选地，您还可以考虑达到一定深度的相邻低分辨率节点).
这也可以推广到多种分辨率，而不仅仅是 high/low。
最后你应该得到一条足够接近最优的路线。它是局部最优的，但在某种程度上可能比全局最优差一些，这取决于分辨率跳跃（即当一组节点被定义为单个节点时所做的近似）。
有几十种 A* 变体可能符合这里的要求。不过，您必须考虑您的用例。
- 您的内存（以及缓存）受限吗？
- 你能并行搜索吗？
- 您的算法实施是否仅在一个位置使用（例如大伦敦，而不是纽约市或孟买或其他任何地方）？
我们无法知道您和您的雇主所知道的所有详细信息。因此，您的第一站应该是 CiteSeer 或 Google 学者：寻找使用与您相同的一般约束集处理寻路的论文。
然后向下选择三个或四个算法，进行原型设计，测试它们如何扩展并微调它们。您应该记住，您可以根据点之间的距离、剩余时间或任何其他因素，将各种算法组合在同一个大寻路例程中。
如前所述，根据您的目标区域的小规模，放弃 Haversine 可能是您在昂贵的三角评估上节省宝贵时间的第一步。注意：我不建议在纬度、经度坐标中使用欧氏距离 - 将您的地图重新投影到例如靠近中心的横向墨卡托，并使用以码或米为单位的笛卡尔坐标！
预计算是第二个，更改编译器可能是明显的第三个想法（切换到 C 或 C++ - 详情请参阅 https://benchmarksgame.alioth.debian.org/）。
额外的优化步骤可能包括摆脱动态内存分配，并使用有效的索引在节点之间进行搜索（想想 R 树及其 derivatives/alternatives）。
GraphHopper does two things more to get fast, none-heuristic and flexible routing (note: I'm the author and you can try it online here)
- 一个不太明显的优化是避免 1:1 OSM 节点到内部节点的映射。相反，GraphHopper 仅使用连接点作为节点，并节省大约 1/8 的遍历节点。
- 它具有 A*、Dijkstra 或例如 A* 的高效工具。一对多 Dijkstra。这使得在不到 1 秒的时间内穿越整个德国成为可能。 A* 的（none-启发式）双向版本使它更快。
所以应该可以为您提供前往大伦敦地区的快速路线。
此外，默认模式是速度模式，它使一切都快一个数量级（例如，欧洲宽路线为 30 毫秒）但灵活性较低，因为它需要预处理 (Contraction Hierarchies)。如果您不喜欢这个，只需禁用它并进一步微调包含的汽车街道，或者可能更好地为卡车创建一个新的配置文件 - 例如排除服务街道和轨道，它们应该会给您带来 30% 的进一步提升。与任何双向算法一样，您可以轻松实现并行搜索。
我在一家大型导航公司工作，所以我可以自信地说，即使在嵌入式设备上，100 毫秒也应该可以让您从伦敦到雅典。大伦敦将是我们的测试地图，因为它很小（很容易放入 RAM - 这实际上不是必需的）
首先，A* 已经完全过时了。它的主要优点是 "technically" 不需要预处理。在实践中，您无论如何都需要预处理 OSM 贴图，所以这是毫无意义的。
给你巨大速度提升的主要技术是弧形标志。如果将地图划分为 5x6 部分，则可以为每个部分分配 32 位整数中的 1 位位置。您现在可以确定每条边在从另一个路段 到 路段 {X,Y} 行进时是否有用。通常，道路是双向的，这意味着两个方向中只有一个是有用的。所以两个方向之一设置了该位，另一个将其清除。这可能看起来不是真正的好处，但这意味着在许多交叉路口，您可以将要考虑的选择数量从 2 个减少到仅 1 个，而这只需要一个位操作。
通常 A* 伴随着过多的内存消耗而不是时间问题。
不过，我认为首先仅使用属于 "big streets" 的节点进行计算可能会有用，您通常会选择高速公路而不是小巷。
我猜你可能已经将它用于你的权重函数，但如果你使用一些优先级队列来决定下一步要测试哪个节点以进行进一步的旅行，你可以更快。
您也可以尝试将图形减少到仅属于低成本边的节点，然后找到从 start/end 到这些节点中最近的节点的方法。
所以你有 2 条路径，从开始到 "big street" 和 "big street" 到结束。
您现在可以计算缩减图中 "big streets" 的两个节点之间的最佳路径。
老问题，但是：
尝试使用 "binary heap" 不同的堆。 'Best asymptotic complexity heap' 绝对是斐波那契堆，它的维基页面有一个很好的概述：
https://en.wikipedia.org/wiki/Fibonacci_heap#Summary_of_running_times
请注意，二叉堆具有更简单的代码，它是在数组上实现的，并且数组的遍历是可预测的，因此现代 CPU 执行二叉堆操作 很多 更快。
然而，如果数据集足够大，其他堆将胜过二进制堆，因为它们的复杂性...
这个问题好像数据集够大了。
我正在 OpenStreetMap 地图上编写 courier/logistics 模拟，我意识到如下图所示的基本 A* 算法对于大型地图（如大伦敦）来说不够快。
绿色节点对应的是开放set/priority队列中的节点，由于数量庞大（整张地图大概1-2百万），需要5秒左右的时间才能找到图中的路线。不幸的是，每条路线 100 毫秒大约是我的绝对极限。
目前，节点存储在邻接列表和空间 100x100 二维数组中。
我正在寻找可以权衡预处理时间的方法，space，如果需要优化路由，以实现更快的查询。根据分析器，启发式成本的直线 Haversine 公式是最昂贵的函数 - 我已经尽可能地优化了我的基本 A*。
例如，我在想如果我从二维数组的每个象限中选择一个任意节点 X 并且在每个象限之间选择 运行 A*，我可以将路径存储到磁盘以供后续模拟。查询时，我可以运行只在象限内进行A*搜索，在预先计算好的路线和X之间。
是否有比我上面描述的更精确的版本，或者我应该采用的不同方法。非常感谢！
作为记录，这里有一些基准测试结果，用于任意加权启发式成本并计算 10 对随机选择的节点之间的路径：
Weight // AvgDist% // Time (ms)
1 1 1461.2
1.05 1 1327.2
1.1 1 900.7
1.2 1.019658848 196.4
1.3 1.027619169 53.6
1.4 1.044714394 33.6
1.5 1.063963413 25.5
1.6 1.071694171 24.1
1.7 1.084093229 24.3
1.8 1.092208509 22
1.9 1.109188175 22.5
2 1.122856792 18.2
2.2 1.131574742 16.9
2.4 1.139104895 15.4
2.6 1.140021962 16
2.8 1.14088128 15.5
3 1.156303676 16
4 1.20256964 13
5 1.19610861 12.9
令人惊讶的是，将系数增加到 1.1 几乎使执行时间减半，同时保持相同的路线。
您应该能够通过权衡最优性使其更快。请参阅维基百科上的 Admissibility and optimality。
想法是使用 epsilon 值，这将导致解决方案不比最佳路径的 1 + epsilon 倍差，但会导致算法考虑的节点更少。请注意，这并不意味着返回的解决方案将始终是最佳路径的 1 + epsilon 倍。这只是最坏的情况。我不知道它在实践中如何解决你的问题，但我认为值得探索。
你在维基百科上得到了许多依赖于这个想法的算法。我相信这是您改进算法的最佳选择，它有可能在您的时间限制内 运行，同时仍然返回良好的路径。
由于您的算法确实在 5 秒内处理了数百万个节点，我假设您也使用二叉堆来实现，对吗？如果您手动实现它们，请确保它们被实现为简单数组并且它们是二进制堆。
这个问题有专门的算法可以进行大量的预计算。从内存中，预计算将信息添加到 A* 用来产生比直线距离更准确的启发式的图形。维基百科在 http://en.wikipedia.org/wiki/Shortest_path_problem#Road_networks and says that Hub Labelling is the leader. A quick search on this turns up http://research.microsoft.com/pubs/142356/HL-TR.pdf. An older one, using A*, is at http://research.microsoft.com/pubs/64505/goldberg-sp-wea07.pdf.
处给出了许多方法的名称你真的需要使用半正弦吗？为了覆盖伦敦，我本以为你可以假设地球是平坦的并使用毕达哥拉斯，或者在图中存储每个 link 的长度。
Microsoft Research 就此主题撰写了一篇非常棒的文章：
http://research.microsoft.com/en-us/news/features/shortestpath-070709.aspx
原始论文在这里托管（PDF）：
http://www.cc.gatech.edu/~thad/6601-gradAI-fall2012/02-search-Gutman04siam.pdf
基本上有几件事你可以尝试：
- 从源头和目的地开始。这有助于最大程度地减少从源向外遍历目标时执行的无用工作量。
- 使用地标和高速公路。本质上，在每张地图中找到一些通常采用的路径的位置，并执行一些预计算以确定如何在这些点之间有效导航。如果您可以找到一条从源头到地标，然后到其他地标，然后到目的地的路径，您可以快速找到可行的路线并从那里进行优化。
- 探索算法，例如 "reach" 算法。这有助于通过最小化需要考虑的顶点数来找到有效路径，从而最大程度地减少遍历图形时的工作量。
我认为用 "quadrants" 来实现你的想法是值得的。更严格地说，我称之为低分辨率路线搜索。
您可以选择 X 个足够接近的连接节点，并将它们视为单个低分辨率节点。将你的整个图表分成这样的组，你会得到一个低分辨率的图表。这是准备阶段。
为了计算从源到目标的路由，首先识别它们所属的低分辨率节点，并找到低分辨率路由。然后通过在高分辨率图上查找路线来改进您的结果，但是将算法限制为仅属于低分辨率路线的低分辨率节点的节点（可选地，您还可以考虑达到一定深度的相邻低分辨率节点).
这也可以推广到多种分辨率，而不仅仅是 high/low。
最后你应该得到一条足够接近最优的路线。它是局部最优的，但在某种程度上可能比全局最优差一些，这取决于分辨率跳跃（即当一组节点被定义为单个节点时所做的近似）。
有几十种 A* 变体可能符合这里的要求。不过，您必须考虑您的用例。
- 您的内存（以及缓存）受限吗？
- 你能并行搜索吗？
- 您的算法实施是否仅在一个位置使用（例如大伦敦，而不是纽约市或孟买或其他任何地方）？
我们无法知道您和您的雇主所知道的所有详细信息。因此，您的第一站应该是 CiteSeer 或 Google 学者：寻找使用与您相同的一般约束集处理寻路的论文。
然后向下选择三个或四个算法，进行原型设计，测试它们如何扩展并微调它们。您应该记住，您可以根据点之间的距离、剩余时间或任何其他因素，将各种算法组合在同一个大寻路例程中。
如前所述，根据您的目标区域的小规模，放弃 Haversine 可能是您在昂贵的三角评估上节省宝贵时间的第一步。注意：我不建议在纬度、经度坐标中使用欧氏距离 - 将您的地图重新投影到例如靠近中心的横向墨卡托，并使用以码或米为单位的笛卡尔坐标！
预计算是第二个，更改编译器可能是明显的第三个想法（切换到 C 或 C++ - 详情请参阅 https://benchmarksgame.alioth.debian.org/）。
额外的优化步骤可能包括摆脱动态内存分配，并使用有效的索引在节点之间进行搜索（想想 R 树及其 derivatives/alternatives）。
GraphHopper does two things more to get fast, none-heuristic and flexible routing (note: I'm the author and you can try it online here)
- 一个不太明显的优化是避免 1:1 OSM 节点到内部节点的映射。相反，GraphHopper 仅使用连接点作为节点，并节省大约 1/8 的遍历节点。
- 它具有 A*、Dijkstra 或例如 A* 的高效工具。一对多 Dijkstra。这使得在不到 1 秒的时间内穿越整个德国成为可能。 A* 的（none-启发式）双向版本使它更快。
所以应该可以为您提供前往大伦敦地区的快速路线。
此外，默认模式是速度模式，它使一切都快一个数量级（例如，欧洲宽路线为 30 毫秒）但灵活性较低，因为它需要预处理 (Contraction Hierarchies)。如果您不喜欢这个，只需禁用它并进一步微调包含的汽车街道，或者可能更好地为卡车创建一个新的配置文件 - 例如排除服务街道和轨道，它们应该会给您带来 30% 的进一步提升。与任何双向算法一样，您可以轻松实现并行搜索。
我在一家大型导航公司工作，所以我可以自信地说，即使在嵌入式设备上，100 毫秒也应该可以让您从伦敦到雅典。大伦敦将是我们的测试地图，因为它很小（很容易放入 RAM - 这实际上不是必需的）
首先，A* 已经完全过时了。它的主要优点是 "technically" 不需要预处理。在实践中，您无论如何都需要预处理 OSM 贴图，所以这是毫无意义的。
给你巨大速度提升的主要技术是弧形标志。如果将地图划分为 5x6 部分，则可以为每个部分分配 32 位整数中的 1 位位置。您现在可以确定每条边在从另一个路段 到 路段 {X,Y} 行进时是否有用。通常，道路是双向的，这意味着两个方向中只有一个是有用的。所以两个方向之一设置了该位，另一个将其清除。这可能看起来不是真正的好处，但这意味着在许多交叉路口，您可以将要考虑的选择数量从 2 个减少到仅 1 个，而这只需要一个位操作。
通常 A* 伴随着过多的内存消耗而不是时间问题。
不过，我认为首先仅使用属于 "big streets" 的节点进行计算可能会有用，您通常会选择高速公路而不是小巷。
我猜你可能已经将它用于你的权重函数，但如果你使用一些优先级队列来决定下一步要测试哪个节点以进行进一步的旅行，你可以更快。
您也可以尝试将图形减少到仅属于低成本边的节点，然后找到从 start/end 到这些节点中最近的节点的方法。 所以你有 2 条路径，从开始到 "big street" 和 "big street" 到结束。 您现在可以计算缩减图中 "big streets" 的两个节点之间的最佳路径。
老问题，但是：
尝试使用 "binary heap" 不同的堆。 'Best asymptotic complexity heap' 绝对是斐波那契堆，它的维基页面有一个很好的概述：
https://en.wikipedia.org/wiki/Fibonacci_heap#Summary_of_running_times
请注意，二叉堆具有更简单的代码，它是在数组上实现的，并且数组的遍历是可预测的，因此现代 CPU 执行二叉堆操作 很多 更快。
然而，如果数据集足够大，其他堆将胜过二进制堆，因为它们的复杂性...
这个问题好像数据集够大了。