问题标签 [a-star]

我发现 AIMA（人工智能：现代方法）中的算法描述根本不正确。“必要”是什么意思？内存限制是多少？队列大小或处理的节点？如果当前节点根本没有子节点怎么办？

我想知道这个算法本身是否正确。因为我搜索了互联网，还没有人实现它。

谢谢。

我正在尝试为15 方拼图构建A* 求解器。

目标是重新排列图块，使它们出现在其自然位置。您一次只能滑动一个图块。拼图的每个可能状态都是搜索图中的一个节点。

对于 h(x) 函数，我在所有图块中使用图块与目标状态的错位的总和。在上图中，5 位于位置 0,0，它属于位置 1,0，因此它对 h(x) 函数的贡献为 1。下一个图块是 11，位于 0,1，属于 2,2，因此它对 h(x) 的贡献为 3。等等。编辑：我现在明白这就是他们所说的“曼哈顿距离”或“出租车距离”。

我一直在使用 g(x) 的步数。在我的实现中，对于状态图中的任何节点，g 只是前一个节点的 g 的 +1。

为了找到连续的节点，我只是检查我可以在拼图中移动“洞”的位置。显示的拼图状态（又名节点）有 3 个邻居：洞可以向北、向西或向东移动。

我的 A* 搜索有时会在 20 秒内收敛，有时会在 180 秒内收敛，有时根本不会收敛（等待 10 分钟或更长时间）。我认为 h 是合理的。我想知道我是否正确地模拟了 g 。换句话说，我的 A* 函数是否有可能通过不是最短路径的路径到达图中的节点？

也许我没有等待足够长的时间？也许10分钟还不够长？

对于完全随机排列（假设没有奇偶性问题），A* 解决方案将检查的平均排列数是多少？（请显示数学）

我将在我的代码中查找逻辑错误，但与此同时，有什么提示吗？

（ps：它是用Javascript完成的）。

另外，不，这不是 CompSci 作业。这只是个人探索的事情。我只是想学习 Javascript。

编辑：我发现运行时间高度依赖于启发式。我从某人提到的文章中看到了应用于启发式算法的 10 倍因子，这让我想知道 - 为什么是 10 倍？为什么是线性的？因为这是在 javascript 中完成的，所以我可以修改代码以使用当前正在考虑的节点动态更新 html 表。这让我可以看到算法的进展。使用常规的出租车距离启发式，我看着它未能收敛。

顶排有 5 个和 12 个，他们一直在附近闲逛。我会看到 1,2,3,4 爬到顶行，但随后他们会退出，其他数字会向上移动。我希望看到的是 1,2,3,4 爬到顶部，然后呆在那里。

我心想——这不是我个人解决这个问题的方式。手动执行此操作，我解决了第一行，然后是第 2 行，然后是第 3 和第 4 行。

因此，我调整了 h(x) 函数以更重地加权较高的行和“左侧”列。结果是 A* 收敛得更快。它现在在 3 分钟内运行，而不是“无限期”运行。通过我所说的“窥视”，我可以看到较小的数字爬到较高的行并留在那里。这不仅看起来是正确的，而且运行得更快。

我正在尝试一系列变化。很明显，A* 运行时对启发式非常敏感。目前我发现的最好的启发式方法使用 i 和 j 的总和， dislocation * ((4-i) + (4-j))其中 i 和 j 是行和列，错位是出租车距离。

我得到的结果中有一个有趣的部分：使用特定的启发式方法，我很快就找到了一条路径，但这显然不是最短路径。我认为这是因为我正在加权启发式。在一种情况下，我在 10 秒内获得了 178 步的路径。我自己的手动工作在 87 步中产生了一个解决方案。（远远超过 10 秒）。有必要进行更多调查。

所以结果是我看到它收敛得更快，而且路径肯定不是最短的。我必须更多地考虑这一点。

代码：

我有几个关于在图表/树中搜索的问题：

