问题标签 [dijkstra]

我在我的一本 AI 书籍中读到，在模拟或游戏中用于寻路的流行算法（A-Star、Dijkstra）也用于解决著名的“15 谜题”。

谁能给我一些关于如何将 15 谜题简化为节点和边图的指示，以便我可以应用其中一种算法？

如果我将图中的每个节点都视为游戏状态，那么那棵树不会变得很大吗？或者这只是这样做的方法吗？

我有一个大约 100 个节点和大约 200 条边的无向图。一个节点标记为“开始”，一个节点标记为“结束”，大约有十几个标记为“必须通过”。

我需要找到从“开始”开始，在“结束”结束，并通过所有“必须通过”节点（以任何顺序）的最短路径。

（http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt是有问题的图表 - 它代表宾夕法尼亚州兰开斯特的玉米迷宫）

我看到了 Edsger Dijsktra 看到的这篇关于编程风格的文章。快速解释一下，主要区别在于莫扎特，当类比到编程时，在写任何东西之前完全理解（有争议的）问题，而贝多芬在将笔记写在纸上时做出了决定，并在此过程中进行了许多修改。使用 Mozart 编程，1.0 版将是软件的唯一版本，其目标是无错误地工作和最高效率。此外，Dijkstra 表示，不应该向公众发布没有达到那种细化和稳定性水平的软件。

根据他的观点，有两个问题。莫扎特编程甚至可能吗？如果我们采用莫扎特风格，我们今天编写的软件真的会受益吗？

我的想法。看来，为了解决软件日益复杂的问题，我们已经从这种方法转向敏捷开发、公共 beta 测试和不断修订等定义 Web 开发的方法，其中速度最重要。但是，当我想到 Web 软件可以经历的所有修订时，尤其是在维护期间，通常会在补丁之上应用补丁，然后通过繁琐的重构过程进行改进——莫扎特的方式似乎很有吸引力。它至少会减少那些烦人的软件更新，例如 Digsby、Windows、iTunes 等，其中许多是需要立即发布新版本的不可预见漏洞造成的。

编辑：有关 Dijsktra 观点的更准确解释，请参阅下面的回复。

我正在查看 A* 寻路算法的定义，它在不同地方的定义似乎有所不同。

不同之处在于遍历节点的后继节点时执行的操作，并发现后继节点在封闭列表中。

• 一种方法（由Wikipedia和本文建议）说：如果继任者在封闭列表中，则忽略它
• 另一种方法（例如，在此处和此处建议）说：如果继任者在封闭列表中，请检查其成本。如果它高于当前计算的分数，则从封闭列表中删除该项目以供将来检查。

我很困惑 - 哪种方法是正确的？直觉上，第一个对我来说更有意义，但我想知道定义上的差异。其中一个定义是错误的，还是它们在某种程度上是同构的？

我有一个AdjacencyGraph<string, Edge<string>>我想运行AlgorithmExtensions.ShortestPathsDijkstra的，但 QuickGraph 文档不是最好的。

有人有我可以效仿的例子吗？

我在谷歌上找到的所有东西都使用了观察者，这AlgorithmExtension并不需要。

这是一个奇怪的问题。我正在写一本关于学习使用正式方法进行编程的书，并且我将把它针对具有一些编程经验的人。这个想法是教他们成为高质量的程序员。

基本符号将来自 Dijkstra 的Discipline of Programming，以及一些并发和通信扩展。

与 EWD 不同，我希望我的学生最终能够编写出实际的可执行程序。这意味着在某些时候将 EWD 符号转换为其他语言。当我第一次开始进行正式编程时，我的目标是 C，但你最终会编写很多管道，加上处理指针等的所有复杂性。Ruby 显然是一个可能的目标，Scheme 或 Lisp 也是如此。但也有各种功能语言；因为我对并发特别感兴趣，所以 Erlang 似乎是一种可能性。

所以，最后，这是我的问题：我应该教我的读者使用什么语言来定位他们正式开发的程序？

任何人都可以帮助我更快地实现 Dijkstra 算法的 j2ME 吗？我有两个循环，一个在另一个里面。像这样

我有将近 23000 个节点和 50000 条边连接它们......在下面提到的所有改进之后，内部循环平均执行 169330131 次。在我的 w910i 手机上完成这需要 5 分钟，而在我的模拟器上则需要几分钟以上。这对我来说太过分了。有什么改进的建议吗？我已经实施了以下改进。

1. 使用数组代替向量。
2. 确保内部循环不考虑访问节点。我所有访问过的节点都在数组的末尾，我节点知道计数。所以，我可以很容易地完全跳过它们。

从 sdk 3.0 开始可以轻松使用 iPhone 中的 GPS 功能，但明确禁止使用 Google 的地图。我认为这有两个含义：

1. 您必须自己提供地图
2. 您必须自己计算最短路线。

我知道计算最短路线多年来一直困扰着数学家，但汤姆汤姆和谷歌都做得很好，所以这个问题似乎已经解决了。在网上搜索，我自己不是数学家，我遇到了Dijkstra 算法。有没有人在 iPhone 的类似地图的应用程序中成功使用过这个算法？您愿意与我/社区分享吗？这是正确的方法，还是其他选择？非常感谢您的考虑。

这是一个学校项目；我遇到了很多麻烦，我似乎找不到可以理解的解决方案。

那就是二维数组。因此，如果您想找到最短路径，它从 a,b,e,d,z = 7 和 (a,b) = (b,a) 开始 - 它会将您带到新行以获取该行的相邻行路径

有没有人可以帮我实现这个例子的 Dijkstra 算法？我真的很感激。（我似乎最喜欢数组，地图和集合让我有点困惑，列表是可管理的——尽管我现在愿意研究任何类型的解决方案）

[至少我不只是从网络上抄袭来源。我真的很想学习这些东西......这真的很难（>.<）]

哦，起点是A，终点是Z

和大多数人一样，我认为算法的概念并不难——我只是可以看到正确的编码......请帮忙？

示例代码——一个朋友帮了我很多（尽管它充满了我发现难以理解的数据结构）我也尝试过调整来自 dreamincode.net/forums/blog/martyr2/index.php 的 C++ 代码？ showentry = 578 进入java，但这并不顺利......

Edsger Dijkstra，有时可能有点粗鲁（他称“卡尔弗里德里希高斯，数学家王子，但也有点懦夫”）在他的文章“论真正教授计算科学的残酷性”（EWD1036）中说：

这些现象中的许多都以“软件工程”的名义捆绑在一起。正如经济学被称为“悲惨的科学”，软件工程应该被称为“注定的学科”，因为它的目标是自相矛盾的，它甚至无法接近它的目标。当然，软件工程本身是另一个有价值的事业，但那是洗眼：如果你仔细阅读它的文献并分析它的拥护者实际上做了什么，你会发现软件工程已经接受了它的章程“如果你不能编程，如何编程."。

这是真的？