问题标签 [path-finding]

我们能否让人们以每种语言发布 A* 寻路算法的简单优化实现代码？

这主要是为了好玩和玩 stackoverflow 本身的能力......虽然我实际上有兴趣获得一个 ActionScript 3 版本。

但想法是，即使创建了不同的编程语言，这个“问题”也将在未来不断更新！

我不知道在网上还有其他地方可以看到伪代码“翻译”成许多（更不用说每种）不同的语言。似乎它是一个有价值的资源，虽然不一定是这个网站的设计目的，但尝试一下并看看它是否是一个可以使用 stackoverflow 的有价值的东西并没有什么坏处！

Garmin 和 TomTom 等导航系统一直让我着迷。我想实现小型地图/导航应用程序来尝试各种路径算法并扩展我对它们的了解。

这是一个两部分的问题：

1.) 地图数据如何存储？ - 当您拥有道路网络时，这些数据通常如何存储？保留哪些部分数据以便以后重现地图？每条道路是否存储为一系列改变方向的点？这些数据以何种文件格式存储？是否有公开可用的库来轻松解析这些文件？有没有人有关于如何存储/表示地图/道路数据的细节，这将非常有帮助。

2.）导航/路径 - 在此地图数据（la Garmin）上进行基本路径时，我的假设是否正确，即它被转换为有向图？每个道路交叉点是否是一个顶点，边缘加权顶点之间的距离？这就是我正在考虑做的，所以我可以尝试一些基本的众所周知的路径算法，看看我得到了什么。

我已经在美国看到了这个公开可用的地图数据，但我不确定它是如何表示的，以及它是否足够详细，让我能够从中构建我的有向图。

如果有人有任何信息，我将不胜感激。掌握的知识越详细越好。

我有大量加权节点，边缘将节点集群连接在一起。该图遵循典型的小世界布局。

我希望找到一种寻路算法，它不会消耗处理器能力，沿着最佳可能路径找到一条路径，其中节点的权重最有利，最快的路线不是最重要的因素。该算法还考虑了负载和流量重新路由。

（旁注：这里可以使用神经网络吗？）

谢谢

我在看ACO。对于这种问题，有什么比 ACO 更好的吗？

正确的A*算法在没有负载平衡的情况下找到成本最低或最快的路线。

可以说最快或最短的路线不是最重要的路线，更重要的是遵循加权节点具有一定值的路径。没有。

没有2。如果使用 A*，那条路由上的流量就会超载，那么这条路径突然就变得多余了。因此，尽管 A* 很酷，但它没有 ACO 的某些特性，即固有的负载平衡。

-- 除非我弄错和误解了 A*

那么什么比 ACO 更胜一筹？

这看起来真的像是 ACO 和 A* 之间的一场对决，关于 A* 的正面讨论太多了，我一定会更深入地研究它。

首先是对大卫的回应；我可以在后台运行 ACO 模拟并提出最佳路径，所以是的，有初始启动成本，但幸运的是，启动并不是必需的。所以我有能力多次运行模拟。一个真正的麻烦是找到连接的源节点和目标节点。而 A* 似乎很容易做到这一点。现在，当这个网络变得像数百万个节点一样大时会发生什么。A* 能否轻松扩展？

我将进一步研究 A*。但我留给你最后一个问题！

A* 能否像 Antnet (ACO) 一样扩展？

我希望处理的大型网络（小世界图类型）本质上是动态的，经常添加和减少新节点。大概使用 D* over A* 会是在这种动态环境中检测路径的更好方法？

D*有多坚固？它有任何现实世界的经验吗？就像加密算法一样——D* 是否通过大量同行评审和测试得到强化？你会用 D* 来解决这个问题吗？

我曾经发现一篇关于通过涉及烟雾（一般是流体）的模拟来寻找路径的论文。有没有人读过这样的东西？我不记得论文的名字或作者的名字。如果你知道这样的论文，请告诉我

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

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

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

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

我的数学课远远落后，我目前正在努力为我遇到的问题找到一个体面的解决方案：我有一棵树，其中的节点是动作，并且根据多个标准“加权”：所说的行动，它将花费的时间，必要的资源，干扰等......

