对最短路径算法的调整
在大学的一个数据结构和算法课程中，我们需要实现一篇论文中提出的一个算法。你可以在这里找到这篇论文。
我已经完全实现了这个算法，但还有一些错误（不过这并不是我提问的主要原因，如果你想看看我到目前为止是怎么实现的，可以在这里找到）。
我在StackOverflow上提问的真正原因是作业的第二部分：我们需要尝试改进这个算法。我有几个想法，但它们在理论上听起来不错，但在实际应用中可能效果不佳：
- 在起点和终点之间画一条线，寻找离这条线中间最近的节点，然后递归地将“路径”分成两部分。基本情况是一个较小的图，单个的Dijkstra算法就能完成计算。这个方法其实并不是对当前算法的调整，经过思考可以发现这并不能提供最优解。
- 尝试给算法一些方向感，优先考虑指向终点的边。这也不会是最优的……
所以现在我没有更多的想法，希望这里有人能给我一点可能的调整建议。其实不一定要改进算法，我觉得他们让我们这样做的第一个原因是希望我们不仅仅是实现论文中的算法，而是了解其背后的原理。
（如果StackOverflow不是问这个问题的合适地方，我表示歉意 :)）
算法的简要描述：这个算法试图选择哪些节点看起来比较有希望。这里的“有希望”是指它们有较大可能在最短路径上。一个节点的“有希望程度”用它的“可达性”来表示。路径上一个顶点的可达性是它到起点和终点的距离中的最小值。在图中，一个顶点的可达性是所有最短路径上该顶点可达性的最大值。
为了最终确定一个节点是否被添加到Dijkstra算法的优先队列中，添加了一个test()函数。这个函数返回true的条件是：图中一个顶点的可达性大于或等于从起点到v的路径权重（在v被插入优先队列时），或者图中该顶点的可达性大于或等于从v到终点的欧几里得距离。
Harm De Weirdt
1 个回答
在这种情况下，你可以把自己想象成一个研究者。研究，尤其是计算机科学的研究，通常是一步一步慢慢改进的。比如，有人用Dijkstra算法让计算变得更快，后来他们或者其他人又用A*算法让同样的计算变得更快。这就是一个个小进步的过程。
所以，如果你想找办法改进论文中提到的算法，最好的地方就是看“未来方向”这一部分。这篇论文给你提供了一些思路，但真正的宝藏在第5和第6部分。作者在这里提到了一些不同的可能方法。你可以研究一下这些方法，这样可能会找到改进算法的办法，或者至少能找到一个可以讨论的改进点。祝你好运！