寻路:到目的地的多条路径,去除边缘
pathfinding: multiple paths to a destination, with edge removal
我有一个奇怪的寻路问题。在下图中,有两种边——红色和蓝色。红色边缘是可靠的,而蓝色边缘则不是——它们提供捷径,但在某些情况下可能会消失或不可用——你可以将它们想象成冬天被大雪覆盖的山口,或者周末不运营的渡口,或仅在通勤时间运营的火车线路。
我希望我的探路者产生一系列可能的路径。用户必须知道到达目的地的最快的不可靠方式,以及如果该路径不可用时可能的替代方案。探路者应该产生最短路线(在图中,3 跳使用蓝色边 'b'),和最短的可靠路径 -(5 跳,仅使用红色边)以及所有其他可能的比可靠的路线并利用不可靠的蓝色边缘。
对于图表,这些是可能的排列:
- 3 跳,使用边缘 'b'
- 3 跳,使用边 'a'、'd'
- 4 跳,使用边缘 'c'
- 4 跳,使用边缘 'a'
- 4 跳,使用边缘 'd'
- 5 步,仅使用红色边缘
我对这个算法的第一次尝试如下:
- 查找并保存最短路径(使用广度优先搜索)
- 如果路径中没有蓝色边缘,则停止。
- 如果路径中有蓝色边,移除第一个并转到 1。
但是,此算法并不完整,因为它可能会遗漏一些可能的路径。在上面的示例中,将错过仅使用边缘 'a' 的路径(将包括所有其他路径。)
我的下一个想法是 运行 搜索所有可能的蓝色边缘组合:[a], [b], [c], [d], [a,b], [a,c], ..., [a,b,c,d]
。当然,这是非常低效的,并且对于大量的蓝色边缘可能不可行。
你能想出任何可以帮助我解决这个问题的解决方案吗?我需要其中之一:
- 一种计算所有可能路径的有效方法
- 一种算法,returns 路径按从最短到最长的顺序排列
前者是最好的解决方案,但后者我可以 运行 比如说 10 秒,然后 return 至少可以选择到目的地的短路径。
顺便说一句,我很清楚我的图的大小:大约有 7000 个顶点、30,000 条红色边和 200 条蓝色边。
我敢肯定之前已经考虑过这种问题,但是我找不到任何关于它的文章。你能给我指出正确的方向吗?
据我所知,您可以将问题分为两部分:
- 获取最短可靠路径 - 这可以通过从图中删除所有蓝色边和 运行 任何最短路径算法(例如 Dijkstra's Algorithm)来完成。
- 获取 k 条最短不可靠路径 - 这是未修改图上的 K shortest paths problem,您需要选择
k
。 k
越大 - 生成路径的范围就越大。
请注意,找到所有可能的路径是非常低效的,因为存在这些路径的阶乘数,并且除了最小的图(对于 7,000 个节点来说绝对无法计算)之外,这个数字往往无法计算
我有一个奇怪的寻路问题。在下图中,有两种边——红色和蓝色。红色边缘是可靠的,而蓝色边缘则不是——它们提供捷径,但在某些情况下可能会消失或不可用——你可以将它们想象成冬天被大雪覆盖的山口,或者周末不运营的渡口,或仅在通勤时间运营的火车线路。
我希望我的探路者产生一系列可能的路径。用户必须知道到达目的地的最快的不可靠方式,以及如果该路径不可用时可能的替代方案。探路者应该产生最短路线(在图中,3 跳使用蓝色边 'b'),和最短的可靠路径 -(5 跳,仅使用红色边)以及所有其他可能的比可靠的路线并利用不可靠的蓝色边缘。
对于图表,这些是可能的排列:
- 3 跳,使用边缘 'b'
- 3 跳,使用边 'a'、'd'
- 4 跳,使用边缘 'c'
- 4 跳,使用边缘 'a'
- 4 跳,使用边缘 'd'
- 5 步,仅使用红色边缘
我对这个算法的第一次尝试如下:
- 查找并保存最短路径(使用广度优先搜索)
- 如果路径中没有蓝色边缘,则停止。
- 如果路径中有蓝色边,移除第一个并转到 1。
但是,此算法并不完整,因为它可能会遗漏一些可能的路径。在上面的示例中,将错过仅使用边缘 'a' 的路径(将包括所有其他路径。)
我的下一个想法是 运行 搜索所有可能的蓝色边缘组合:[a], [b], [c], [d], [a,b], [a,c], ..., [a,b,c,d]
。当然,这是非常低效的,并且对于大量的蓝色边缘可能不可行。
你能想出任何可以帮助我解决这个问题的解决方案吗?我需要其中之一:
- 一种计算所有可能路径的有效方法
- 一种算法,returns 路径按从最短到最长的顺序排列
前者是最好的解决方案,但后者我可以 运行 比如说 10 秒,然后 return 至少可以选择到目的地的短路径。
顺便说一句,我很清楚我的图的大小:大约有 7000 个顶点、30,000 条红色边和 200 条蓝色边。
我敢肯定之前已经考虑过这种问题,但是我找不到任何关于它的文章。你能给我指出正确的方向吗?
据我所知,您可以将问题分为两部分:
- 获取最短可靠路径 - 这可以通过从图中删除所有蓝色边和 运行 任何最短路径算法(例如 Dijkstra's Algorithm)来完成。
- 获取 k 条最短不可靠路径 - 这是未修改图上的 K shortest paths problem,您需要选择
k
。k
越大 - 生成路径的范围就越大。
请注意,找到所有可能的路径是非常低效的,因为存在这些路径的阶乘数,并且除了最小的图(对于 7,000 个节点来说绝对无法计算)之外,这个数字往往无法计算