假设我有一个空棋盘，我想将棋子从 A 点移动到 B 点。

A. 当使用深度优先搜索或广度优先搜索时，我们必须使用开放列表和封闭列表吗？这是一个包含所有要检查的元素的列表，以及已经检查过的所有其他元素的列表？甚至可以在没有这些列表的情况下做到这一点吗？A*呢，需要吗？

B. 使用列表时，找到解决方案后，如何获得从 A 到 B 的状态序列？我假设当您在打开和关闭列表中有项目时，不仅仅是具有 (x, y) 状态，而是具有由 (x, y, parent_of_this_node) 形成的“扩展状态”？

C. 状态 A 有 4 种可能的移动方式（右、左、上、下）。如果我先左移，我应该让它在下一个状态回到原来的状态吗？这，就是，做“正确”的举动吗？如果不是，我是否必须每次都遍历搜索树以检查我去过哪些州？

D. 当我在树上看到我已经去过的状态时，我是否应该忽略它，因为我知道这是一条死胡同？我想要做到这一点，我必须始终保留访问状态的列表，对吗？

E. 搜索树和图有什么区别吗？它们只是看待同一事物的不同方式吗？

有这么多可用的实现，使用小网格的 C++ 执行速度最快（CPU 密集度最低、二进制文件最小）、跨平台（Linux、Mac、Windows、iPhone）的 A* 实现是什么？

实现

谷歌返回：

• http://www.heyes-jones.com/astar.html（该站点上的大多数链接都已失效。）
• http://www.grinninglizard.com/MicroPather（据说比 Heyes-Jones 慢。）
• http://www.ceng.metu.edu.tr/~cuneyt/codes.html（通用 C++ 代码。）
• http://swampthingtom.blogspot.com/2007/07/pathfinding-sample-using.html
• http://opensteer.sourceforge.net/（对游戏感兴趣，不是 A*。）
• Dijkstra 算法的堆栈溢出

还有其他人吗？

车轮

正如所问的那样，这个问题涉及重用（插入游戏），而不是重新发明（至少在性能被证明是一个问题之前）。结果可能是 Dijkstra 实现（或通用寻路算法）更适合，或者最快的实现不够快。我很欣赏替代算法的建议，但问题不是“我应该自己滚动 A* 吗？”

• 乔尔谈软件——不是在这里发明的综合症
• 编码恐怖：不要重新发明轮子
• 克服“这里没有发明综合症”

哪种方法可以在 C# 中简单实现 A*（A 星）算法？

我有一段时间专注于机器人的运动规划，并且有一段时间想探索利用“势场”方法提供的机会的可能性。我的挑战是避免机器人在使用“势场”方法时陷入“局部最小值”。我没有使用“随机行走”方法来避免机器人被困，而是考虑是否有可能实现 A* 的变体，它可以作为一种精确避免机器人被困在“局部最小值”。

有没有这种经验，或者可以参考文献，比“随机游走”的方法更有效地避免了局部最小值。

对于实习，我在以下情况下使用了 A* 算法：

• 单位形状是一个高度和宽度为1的正方形，
• 我们可以从一个由另一个矩形表示的区域旅行，但我们不能在这些预先定义的区域之外旅行，
• 我们可以通过一扇门从一个矩形到另一个矩形，由相应正方形边缘上的一条线段表示。

以下是我已经做过但没有让我的老板满意的两件事：

1：我创建了以下类：-a Door 类，其中包含 2 个分隔正方形的位置和门的方向（上、左、下、右），-a Map 类，其中包含门列表，矩形列表表示可步行区域和表示地面方格的 2D 数组（用于通过枚举获取附加信息） - A* 算法的类（节点、AStar）

2 : -a MapCase 类，通过枚举包含有关案例效果和门的信息（设置了 [FLAGS] 属性，以便能够累积每个案例的多个信息） -a Map 类，仅包含 2D 数组MapCase 类 - A* 算法的类（仍然是 AStar 节点）。

