关于使用A *的15平方的难题问题 [英] questions regarding the use of A* with the 15-square puzzle
问题描述
我试图建立一个 A *求解了的15-square拼图的。
的目的是重新排列的瓷砖，以便它们出现在它们的自然位置。您只可以一次滑动一个砖。拼图的每个可能的状态是在搜索图的节点。
对于H（x）函数，我现在用的是砖的错位，从目标状态的总金额，在所有瓷砖。另外，在上述图像中，5是在位置0,0，和属于在位置1,0，因此它有助于1到H（x）函数。下一瓦片是11，位于0,1，属于在2,2，因此它有助于3到h（x）的。等等。 编辑：我现在明白了，这是他们所谓的曼哈顿距离，或出租车距离
我一直在使用一个步数为G（x）的。在我的实现，在状态图中的任何节点，g是刚一从先前节点的克
要找出连续节点，我刚刚检查，我都不可能在移动拼图洞。有3个邻居的拼图状态（即节点）显示：孔可以移动北，西，东或。
我的A *搜索有时会收敛到20多岁，有时180秒的解决方案，有时不衔接可言（等了10分钟以上）。我想，h是合理的。我想知道如果我正确地模仿克换句话说，是有可能，我的A *的功能是通过不是最短路径的路径到达图中的一个节点？
也许我已不是等了很久？也许10分钟不够长？
对于完全随机排列，（假设无奇偶校验问题），什么是排列的平均数量的A *的解决方案将检查？（请出示数学）
我要去找我的code逻辑错误，但在此期间， 任何提示吗？
（PS：它在Javascript中完成）。
此外，没有，这不是CompSci功课。这只是一个个人探索的事情。我只是想学习JavaScript。
修改：我发现，在运行时是高度依赖于启发式。只见应用于启发式从别人文章提到的10倍的因素，它使我想知道 - 为什么10倍？为什么直线？因为这是在JavaScript做的，我可以修改code动态与目前正在考虑的节点更新HTML表。这allowd我偷看算法，因为它正在取得进展。一个普通的出租车距离启发，我看着它没有收敛。
有5年代和12年代的前行中，他们不停地四处张望。我会看到1,2,3,4潜入排在前列，但随后他们会辍学，和其他数字将有向上移动。我希望能看到的是1,2,3,4排序攀升到顶部，然后呆在那里了。
我心想 - 这不是我解决这个个人的方式。手动这样做，我解决了最上面一排，然后2NE行，然后是第3和第4行的排序兼任。
所以我调整的H（x）函数，以更大的权重越高的行和lefter列。其结果是，在A *更快地收敛。它现在运行在3分钟内，而不是无限期。随着偷看我谈过，我能看到更小的数字攀升到更高的行和呆在那里。这不仅看起来正确的事情，它运行得更快。
我在试图一束变化的过程。看来pretty的明显，A *运行时间是启发式非常敏感。目前，我已经找到了最好的启发式使用错*的总和（（4-I）+（4-J））其中i和j行和列，脱位是出租车的距离。
我得到的结果的一个有趣的部分：与特定启发我找到一个路径非常快，但它显然不是最短路径。我想这是因为我加权启发。在一种情况下，我得到了在10秒178步的路径。我自己手动工作产生87移动的解决方案。 （大于10秒多）。更多调查必要。
所以，结果是我看到它必须收敛速度快，路径绝对不是最短的。我想了解更多这方面。
code：
VAR停止= FALSE;
功能阿斯达（启动，目标，回调）{
//启动和目标是图中的节点，再presented通过
// 16整数数组。我们的目标是：[1,2,3，... 14,15,0]
//零重新presents孔。
//回调是一个方法完成后调用。这将运行很长一段时间，
//因此我们需要使用的setTimeout（）来打破它，以避免
//类似的警告浏览器的停止运行此脚本？
// g是初始节点前往当前节点的实际距离。
// h是距离从目前的启发式估算目标。
停止= FALSE;
start.g = start.dontgo = 0;
// calcHeuristic插入一个.H成员到数组
calcHeuristicDistance（开始）;
//启动栈一个元素
VAR闭合= []; //节点集已经评估。
VAR开放= [开始]。 //设置节点，以评估（开始初始节点）
VAR迭代=功能（）{
如果（open.length == 0）{
//没有更多的节点。失败。
回调（空）;
返回;
}
变种电流= open.shift（）; //获取最高优先级的节点
//与更新的表重新presentation浏览器
//节点进行评估
$（＃溶液）的HTML（stateToString（电流））。
//检查解决方案返回true，如果目前的==目标
如果（checkSolution（电流，目标））{
// reconstructPath刚刚记录孔的位置
//通过每个节点
VAR路径= reconstructPath（启动，电流）;
回调（路径）;
返回;
}
closed.push（电流）;
//获取一组邻居。这是3个或更少的节点。
//（nextStates进行了优化，无法开机直接回自己）
VAR邻居= nextStates（电流，目标）;
对于（VAR I = 0; I＆LT; neighbors.length;我++）{
变种N =邻居[我]
//跳过这一个，如果我们已经访问过它
如果（closed.containsNode（N））继续;
// .G，.h和。previous得到隐时所分配
//计算邻居。 n.g无非是
// current.g + 1;
//添加到开放列表
如果（！open.containsNode（正））{
//槽进入榜单，按优先顺序（最小f第一）
open.priorityPush（N）;
。ñprevious =电流;
}
}
如果（停止）{
回调（空）;
返回;
}
的setTimeout（迭代中，1）;
};
//揭开序幕的第一次迭代
迭代（）;
返回null;
}
这是A-搜星会发现通过证明尚未得到解决的所有路径都不能被解决了移动比当前解决方案更少的最优解。你是不是找的最佳的解决方案，但最快的解决方案。因此，您可以通过返回的第一个解决方案，通过加权的比你的启发式功能的移动数字越低，优化算法和启发式可以返回高估。
启发式函数本身通常是最好的曼哈顿距离和线性冲突建模。曼哈顿距离是在其他的答案和维基百科文章很好的解释，你似乎有它的句柄。线性冲突增加了两个到曼哈顿距离对于每一对，将必须被交换以达到溶液块。例如，如果一个行包含3 2 1 4，然后一个和三个已被交换，和一个将必须被移动到另一行这样做。
用模式数据库是一个选项，可以帮助你的搜索避免某些死胡同，而这样做的一个15拼图的内存使用情况应该是可控的。
I'm trying to build an A* solver for a 15-square puzzle.
The goal is to re-arrange the tiles so that they appear in their natural positions. You can only slide one tile at a time. Each possible state of the puzzle is a node in the search graph.
For the h(x) function, I am using an aggregate sum, across all tiles, of the tile's dislocation from the goal state. In the above image, the 5 is at location 0,0, and it belongs at location 1,0, therefore it contributes 1 to the h(x) function. The next tile is the 11, located at 0,1, and belongs at 2,2, therefore it contributes 3 to h(x). And so on. EDIT: I now understand this is what they call "Manhattan distance", or "taxicab distance".
I have been using a step count for g(x). In my implementation, for any node in the state graph, g is just +1 from the prior node's g.
To find successive nodes, I just examine where I can possibly move the "hole" in the puzzle. There are 3 neighbors for the puzzle state (aka node) that is displayed: the hole can move north, west, or east.
My A* search sometimes converges to a solution in 20s, sometimes 180s, and sometimes doesn't converge at all (waited 10 mins or more). I think h is reasonable. I'm wondering if I've modeled g properly. In other words, is it possible that my A* function is reaching a node in the graph via a path that is not the shortest path?
Maybe have I not waited long enough? Maybe 10 minutes is not long enough?
For a fully random arrangement, (assuming no parity problems), What is the average number of permutations an A* solution will examine? (please show the math)
I'm going to look for logic errors in my code, but in the meantime, Any tips?
(ps: it's done in Javascript).
Also, no, this isn't CompSci homework. It's just a personal exploration thing. I'm just trying to learn Javascript.
EDIT: I've found that the run-time is highly depend upon the heuristic. I saw the 10x factor applied to the heuristic from the article someone mentioned, and it made me wonder - why 10x? Why linear? Because this is done in javascript, I could modify the code to dynamically update an html table with the node currently being considered. This allowd me to peek at the algorithm as it was progressing. With a regular taxicab distance heuristic, I watched as it failed to converge.
There were 5's and 12's in the top row, and they kept hanging around. I'd see 1,2,3,4 creep into the top row, but then they'd drop out, and other numbers would move up there. What I was hoping to see was 1,2,3,4 sort of creeping up to the top, and then staying there.
I thought to myself - this is not the way I solve this personally. Doing this manually, I solve the top row, then the 2ne row, then the 3rd and 4th rows sort of concurrently.
So I tweaked the h(x) function to more heavily weight the higher rows and the "lefter" columns. The result was that the A* converged much more quickly. It now runs in 3 minutes instead of "indefinitely". With the "peek" I talked about, I can see the smaller numbers creep up to the higher rows and stay there. Not only does this seem like the right thing, it runs much faster.
I'm in the process of trying a bunch of variations. It seems pretty clear that A* runtime is very sensitive to the heuristic. Currently the best heuristic I've found uses the summation of dislocation * ((4-i) + (4-j)) where i and j are the row and column, and dislocation is the taxicab distance.
One interesting part of the result I got: with a particular heuristic I find a path very quickly, but it is obviously not the shortest path. I think this is because I am weighting the heuristic. In one case I got a path of 178 steps in 10s. My own manual effort produce a solution in 87 moves. (much more than 10s). More investigation warranted.
So the result is I am seeing it converge must faster, and the path is definitely not the shortest. I have to think about this more.
Code:
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;
}
An A-star search will find the optimal solution by proving that all paths that have not yet been solved are incapable of being solved with fewer moves than the current solution. You aren't looking for the best solution, but the fastest solution. Therefore, you can optimize your algorithm by returning the first solution, by weighting the number of moves lower than your heuristic function, and the heuristic can return an over-estimate.
The heuristic function itself is typically best modeled by the Manhattan distance and linear conflict. Manhattan distance is well explained in other answers and in the Wikipedia article, and you seem to have a handle on it. Linear conflict adds two to the manhattan distance for each pair of blocks that would have to be swapped to reach a solution. For example, if a row contains "3 2 1 4", then the one and the three have to be swapped, and one would have to be moved to another row to do so.
Using a pattern database is an option and could help your search avoid certain dead-ends, and the memory usage of doing so for a 15-puzzle should be manageable.
这篇关于关于使用A *的15平方的难题问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
