问题标签 [a-star]

在 A* 中，您得到的结果通常只有一条路径。根据 A*，给定的起点和终点是否有可能有 3 条推荐路径？所以返回的第二个是第二好的路径，第三个是第三好的路径..

我在想也许以某种方式修改启发式以反映第二和第三个最佳路径。你们怎么看？

更新： 我的实现是在 PHP 中，我使用的是封闭集。因此，如果有办法做到这一点，请告诉我。

我目前正在研究 A* 寻路，但我遇到了一些问题。在采取最佳路径之前，它会走错路。我究竟做错了什么？

源代码：http ://basic.apayostudios.com/AStar.zip

在线的：

Game.cs http://pastie.org/1656955

Node.cs http://pastie.org/1656956

枚举：

谢谢！

可能重复：
使用 A* 解决旅行商问题

我最近了解到A*算法可以应用于旅行商问题。Bot 我们如何在这里定义起点和目标，以及我们如何将权重应用于节点（什么是启发式）？

有人可以向我解释如何在这里应用 A* 吗？

我编写了一些 C++ 代码来查找 A* 路径，但它的行为很奇怪。这里有相当多的代码，所以我将它分成块并尝试解释我在做什么。我不会解释 A* 路径是如何工作的。我假设如果你想帮助你已经知道算法。

首先，这是我计算节点 h 值的函数：

我很确定这里没有问题；很简单的东西。

接下来是我的 Node 类。而且我知道，我知道，将这些变量设为私有并使用 getter；我只是出于测试目的这样做。

每个节点都有一个 X 和 Y 变量。我只存储 G 和 H，而不是 F，并在需要时计算 F（这在我的代码中只有一次）。然后是父 X 和 Y 值。List 是一个布尔值：fale = 打开列表，true = 关闭列表。

我也有一个对象类。这里唯一重要的变量是 X、Y 和 Passable，它们都通过 getter 访问。
现在这是我实际寻路代码的开始。它返回一串对应方向的数字，如下所示：
432
501
678
所以1表示向右移动，8表示向下和向右，0表示不去任何地方。

现在我们循环直到找到目的地。请注意， sizeLimit 只是为了确保我们不会永远循环（如果我可以修复此代码，它将不会。到目前为止，这是非常必要的）。从这一点开始，除非我另有标记，否则一切都在 ij 循环内。

下一部分：

继续：

这是 ij 循环的最后一部分：

现在我们找到 F 分数最低的 Node，将其更改为当前节点，并将其添加到关闭列表中。防止无限循环的保护也在这里完成：

我遇到的问题是它找不到某些路径。如果路径在任何时候上升或离开，它似乎永远不会起作用。向下，向左和向右都可以正常工作。反正大多数时候。我完全不知道是什么导致了这个问题；有一次，我什至尝试手动按照我的代码查看问题出在哪里。没有奏效也就不足为奇了。

还有一件事：如果你在数我的花括号（首先哇，你比我想象的更投入），你会注意到我最后缺少了一个大括号。更不用说我的退货声明了。最后有一点代码来实际制作我遗漏的路径。我知道那部分不是问题。我目前已将其注释掉，但它仍然不能以相同的方式工作。我添加了一些代码来告诉我它在哪里不起作用，它在寻路部分，而不是解释。

对不起，我的代码如此混乱和低效。我是 C++ 新手，因此也欢迎对我的技术提出任何批评意见。

我面临一个优化问题：

我有一个带有很多节点（10^5）的图，它们代表平面上的点。

我需要在图表上找到最短路径才能到达“结束节点”，从“开始节点”开始。

任何一对节点都可以连接或不连接。检查它们是否已连接是一项非常昂贵的操作。如果它们是连接的，则与链接相关的权重是两个节点之间的欧几里德距离。

目前我只检查从“当前节点”到每个其他节点的所有链接，以填充 A* 的“打开列表”。我选择了 A*，因为它似乎是寻路中最好的算法，而且我对节点 J 有一个快速、可接受且简单的启发式 H（H = 到目标的距离），但我不确定它是否对我的问题有好处。

预先构建图表是无法管理的，需要检查 N^2 个链接，它太慢了。目前（几乎）只有在没有解决方案、没有从开始到结束的路径的情况下才会构建整个图。

