问题标签 [a-star]

我似乎要么失去理智，要么错误地实现了 A* 算法：

下面是我的代码，似乎无论我输入什么值，它总是会返回 360。我在这里遗漏了一些关键信息吗？同样在有人问是之前，这与我收到的机器学习作业有关。

公共类 A_Star {

}

和

公共类 SearchNode {

public SearchNode(int cost, int xCoordinate,int yCoordinate){
this.cost=cost;
this.xCoordinate =xCoordinate;
this.yCoordinate = yCoordinate;
}
public int getCost() { 返回成本；}

}

我编写了我的第一个稍微复杂的算法，A Star Pathfinding算法的实现。我遵循了一些关于实现图形的Python.org 建议，因此字典包含每个节点也链接的所有节点。现在，由于这一切都是为了游戏，每个节点实际上只是节点网格中的一个图块，因此我是如何制定启发式方法和偶尔引用它们的。

多亏了 timeit，我知道我可以每秒成功运行这个函数一百多次。可以理解的是，这让我有点不安，因为没有任何其他“游戏内容”，比如图形或计算游戏逻辑。所以我很想看看你们中的任何人是否可以加快我的算法，我完全不熟悉 Cython 或它的亲戚，我不能编写一行 C。

废话不多说，这是我的 A Star 函数。

我正在尝试从维基百科的伪代码中实现 A*，但是我得到了一些奇怪的结果。

该实现找到了最初看起来不错的路径，但进一步看，它总是产生相同的路径！

任何人都可以发现任何问题吗？代码用 python 3.1 编写并使用 pygame。

我真的不知道，因为我认为我已经逐句实现了伪代码语句。

这里也是一个截图： http ://andhen.mine.nu/uploads/astar.dib

谢谢！

我正在尝试实现 A* 搜索算法。现在我只是想在一个到处都是墙壁的环境中找到一条好路。墙壁是随机生成的，在某些情况下，我的路径会“卡住”。如果搜索在它前面遇到一堵墙，并且在它的所有侧面（除了把它带入这个烂摊子的那一面），它就会停止。我能做些什么来防止这种情况发生吗？我正在为我的 H 值使用“如乌鸦飞”点系统，它忽略了墙壁，只是估计到达目的地需要多远。这有时会导致它陷入这个陷阱。

谢谢。

我的任务是编写 A* 算法（提供启发式算法）的实现，以解决旅行商问题。我了解算法，它很简单，但我看不到实现它的代码。我的意思是，我明白了。节点的优先级队列，按距离 + 启发式（节点）排序，将最近的节点添加到路径上。问题是，如果不能从前一个最近的节点到达最近的节点会发生什么？一个人实际上如何将“图形”作为函数参数？我只是看不到算法实际上是如何运作的，就像代码一样。

在发布问题之前，我阅读了维基百科页面。反复。它并没有真正回答这个问题——搜索图表是一种方式，与解决 TSP 方式不同。例如，您可以构建一个图，其中任何给定时间的最短节点总是导致回溯，因为两条相同长度的路径不相等，而如果您只是尝试从 A 到 B，那么两条路径相同的长度是相等的。

您可以得出一个图表，通过始终最接近的方式永远无法到达某些节点。

我真的不明白 A* 如何适用于 TSP。我的意思是，找到从 A 到 B 的路线，当然，我明白了。但是TSP？我没有看到联系。

存在哪些与 Dijkstra 概念不同的路由算法？

Dijkstra（和 A*、D*、bellman forge 等）使用这个概念：从已知节点中获取最佳节点，展开并将结果保存到已知节点。

有没有根本不同的概念？

您如何在图形搜索类中构建图形/节点？我基本上是在创建一个 NavMesh，需要生成从 1 个多边形到另一个多边形的节点。连接两个多边形的边将是节点。

然后我将在这些节点上运行 A* 来计算最短路径。我只需要知道如何构建我的类及其属性？

我确信我不需要用节点和边创建一个完全成熟的无向图。

我在这里找到了这个算法。

我有一个问题，我似乎无法理解如何设置和传递我的启发式函数。

如您所见，它接受 2 个函数，一个距离和一个估计函数。

使用曼哈顿启发式距离函数，我需要采用 2 个参数。我是否需要修改他的源并将其更改为接受 TNode 的 2 个参数，以便我可以将曼哈顿估计值传递给它？这意味着第 4 个参数将如下所示：

并将估计函数更改为：

我的曼哈顿功能是：

我目前正在使用 A* 寻路算法来计算无限网格上的路径（使用 Gridworld 中的 UnboundedGrid，AP CS 案例研究，如果对任何人有帮助的话）。一切都很好，除了因为末端节点完全被墙包围而没有有效路径的情况。正如预期的那样，算法继续无限搜索，永远找不到结束节点。

一个可能的解决方案是在整个寻路区域周围放置不可见的（如用户看不到但算法看到的）墙，确保开始节点、结束节点和所有墙节点都在这些范围内墙壁，有2-3个空格填充左右。就像是：

...想法是最终所有节点都将添加到封闭列表中，开放列表将变为空，此时我将知道不存在有效路径。

这似乎是解决问题的合理方法吗？有什么方法可能会出错吗？我知道另一种解决方案是同时从末端向后寻路，但这似乎可能很昂贵，特别是在末端节点没有那么紧密封闭的情况下。

我从这个A* 教程中获取了这个数据结构：

我不知道如何创建一个简单的图表。

如何使用 C# 添加类似以下无向图的内容：

基本上我想知道如何连接节点。我有自己的数据结构，我已经可以确定邻居和距离。我现在想把它转换成这个张贴的数据结构，这样我就可以通过 AStar 算法运行它。

我正在寻找更多类似的东西：