我想在这棵树中找到最小化成本和时间的路径，或者干扰和成本和时间等。我的问题是我不知道该怎么做，除非上来使用全局成本函数 F(cost, time, resources,...)，并使用 F(...) 的结果作为我唯一的权重应用常规树遍历算法。但是，我该如何想出 F ？像“F(cost, time, resources) = a * cost + b * time + c * resources”这样的东西感觉很“不专业”......

编辑：

我想避免使用“求和”这个词，因为我不确定这是否真的是要走的路，但本质上，这就是我正在做的事情：计算来自的每个“路径”或“分支”的总成本该顶部节点，到其中一个叶子，并选择最小化成本的“路径”或“分支”。问题是每个节点都有一个基于所需时间、财务成本、资源使用等的权重。

因此，正如斯蒂芬所说，似乎不可避免地必须提出一个公式，将所有这些参数减少到每个节点的一个全局成本，然后我可以在沿树向下移动时跨节点求和，并选择路径最小化总成本。

所以我想我的问题真的是，是否有选择该功能的方法？

感谢您的回答和评论，现在我的头脑开始变得更加清晰了。

地图提供商（例如 Google 或 Yahoo! Maps）如何建议路线？

我的意思是，他们可能有某种形式的真实世界数据，当然包括距离，也可能包括行驶速度、人行道的存在、火车时刻表等。但假设数据采用更简单的格式，比如一个非常大的有向图边缘权重反映距离。我希望能够快速计算从一个任意点到另一点的方向。有时这些点会靠近（在一个城市内），而有时它们会相距很远（越野）。

像 Dijkstra 算法这样的图算法将不起作用，因为图是巨大的。幸运的是，像 A* 这样的启发式算法可能会起作用。但是，我们的数据非常结构化，也许某种分层方法可能有效？（例如，存储相距较远的某些“关键”点之间的预先计算的方向，以及一些局部方向。那么两个远点的方向将涉及到一个关键点的局部方向，到另一个关键点的全局方向，然后是局部方向再次指示。）

在实践中实际使用了哪些算法？

PS。这个问题的动机是发现在线地图方向的怪癖。与三角不等式相反，有时谷歌地图认为XZ比在XYZ中使用中间点需要更长的时间和更远的距离。但也许他们的步行方向也针对另一个参数进行了优化？

聚苯乙烯。这是对三角不等式的另一个违反，这表明（对我而言）他们使用某种分层方法：XZ与XYZ。前者似乎使用了著名的 Boulevard de Sebastopol，尽管它有点偏僻。

编辑：这些示例似乎都不再有效，但在原始帖子发布时都有效。

我正在寻找一种用于我正在制作的赛车游戏的算法。地图/关卡/轨道是随机生成的，所以我需要找到两个位置，起点和目标，以充分利用地图。

• 该算法是在二维空间内工作
• 从每一点出发，只能从四个方向穿越到下一个点；上下左右
• 点只能被阻塞或非阻塞，只能遍历非阻塞点

关于距离的计算，应该不是没有更好的词的“鸟道”。如果 A 和 B 之间有墙（或其他阻挡区域），则 A 和 B 之间的路径应该更长。

我不确定从哪里开始，非常欢迎评论，并且建议的解决方案在伪代码中是首选。

编辑：对。在查看了gs 的代码后，我又试了一次。这次我用 C++ 编写而不是 python。但是，即使在阅读了Dijkstras 算法、洪水填充和Hosam Alys 解决方案之后，我仍然没有发现任何关键的区别。我的代码仍然有效，但没有你看起来运行的那么快。完整的源代码在paste上。唯一有趣的行（我猜）是第 78-118 行的 Dijkstra 变体本身。

但速度不是这里的主要问题。如果有人愿意指出算法中的差异，我将非常感谢您的帮助。

• 在 Hosam Alys 算法中，他从边界而不是每个节点扫描的唯一区别是什么？
• 在 Dijkstras 中，您跟踪并覆盖步行距离，但不是在洪水填充中，但仅此而已？

我有各种表面为 3D 且非矩形的对象，例如球体、金字塔以及由网格表示的各种其他对象。网格不是由相同大小和分布在对象表面上的多边形组成，它们也不是像圆柱体、球体和圆锥体的理想形状那样都是半/对称的对象。

因此，我将如何设计或改进一种寻路算法，该算法采用任意网格并生成可以以多种方式环绕自身的节点？