目标是重新排列图块，使它们出现在其自然位置。您一次只能滑动一个图块。拼图的每个可能状态都是搜索图中的一个节点。
对于 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 秒）。有必要进行更多调查。
所以结果是我看到它收敛得更快，而且路径肯定不是最短的。我必须更多地考虑这一点。
代码：
var stop = false;
function Astar(start, goal, callback) {
// start and goal are nodes in the graph, represented by
// an array of 16 ints. The goal is: [1,2,3,...14,15,0]
// Zero represents the hole.
// callback is a method to call when finished. This runs a long time,
// therefore we need to use setTimeout() to break it up, to avoid
// the browser warning like "Stop running this script?"
// g is the actual distance traveled from initial node to current node.
// h is the heuristic estimate of distance from current to goal.
stop = false;
start.g = start.dontgo = 0;
// calcHeuristic inserts an .h member into the array
calcHeuristicDistance(start);
// start the stack with one element
var closed = []; // set of nodes already evaluated.
var open = [ start ]; // set of nodes to evaluate (start with initial node)
var iteration = function() {
if (open.length==0) {
// no more nodes. Fail.
callback(null);
return;
}
var current = open.shift(); // get highest priority node
// update the browser with a table representation of the
// node being evaluated
$("#solution").html(stateToString(current));
// check solution returns true if current == goal
if (checkSolution(current,goal)) {
// reconstructPath just records the position of the hole
// through each node
var path= reconstructPath(start,current);
callback(path);
return;
}
closed.push(current);
// get the set of neighbors. This is 3 or fewer nodes.
// (nextStates is optimized to NOT turn directly back on itself)
var neighbors = nextStates(current, goal);
for (var i=0; i<neighbors.length; i++) {
var n = neighbors[i];
// skip this one if we've already visited it
if (closed.containsNode(n)) continue;
// .g, .h, and .previous get assigned implicitly when
// calculating neighbors. n.g is nothing more than
// current.g+1 ;
// add to the open list
if (!open.containsNode(n)) {
// slot into the list, in priority order (minimum f first)
open.priorityPush(n);
n.previous = current;
}
}
if (stop) {
callback(null);
return;
}
setTimeout(iteration, 1);
};
// kick off the first iteration
iteration();
return null;
}