2

对于大学的数据结构和算法课程，我们必须实现论文中提出的算法。论文可以在这里找到。所以我完全实现了算法，但仍然存在一些错误（但这并不是我问这个问题的真正原因，如果你想看看我到目前为止是如何实现的，你可以在这里找到它）

我在 Stackoverflow 上提问的真正原因是作业的第二部分：我们必须努力让算法变得更好。我想到了几种方法，但它们在理论上听起来都不错，但在实践中它们并不会真正做得很好：

  • 在源节点和结束节点之间画一条线，搜索最靠近该线中间的节点，并将“路径”递归地划分为 2。如果单个 Dijkstra 进行计算，基本情况将是一个较小的图。这并不是对当前算法的真正调整，但有些人认为很明显这不会给出最佳解决方案。
  • 尝试通过为指向末端节点的边赋予更高的优先级来给算法一些方向感。这也不会是最佳的..

所以现在我完全没有想法，希望这里有人能给我一点提示，以便可能进行调整。它实际上并不需要改进算法，我认为他们要求我们这样做的第一个原因是，我们不只是在不知道其背后是什么的情况下实现论文中的算法。

（如果 Stackoverflow 不适合问这个问题，我很抱歉 :)）

算法的简短描述：算法尝试选择哪些节点看起来很有希望。通过承诺，我的意思是他们很有可能躺在最短的路径上。一个节点的前景如何由它的“范围”表示。路径上顶点的范围是它到起点和终点的距离中的最小值。图中一个顶点的范围是该顶点在所有最短路径上的最大范围。为了最终确定一个节点是否被添加到 Dijkstra 算法中的优先级队列中，添加了一个 test() 函数。

危害德怪异

4

1 回答 1

2

在这种情况下，你最好的选择是像研究人员一样思考：一般研究和计算机科学研究具体是关于增量改进，一个人表明他们可以使用 Dijkstra 算法更快地计算某些东西，然后他们或其他人表明他们可以使用 A* 更快地计算相同的东西。这是一系列的小步骤。

也就是说，寻找改进论文中提出的算法的最佳方法是在未来方向部分。本文为您提供了一些在这个方向上的工作，但在这种情况下，您的金矿位于第 5 节和第 6 节。作者在多个地方承认不同的可能方法。尝试研究其中一些方法，这应该会导致您对算法进行可能的改进，或者至少是一个有争议的改进。祝你好运！

于 2010-12-12T09:35:45.927 回答