关于在 15 方格拼图中使用 A* 的问题 [英] questions regarding the use of A* with the 15-square puzzle

问题描述

我正在尝试为

目标是重新排列图块，使它们出现在自然位置.您一次只能滑动一个图块.拼图的每个可能状态都是搜索图中的一个节点.

对于 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.

<小时>

编辑:我发现运行时间高度依赖于启发式.我看到有人提到的文章中将 10x 因子应用于启发式，这让我想知道 - 为什么是 10x?为什么是线性的?因为这是在 javascript 中完成的，所以我可以修改代码以使用当前正在考虑的节点动态更新 html 表.这让我可以在算法的进展过程中窥视它.使用常规的出租车距离启发式方法，我看到它未能收敛.

顶行有 5 个和 12 个，他们一直在附近徘徊.我会看到 1、2、3、4 爬进顶行，但随后它们会退出，其他数字会向上移动.我希望看到的是 1,2,3,4 爬到顶部，然后留在那里.

我心想——这不是我个人解决这个问题的方式.手动执行此操作，我解决了顶行，然后是第 2 行，然后是第 3 行和第 4 行.

所以我调整了 h(x) 函数，以增加较高行和左侧"列的权重.结果是 A* 收敛得更快.它现在在 3 分钟内运行，而不是无限期"运行.通过我所说的窥视"，我可以看到较小的数字爬到较高的行并保持在那里.这不仅看起来正确，而且运行速度更快.

我正在尝试一系列变体.很明显，A* 运行时对启发式非常敏感.目前我发现的最好的启发式方法是使用 dislocation * ((4-i) + (4-j)) 的总和，其中 i 和 j 是行和列，dislocation 是出租车距离.

我得到的结果中有一个有趣的部分:通过特定的启发式方法，我很快找到了一条路径，但它显然不是最短路径.我认为这是因为我正在加权启发式.在一种情况下，我在 10 秒内得到了 178 步的路径.我自己的手工努力在 87 次移动中产生了解决方案.(远远超过 10 秒).需要进行更多调查.

所以结果是我看到它收敛得更快，而且路径绝对不是最短的.我必须更多地考虑这个问题.

<小时>

代码:

var stop = false;功能 Astar(开始，目标，回调){//start 和goal 是图中的节点，表示为//一个 16 个整数的数组.目标是:[1,2,3,...14,15,0]//零代表洞.//回调是完成后调用的方法.这运行了很长时间，//因此我们需要使用 setTimeout() 来分解它，以避免//浏览器警告，如停止运行此脚本?"//g 是从初始节点到当前节点的实际距离.//h 是从当前到目标的距离的启发式估计.停止=假；start.g = start.dontgo = 0;//calcHeuristic 在数组中插入一个 .h 成员calcHeuristicDistance(开始)；//以一个元素开始堆栈var 关闭 = [];//已经评估过的节点集.var open = [开始];//要评估的节点集(从初始节点开始)var 迭代 = 函数(){如果(开放.长度== 0){//没有更多的节点.失败.回调(空)；返回;}var current = open.shift();//获取最高优先级节点//用表的表示更新浏览器//正在评估的节点$("#solution").html(stateToString(current));//如果当前 == 目标，则检查解决方案返回 true如果(检查解决方案(当前，目标)){//reconstructionPath只是记录了洞的位置//通过每个节点var path=reconstructpath(start,current);回调(路径)；返回;}关闭.推(当前)；//获取邻居集.这是 3 个或更少的节点.//(nextStates 被优化为不会直接返回自身)var 邻居 = nextStates(current,goal);for (var i=0; i

解决方案

A-star 搜索将通过证明所有尚未解决的路径无法用比当前解决方案更少的移动来解决来找到最佳解决方案.您不是在寻找最佳解决方案，而是最快解决方案.因此，您可以通过返回第一个解决方案来优化您的算法，通过加权比您的启发式函数低的移动次数，启发式可以返回高估.

启发式函数本身通常最好通过曼哈顿距离和线性冲突建模.曼哈顿距离在其他答案和维基百科文章中得到了很好的解释，您似乎对此有所了解.线性冲突为每对必须交换以达到解决方案的块的曼哈顿距离增加两个.例如，如果一行包含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.

这篇关于关于在 15 方格拼图中使用 A* 的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！