algorithm - 关于在 15 方格拼图中使用 A* 的问题

Question

我正在尝试构建一个 A* solver对于 15-square puzzle .



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

对于 h(x) 函数，我使用了所有磁贴与目标状态的磁贴错位的总和。在上图中，5 位于位置 0,0，并且它属于位置 1,0，因此它对 h(x) 函数贡献了 1。下一个图块是 11，位于 0,1，属于 2,2，因此它对 h(x) 贡献了 3。等等。 编辑:我现在明白这就是他们所说的“曼哈顿距离”或“taxicab distance”。

我一直在使用 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 爬到顶部，然后留在那里。

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

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

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

我得到的结果中有一个有趣的部分:通过特定的启发式方法，我很快找到了一条路径，但它显然不是最短路径。我认为这是因为我正在加权启发式。在一种情况下，我在 10 秒内得到了 178 步的路径。我自己的手工努力在 87 个 Action 中产生了一个解决方案。 (远远超过 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;
}

Answer 1

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

启发式函数本身通常最好由 Manhattan distance 建模。和线性冲突。曼哈顿距离在其他答案和维基百科文章中得到了很好的解释，您似乎对此有所了解。线性冲突为每对必须交换以达到解决方案的块的曼哈顿距离增加两个。例如，如果一行包含“3 2 1 4”，则必须交换一个和三个，并且必须将一个移到另一行才能这样做。

使用模式数据库是一种选择，可以帮助您的搜索避免某些死胡同，并且为 15 拼图这样做的内存使用应该是可以管理的。