替代文字http://i49.tinypic.com/343r8ki.jpg
目标是重新排列瓷砖,使它们出现在自然位置.您一次只能滑动一个图块.拼图的每个可能状态是搜索图中的节点.
对于h(x)函数,我在所有图块中使用了图块与目标状态的错位的总和.在上面的图像中,5位于位置0,0,它属于位置1,0,因此它对h(x)函数贡献1.下一个区块是11,位于0,1,属于2,2,因此它对h(x)贡献3.等等.编辑:我现在明白这就是他们所谓的"曼哈顿距离",或" 出租车距离 ".
我一直在使用g(x)的步数.在我的实现中,对于状态图中的任何节点,g只是来自先前节点g的+1.
为了找到连续的节点,我只是检查在哪里可以移动拼图中的"洞".显示的拼图状态(aka节点)有3个邻居:洞可以向北,向西或向东移动.
我的A*搜索有时会收敛到20s,有时是180s的解决方案,有时根本不收敛(等待10分钟或更长时间).我认为我是合理的.我想知道我是否正确地模拟了g.换句话说,我的A*函数是否可能通过不是最短路径的路径到达图中的节点？
也许我没有等待足够长的时间？也许10分钟不够长？
对于完全随机的安排,(假设没有奇偶校验问题),A*解决方案将检查的平均排列数是多少？(请显示数学)
我将在我的代码中查找逻辑错误,但在此期间,任何提示？
(ps:它是用Javascript完成的).
另外,不,这不是CompSci的功课.这只是个人探索的事情.我只是想学习Javascript.
编辑:我发现运行时间高度依赖于启发式.我从有人提到的文章中看到了10x因子应用于启发式,它让我想知道 - 为什么10x？为何线性？因为这是在javascript中完成的,所以我可以修改代码以使用当前正在考虑的节点动态更新html表.这允许我在算法进展时查看算法.使用常规的出租车距离启发式,我看到它没有收敛.
排在前排有5个和12个,他们一直闲逛.我看到1,2,3,4爬进了最上面的一行,但随后它们会退出,其他数字会向上移动.我希望看到的是1,2,3,4爬到顶部,然后呆在那里.
我心想 - 这不是我亲自解决这个问题的方式.手动执行此操作,我解决了顶行,然后是2ne行,然后是第3行和第4行.
所以我调整了h(x)函数来对更高的行和"lefter"列进行更大的权重.结果是A*收敛得更快.它现在运行3分钟而不是"无限期".通过我所谈到的"偷看",我可以看到较小的数字爬到更高的行并留在那里.这不仅是正确的事情,它运行得更快.
我正在尝试一系列变化.很明显,A*运行时对启发式非常敏感.目前我发现的最佳启发式使用了dislocation * ((4-i) + (4-j))i和j是行和列的总和 ,而位错是出租车距离.
我得到的结果的一个有趣的部分:使用特定的启发式,我很快找到了一条路径,但它显然不是最短的路径.我认为这是因为我正在加权启发式.在一个案例中,我在10s内获得了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 …