我想要一个更好的解决方案的提示......谢谢！

我注意到我遇到的一些“硬”组合问题可以用某种类型的树搜索（如 alpha-beta 剪枝、束搜索或类似算法）进行转换。 然而，对它们进行编程似乎是重复编码相同的东西，而且很容易出错。在我看来应该有一个实现这些算法的库，而我应该被要求写的是

1. 解决方案的编码，即如何从不完整的解决方案中获得更具体的解决方案。这将给出树/图结构。
2. 给定一个部分解决方案，如何获得最大/最小成本，以及可能的成本估算。
3. 初始解决方案/部分解决方案。
4. 也许某种验证解决方案。

很抱歉我没有给出任何具体的代码，但我想我已经解释了这个问题。如果我可以为上述功能编写代码，我是否应该能够轻松地运行许多树/图搜索算法？是否有任何用户友好的库/框架可以轻松支持这一点？我希望它使用 Python 或 C/C++，但很想听听任何建议。

编辑：更准确地说，我说的是知情树搜索算法。

我正在用星算法做 8 个谜题求解器。我在这个求解器中实现了曼哈顿和错位的启发式函数。在某些情况下，求解器可以正常工作。但在某些情况下，找到解决方案需要花费大量时间。我认为我的问题之一是在打开列表中查找具有最低值的节点的函数（等待扩展）。

那么找到最低 f_score 值的最佳方法是什么？只需找到最小值，否则我们必须在有状态要添加时修改列表（添加状态时对列表进行排序），以便最小值将位于第一个位置。

我整天都在努力让这个算法启动并运行，但我一辈子都做不到。我在网上阅读了很多教程，以及AS3、javascript和C++的源代码；但我无法将我所看到的内容适应我自己的代码。

我创建了一个 AStar 类，它有一个名为 Node 的嵌套类。该地图是一个名为 MAP 的二维数组。

我遇到的最大问题是在寻路函数中提取 F 值。

我已经实现了 F = G + H，我的问题是实际的 AStar 算法。有人可以帮忙吗，这是我到目前为止的进展：

这是我使用探路者功能所能获得的最远距离：

您有一张方形瓷砖地图，您可以在其中向 8 个方向中的任何一个方向移动。假设你调用了一个函数cost(tile1, tile2)，它告诉你从一个相邻的瓦片移动到另一个瓦片的成本，你如何找到一个既可接受又一致的启发式函数 h(y,goal)？给定这个设置，寻找启发式的方法是否可以概括，或者它会根据cost功能而有所不同？

我目前正在为研究生代理论文做一个项目。对于我的项目，我有一个想法，可以随时扩展搜索，例如 ARA* ADA* 和 DLite*。我想通过在机器人上模拟来测试这个想法。在过去的几个晚上，我一直在寻找不同的软件，但没有运气。

最终，我需要一个有机器人的东西，它可以随时以离散的方式提供以下信息：

坐标 (x,y,z) 速度

我还需要机器人有某种方式从其环境中收集坐标，例如拥有一个红外扫描仪，它将用（可通过/不可通过）映射 x、y 坐标。

最后，我需要能够在算法中编程，这些算法将使用环境信息来建议在到达目标坐标的路径中要通过哪些状态。

我的问题是是否有软件可以让我轻松实现所有这些。我不想花超过 7 个晚上的时间来编写这个程序，理想情况下，我希望在一两个晚上内获得一些可见的结果。

我为我的论文编写了很多启发式搜索算法（即周界搜索、BiMaxf、BS*、A*、我自己的双向搜索算法以及一些从前到前的搜索）所有这些都基于 8/ 15 个谜题，可以在几秒钟内用 Java 解决相当困难的问题。我很喜欢使用 C 语言或脚本语言，因为我需要的只是 ADT 的哈希表和优先级队列。

那么是否有任何开源软件可以让我（实时）轻松地实现模拟。如果没有，创建我自己的模拟器听起来不可能吗？如果我要这样做，那么它很可能只是一个 2D 模拟器，它知道给定半径内的周围环境......在已经存在的东西上做它会很好，因为实验不会（如）有偏见...