问题标签 [a-star]

我必须得到 2D 中两点之间的（最短）/（最佳）距离。我必须避免可能连接在一起的线条形状。关于如何表示我可以旅行的节点有什么建议吗？我曾想过制作一个网格，但这听起来不太准确或优雅。如果一条线的任何点在正方形内（节点是正方形的中心），我会认为一个节点是不可行走的。

一个例子是从 A 点到 B 点。

网格是解决此问题的推荐方法吗？提前非常感谢！

我已经开始研究算法和软件开发，作为一个小型的自我评估项目，我决定用 C++ 编写 A* 搜索算法。它使用 Qt 和 OpenGL 作为视觉部分（但这并不重要）。

主要使用这个来源： A* Pathfinding for Beginners

我写了一个小应用程序，但是我发现了一个我无法修复的错误。似乎由于某种原因，靠近墙壁的节点的父节点设置为墙壁。（？）由于我存储信息的方式，墙壁的父节点设置为起点（？）。

我使用了 stateMatrix[][] 其中

我还使用矩阵来表示 openNodes 和 closedNode。closedNodes 矩阵是 bool 矩阵，openNode 矩阵还存储一些信息：

openNodes 指令是：

我知道有更好的方法来编码，但我还没有上过这节课；）

这是astar文件的代码：

有谁知道我做错了什么？

谢谢。编辑：这里有一些图片：

我尝试在 java 中创建 A* 算法，但我遇到了这个奇怪的错误。我知道 A* 并不总能找到最佳路径，但在这里它似乎违背了理性并选择了更糟糕的路径，而且我在代码中找不到导致此问题的错误。它似乎在我创建的其他地图上找到了最佳解决方案。这是错误的图片和节点的打印输出

http://i.imgur.com/IudT7.png

这是我使用的（部分）代码。

我的 A-star 实施存在问题。它确实找到了从我的点 A 到 B 的路径，但如果地形更“复杂”，那么我的 Find() 函数似乎没有结束。例如，它确实适用于此处的 20 x 20 阵列，但如果您在底部添加一个正方形 ('#') 到最右侧的障碍物/墙，则它会失败。

我希望有人能指出我正在做的任何错误。这是我的代码：

我的 A* 算法实现需要一些帮助。当我运行算法时，它确实找到了目标，但路径肯定不是最短的：-P

这是我的代码，请帮我找出错误！我认为这可能是我的问题的重建路径，但我不确定。

}

感谢大家的所有伟大的答案！感谢你们，我的 A* 算法现在可以完美运行！:-)

这是我的第一篇文章，这个论坛真的很棒！

我的 AS3 A* 寻路实现有时不会返回最有效的路线，就像这样：

（其中 . 是经过的节点，X 是墙壁。S = 开始，E = 结束，i = 我的假想标记）

问题：我的总分应该是（到结束的距离）30 +（到开始的距离）10 = 40，而我上面的图块的总分应该是（到结束的距离）40 +（到开始的距离）14 = 54。为什么选择 54 而不是 40，我不知道 - 我用它来查找打开列表中总分最低的节点：

（我看不出有任何问题。）

我想，也许这是我计算到最后的距离的错误。所以我检查了我的代码：

（我也看不出有任何问题。）

我真的很难过。

Main.as: http://pastebin.com/ZKQJwY4S PathSearcher:as: http://pastebin.com/KnmWGbQw

（我知道直接贴出问题代码比较好，但是不知道问题代码在哪里：（对不起）

谢谢你的帮助！

我有一个我正在尝试使用 Java 完成的任务，但我对如何设置/下图的节点是什么感到困惑。基本上，它是笔式绘图仪问题，或者更常见的旅行商问题。我的以下输入是：

我的输出结果如下：

假设这张纸的左下角是你的起点（0,0），它的坐标上升，每个坐标都是一个节点，我将如何确定何时移动和画一条线。我知道我应该使用带有 A* 的无向图，但我仍然对哪些是节点（顶点）以及如何确定何时移动以及何时绘制线条感到很困惑，有人能给我一些建议吗？

编辑：请注意，指的是在整个搜索过程中探索的节点数量/数量。

我正在实现 A* 搜索算法，但我一直遇到优先级队列的问题。根据这篇文章，我已经为优先级队列实现了一个自定义比较器

这是相关代码：

调用堆栈：

使用了更大的然后，因为我需要这个算法的最小堆。该实现似乎工作正常，并且当它在发布模式下运行时问题就消失了，但是当优先级队列被 pop() 时，优先级队列偶尔会在调试模式下抛出“无效堆”断言失败。

我不熟悉 stl 中的 binary_function，但问题似乎出在比较器上。删除比较器或将符号更改为 less 可以消除错误，但这会给我一个最大堆。有什么我想念的吗？

我正在尝试在 python 中实现 A* 算法，但在尝试查找此地图的路径时遇到了问题：

我正在使用曼哈顿方法。我的实现确实找到了一条路径，但不是最短的。错误开始于它的第二步——向右移动之后。此时它可以向上移动，启发式成本将是四（三右，一下）或向下（三右，一上）。有没有办法让它选择最短路径？

代码：