问题标签 [a-star]

我正在尝试为一个名为 Twiddle 的小益智游戏找到最佳解决方案（可以在此处找到带有该游戏的小程序）。游戏有一个 3x3 矩阵，数字从 1 到 9。目标是使用最少的移动量以正确的顺序排列数字。在每次移动中，您可以顺时针或逆时针旋转 2x2 正方形。

即如果你有这个状态

然后顺时针旋转左上角 2x2 正方形

我正在使用 A* 搜索来找到最佳解决方案。我的 f() 只是所需的旋转次数。我的启发式函数已经得出了最佳解决方案（如果我修改它，请参阅最后的通知），但我认为它不是你能找到的最好的解决方案。我当前的启发式方法获取每个角落，查看角落的数字并计算到该数字在已解决状态下的位置的曼哈顿距离（这给了我将数字带到这个位置所需的旋转次数）并将所有这些价值观。即你举上面的例子：

和这个最终状态

然后启发式执行以下操作

此外，如果 h 为 0，但状态不是完全有序的，则 h = 1。

但是有一个问题，你一次旋转 4 个元素。因此，在极少数情况下，您可以一次完成两个（或更多）这些估计的旋转。这意味着论文启发式高估了解决方案的距离。

我目前的解决方法是，从至少为我的测试用例解决这个问题的计算中简单地排除一个角。如果真的解决了问题，或者这种启发式方法在某些极端情况下是否仍然高估，我没有进行任何研究。

所以我的问题是：你能想出的最好的启发式方法是什么？

（免责声明：这是一个大学项目，所以这是一个家庭作业。但我可以随意使用任何资源，如果可以的话，所以可以问你们。我也会感谢 Stackoverflow 对我的帮助； ) )

在计算 1 个图块的移动时，是否会导致其他图块达到其目标状态，这不是真的吗？因此，计算每个图块可以让我们获得比达到目标状态所需的最小移动次数更多的计数？

这个问题是在 15-Puzzle 的曼哈顿距离的背景下。

这是不同的问题：

我们可以使用曼哈顿距离作为 N-Puzzle 的可接受启发式算法吗？为了实现 A* 搜索，我们需要一个可接受的启发式算法。曼哈顿启发式是候选人吗？如果是，您如何反驳上述论点（问题的前 3 句话）？

定义： A*是一种搜索算法。它使用启发式函数来确定到目标​​的估计距离。只要这个启发式函数从不高估到目标的距离，算法就会找到最短路径，可能比广度优先搜索更快。满足该条件的启发式是可接受的。

免责声明：我几乎没有 Java 背景，因为我主要是 C# 开发人员。

想要A*算法的java实现。
是的，我在网上看到了很多相同的版本，我无法在它们之间进行选择。

我正在寻找一种 A* 算法实现，它使用 java 的所有新功能，使算法更快（即使有点）。原因是我们正在实现路径查找MMO，因此性能是重中之重。

任何指针（至少在哪里看）？

我已经在 C# 中成功实现了 A* 寻路，但是速度很慢，我不明白为什么。我什至尝试不对 openNodes 列表进行排序，但它仍然是一样的。

地图为 80x80，有 10-11 个节点。

我从这里Wikipedia获取了伪代码

这是我的实现：

这是我正在使用的启发式方法：

我究竟做错了什么？我整天都在看相同的代码。

我正在阅读有关 dijkstra 算法和 A* 星算法的信息。我知道区别在于使用的启发式方法。但是什么是启发式方法以及它如何影响算法？启发式只是一种测量距离的方法？但是dijkstra也考虑距离吗？抱歉，但我的问题是关于启发式及其含义以及为什么要使用它们......（我已经阅读过它，但不明白） 其他问题：每个人应该什么时候使用？

谢谢

这是我的场景。我想实现 A*（在 Python 中），而不必求助于线性时间最小值或操作。我需要一个堆才能有效地获得重量最低的物品。

我的第一反应是‘简单！我将使用 heapq！然后我发现生活很少像我们希望的那样简单。事实证明，这种策略对于 A* 的关键点之一不是最优的。当考虑孩子时，我需要偶尔更新已经在堆上的孩子的分数。

对于那些对 A* 的记忆有一点点流失的人来说，它的要点是我想取一个元素，修改它的权重，并修改堆以反映变化，所有这些都在亚线性时间内完成。

有什么建议么？

有人在 PHP 中实现了A* 算法吗？我知道维基百科有一个伪代码和一个 C++ 的链接，但我似乎找不到一个已经用 PHP 编写的。

我也在寻找一种高效的书面 A* 算法

这是我从这里的站点获得的代码，我想知道 A* 的这种实现是否正确。我已经查看了它并将其与维基百科页面进行比较，它似乎是有效的。我问的原因是因为在该站点中它说此代码中仍然存在错误，我尝试找到它但找不到任何错误。我想更改它，以便将起点和终点作为输入参数

Pqueue 的代码可以在这里找到

如果我有一组坐标为 (x, y) 的节点并且我有一组节点 - 节点 - 成本，在这种情况下，成本以分钟为单位。假设速度恒定，我如何计算欧几里得距离...

一个指标以分钟为单位，而使用 x,y 的距离不是时间指标

I have a set data which is a collection of node - node - associated cost. This cost is represented as a distance in feet.

I also have a x-y-coordinate for each node. Now in the A* algorithm I will need to add the cost from node to node + the heuristic cost from the middle node to the destination. However, these two values needs to be having the same metric/unit. I can't have one in feet and the other one in coordinate distance.

I know that in order to do this I first need to find a scaling factor, to scale the cost from feet to x-y-coordinate distance. Right? All I can say is that all this cost is scalable. So this beta value will be the same for all pair of node-node.. Question is how do I find this value?

What I've done right now is to find the coordinate distance between node - node and then from that compare with the cost in feet. And I can therefore find a beta, which is a constant and should work for every node-node-cost (feet)... I am not sure if this is true though. I am not looking for a magic trick here, just a simple way/math to solve this