由于 2 版本比第一个更好（无用计算更少，映射类架构更好），所以我的老板对我的映射类架构仍然不满意。

A* 和节点类很好并且易于维护，所以我认为我现在不必更深入地解释它们。

所以这是我的问题：有没有人用问题规范（矩形可步行但单位面积为正方形，穿过门）来实现 A* 的好主意？

他说问题的网格视觉（所以二维数组）不应该是解决问题的正确方法。

我希望我在暴露我的问题时已经清楚了..

谢谢

风筝

我正在尝试创建一种方法（使用 *A** 算法）来解决难题并将步骤返回到该解决方案。解决方案很简单..但我无法返回路径。

我使用了一个节点列表，然后每次推回一个新节点时，我都会将父节点设置为指向新节点的父节点；

类节点就是这样

但后来我意识到我无法建立解决难题的道路......

我什至看不到一个父板...

我已经在互联网上搜索了所有内容，但我无法意识到我做错了什么:(

我也试过这个，但它会导致 VS2005 崩溃。

//目标是方法Solve返回的打开列表....

我试图更清楚和客观。所以...看到这个部分

getLowestCostPath 方法返回的值来自：

在那之后......关于方法Solve..有这部分代码

我认为它在这部分的错误，它指向t当它应该指向打开的列表上的节点时

这是真的吗？如果是..我该如何解决这个问题？

我使用自己的 A* 实现穿越了一个 16x16 的迷宫。

一切都很好。然而，在遍历之后，我想知道哪面墙会给我最好的替代路径。除了在迷宫中移除每个块并重新运行 A*，还有什么更聪明和优雅的解决方案？

我在想给每个墙节点（被 A* 忽略）一个暂定的 F 值，并将节点结构更改为也有一个 n 大小的列表，node *tentative_parent其中 n 是迷宫中的墙数。这可能可行吗？

如果将游戏地图划分为子图，如何最小化子图之间的边？

我有一个问题，我试图通过像 pacman 或 sokoban 这样的基于网格的游戏进行 A* 搜索，但我需要找到“附件”。我说的外壳是什么意思？给定作为软约束的每个子图的顶点数的最大尺寸和最小尺寸，具有尽可能少的切割边的子图。
或者你可以说我正在寻找子图之间的桥梁，但它通常是同样的问题。

例子

基于网格的游戏地图示例 http://dl.dropbox.com/u/1029671/map1.jpg

给定一个看起来像这样的游戏，我想做的是找到外壳，这样我就可以正确地找到它们的入口，从而获得一个很好的启发式方法来到达这些外壳内的顶点。

替代文字 http://dl.dropbox.com/u/1029671/map.jpg

所以我想要的是在任何给定的地图上找到这些彩色区域。

我的动机

我之所以费心这样做，而不仅仅是满足于简单的曼哈顿距离启发式的性能，是因为封闭启发式可以提供更优化的结果，而且我不必实际执行 A* 来获得一些适当的距离计算和也用于以后在玩推箱子类型游戏时在这些围栏内增加对手的竞争性阻挡。此外，封闭启发式可用于极小极大方法，以更正确地找到目标顶点。

可能的解决方案

该问题的一个可能解决方案是Kernighan Lin 算法：

我对这个算法的问题是它的运行时间为 O(n^2 * lg(n))，我正在考虑将 A1 和 B1 中的节点限制在每个子图的边界，以减少完成的工作量。

我也不理解算法中的 c[a][b] 成本，如果 a 和 b 之间没有边是假定为 0 或无穷大的成本，或者我应该根据一些启发式方法创建边。

你知道当 a 和 b 之间没有边时 c[a][b] 应该是什么吗？您认为我的问题适合使用多级方法吗？为什么或者为什么不？您对如何减少使用 kernighan-lin 算法完成我的问题的工作有一个好主意吗？