调整最短路径算法
对于数据结构和在大学的算法课上，我们必须实现论文中提出的算法。该论文可以在 在这里。 所以我完全实现了该算法，但仍然存在一些错误（但这并不是我问这个问题的真正原因，如果您想了解到目前为止我是如何实现它的，您可以找到它 这里）
我在 Stackoverflow 上问问题的真正原因是作业的第二部分：我们必须努力让算法变得更好。我想到了几种方法，但它们在理论上听起来都不错，但在实践中却效果不佳：
- 在源节点和结束节点之间画一条线，搜索最接近该线中间的节点，然后将2 中的“路径”递归。基本情况将是一个较小的图，由单个 Dijkstra 进行计算。这实际上并不是对当前算法的调整，但经过一些思考，很明显这不会给出最佳解决方案。
- 尝试通过为指向末端节点的边赋予更高的优先级来赋予算法一定的方向感。这也不是最佳的。
所以现在我已经没有想法了，希望这里有人能给我一些可能的调整的提示。它实际上并不需要改进算法，我认为他们要求我们这样做的第一个原因是我们不只是在不知道其背后是什么的情况下实现论文中的算法。
（如果 Stackoverflow 不是提出这个问题的正确地方，我很抱歉:)）
算法的简短描述： 该算法尝试选择哪些节点看起来有希望。我所说的承诺是指他们有很好的机会走上最短路径。节点的前景如何由它的“覆盖范围”来体现。路径上顶点的范围是其到起点和终点的距离中的最小值。图中顶点的到达范围是该顶点在所有最短路径上的到达范围的最大值。 Dijkstra算法中为了最终判断节点是否被添加到优先级队列中，添加了一个test()函数。 Test 返回 true（如果图中某个顶点的到达范围大于或等于，则将在 v 时刻从原点到 v 的路径的权重插入到优先级队列中）或（图中顶点的到达范围）图大于或等于从 v 到结束顶点的欧几里德距离）。
哈姆·德·韦德特
for a datastructures & algorithms class in college we have to implement an algorithm presented in a paper. The paper can be found here.
So i fullly implemented the algorithm, with still some errors left (but that's not really why I'm asking this question, if you want to see how I implemented it thus far, you can find it here)
The real reason why I'm asking a question on Stackoverflow is the second part of the assignment: we have to try to make the algorithm better. I had a few ways in mind, but all of them sound good in theory but they won't really do good in practice:
- Draw a line between the source and end node, search the node closest to the middle of that line and divide the "path" in 2 recursively. The base case would be a smaller graph were a single Dijkstra would do the computation. This isn't really an adjustment to the current algorithm but with some thinking it is clear this wouldn't give an optimal solution.
- Try to give the algorithm some sense of direction by giving a higher priority to edges that point to the end node. This also won't be optimal..
So now I'm all out of ideas and hoping that someone here could give me a little hint for a possible adjustment. It doesn't really have to improve the algorithm, I think the first reason why they asked us to do this is so we don't just implement the algorithm from the paper without knowing what's behind it.
(If Stackoverflow isn't the right place to ask this question, my apologies :) )
A short description of the algorithm:
The algorithm tries to select which nodes look promising. By promising I mean that they have a good chance on lying on a shortest path. How promising a node is is represented by it's 'reach'. The reach of a vertex on a path is the minimum of it's distances to the start and to the end. The reach of a vertex in a graph is the maximum of the reaches of the vertex on all shortest paths.
To eventually determine whether a node is added to the priority queue in Dijkstra's algorithm, a test() function is added. Test returns true (if the reach of a vertex in the graph is larger or equal then the weight of the path from the origin to v at the time v is to be inserted in the priority queue) or (the reach of the vertex in the graph is larger or equal then the euclidean distance from v to the end vertex).
Harm De Weirdt
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
在这种情况下，你最好的选择是像研究人员一样思考：一般研究和计算机科学研究具体是关于渐进式改进，一个人表明他们可以使用 Dijkstra 算法更快地计算某些东西，然后他们或其他人表明他们可以使用 A* 更快地计算同样的事情。这是一系列的小步骤。
也就是说，寻找改进论文中提出的算法的方法的最佳位置是未来方向部分。本文为您提供了一些朝这个方向努力的机会，但在本例中您的金矿位于第 5 节和第 6 节。作者在多个地方承认了不同的可能方法。尝试研究其中一些方法，这应该会导致您对算法进行可能的改进，或者至少是一种有争议的改进。
祝你好运！
Your best bet in cases like this is to think like a researcher: Research in general and Computer Science research specifically is about incremental improvement, one person shows that they can compute something faster using Dijkstra's Algorithm and then later they, or someone else, show that they can compute the same thing a little faster using A*. It's a series of small steps.
That said, the best place to look for ways to improve an algorithm presented in a paper is in the future directions section. This paper gives you a little bit to work on in that direction, but your gold mine in this case lies in sections 5 and 6. There are multiple places where the authors admit to different possible approaches. Try researching some of these approaches, this should lead you either to a possible improvement in the algorithm or at least an arguable one.
Best of luck!