用于解决n个球迷宫问题的通用算法

Question

有一天，有人问我如何“概述解决一个迷宫问题的一般算法，其中有n个球，目标是将所有球移到迷宫中给定的位置（迷宫没有出口）”。唯一的规则是算法必须有效（比随机移动球更好），并且发出的所有命令都会影响所有球，因此如果未被阻挡，一个球向北移动，其他球也会向北移动。

为了做到这一点，我做了一些假设，即：

• 迷宫是标准/完美的
• 球不能相互阻挡
• 球可以到达要求的位置
• 命令会让球滚动直到撞到墙壁
• 命令只能是N/S/E/W
• 迷宫是随机构建的，并且每次重置时球也是随机分布的
• 迷宫操作员可以同时观察整个迷宫

为了使我的算法起作用，

• 球不相同（例如，它们上面有编号或其他内容）
• 迷宫操作员有摄影记忆

鉴于此，我认为最好的想法是：

1. 随机（或聪明地）移动球，直到有两个球到达目标位置
2. 保存从它们的起始位置到终点位置的路径。
3. 识别那些球以及它们来自哪里，并对每个球执行1.

这个递归算法中的“break”是当所有球都有方法到达给定目标时（我认为是O(log(n))递归？）

这有效吗？还有其他人有更好的解决方案吗？

我还有另一个想法，涉及将所有球移动到同一随机位置，然后将它们全部作为一个球移动，但这似乎是更糟糕的算法。

另一个想法是生成一个图（图论），其中一个球的所有稳定点都是一个节点，移动是一个边缘，但我看不出这不需要大量的暴力才能完成。

- Eric

---

在我看来，“球体不能碰撞”与其他一些假设相矛盾。 - m69 ''snarky and unwelcoming''

你说得对，那是我措辞不当。我的意思是它们不能互相阻挡（或者都是无法碰撞的幽灵球）。我会修改的！ - Eric

Answer 1

我建议使用以下算法：

1. 创建一个数据结构来表示迷宫，对于每个空闲的格子，需要知道以下信息： a. 坐标（行、列） b. 四个方向可移动到达的目标格子（北、东、南、西） c. b的反向：可以移动到该格子的格子（如果有的话）。 2. 从目标格子开始执行广度优先搜索（BFS），使用一个想象中的弹球进行反向移动，对于每个访问的格子，都分配一个从该格子到目标格子所需的最少移动次数。注意，某些格子可能无法通过这种方式被访问到，这意味着如果在该位置放置弹球，则无法通过合法的移动将其移动到目标格子。这些单元格会被赋予无限的距离值（初始值）。 3. 创建一个评估函数，用于为特定的弹球配置分配成本。建议的评估函数将累加由至少一个弹球占据的每个单元格的距离的平方。通过取平方，较大的距离将带来相对较高的成本，因此算法将青睐于改善最差位置的弹球的移动。该函数不会计算被多个弹球占用的单元格的成本。因此，对于弹球共享单个格子的配置，该函数会给予更高的分数。 4. 从起始位置开始，生成四种可能的移动以及它们的评估成本。按它们的成本升序排序，并按照这个顺序递归地执行深度优先搜索（DFS）。当成本变为零时，找到一个解决方案，并在立即回溯时返回“路径”移动。当成本无限时，搜索停止，并尝试下一步移动等。 5. 在搜索过程中保持一个访问过的位置列表。当再次访问一个位置时，评估函数将给它赋予无限值，以便在发生这种情况时进行回溯。

以下是上述算法的JavaScript实现：

"use strict";
function createMaze(mazeStr) {
    var maze, lines, cell, row, ch, id, r, c, n, m;
    
    maze = {
        nodesRowCol: [],
        nodes: [],
        target: null,
        marbles: []
    };
    id = 0;
    lines = mazeStr.split("\n");
    for (r = 0; r < lines.length; r++) {
        maze.nodesRowCol[r] = row = [];
        for (c = 0; c < lines[r].length; c++) {
            ch = lines[r].charAt(c);
            if (ch !== '#') {
                maze.nodes[id] = row[c] = cell = {
                    row: r,
                    col: c,
                    id: id++,
                    comeFrom: [],
                };
                // Keep track of target and marbles
                if (ch === '*') maze.target = cell;
                if (ch === '.') maze.marbles.push(cell);
            }
        }
    }
    // Add neighbours
    for (n = 0; n < maze.nodes.length; n++) {
        cell = maze.nodes[n];
        cell.neighbours = [
            maze.nodesRowCol[cell.row-1][cell.col], /* north */
            maze.nodesRowCol[cell.row][cell.col+1], /* east  */
            maze.nodesRowCol[cell.row+1][cell.col], /* south */
            maze.nodesRowCol[cell.row][cell.col-1]  /* west  */
        ];
    }
    // Add marble moves in two steps
    for (n = 0; n < maze.nodes.length; n++) {
        cell = maze.nodes[n];
        cell.moves = [ 
            cell.neighbours[0] ? cell.neighbours[0].moves[0] : cell, /* north */
            null,
            null,
            cell.neighbours[3] ? cell.neighbours[3].moves[3] : cell, /* west  */
        ];
    }
    for (n = maze.nodes.length - 1; n >= 0; n--) {
        cell = maze.nodes[n];
        cell.moves[1] = cell.neighbours[1] ? cell.neighbours[1].moves[1] : cell; /* west */
        cell.moves[2] = cell.neighbours[2] ? cell.neighbours[2].moves[2] : cell; /* south */
    }
    // add reverse-move ("marble can come from") data
    for (n = maze.nodes.length - 1; n >= 0; n--) {
        cell = maze.nodes[n];
        for (m = 0; m < 4; m++) {
            if (cell.moves[m] !== cell) cell.moves[m].comeFrom.push(cell);
        }
    }
    return maze;
}

function setDistances(maze) {
    var n, cell, distance, stack, newStack, i;
    // clear distance information
    for (n = 0; n < maze.nodes.length; n++) {
        maze.nodes[n].distance = Number.POSITIVE_INFINITY;
    }
    // set initial distance
    cell = maze.target;
    cell.distance = distance = 0;
    // BSF loop to set the distance for each cell that can be reached
    stack = cell.comeFrom.slice();
    while (stack.length) {
        distance++;
        newStack = [];
        for (i = 0; i < stack.length; i++) {
            cell = stack[i];
            if (distance < cell.distance) {
                cell.distance = distance;
                newStack = newStack.concat(cell.comeFrom);
            }
        }
        stack = newStack;
    }
}

function evaluatedPosition(position, visited) {
    // Assign heurstic cost to position
    var m, ids;
    
    position.cost = 0;
    ids = []; // keep track of marble positions
    for (m = 0; m < position.marbles.length; m++) {
        // If mulitple marbles are at same cell, only account for that cell once.
        // This will favour such positions: 
        if (ids[position.marbles[m].id] === undefined) { 
           // Make higher distances cost a lot, so that insentive
           // is to improve the position of the worst placed marble 
           position.cost += Math.pow(position.marbles[m].distance, 2);
           ids[position.marbles[m].id] = position.marbles[m].id;
        }
    }
    // Assign some unique string, identifying the marble configuration
    position.id = ids.join(','); 
    // If position was already visited before, give it the maximum cost
    if (visited[position.id]) position.cost = Number.POSITIVE_INFINITY;
    // Mark position as visited
    visited[position.id] = 1;
    return position;
}

function createMove(dir, marbles, visited) {
    var m, movedMarbles;
    
    movedMarbles = [];
    for (m = 0; m < marbles.length; m++) {
        movedMarbles[m] = marbles[m].moves[dir];
    }
    return evaluatedPosition({
        dir: dir,
        marbles: movedMarbles,
    }, visited);
}

function solve(maze) {
    var visited = {}; // nothing visited yet
    
    function recurse (position) {
        var ids, m, moves, i, path;
        if (position.cost == 0) return []; // marbles are all on target spot.
        if (!isFinite(position.cost)) return false; // no solution
        // get move list
        moves = [];
        for (i = 0; i < 4; i++) {
            moves[i] = createMove(i, position.marbles, visited);
        }
        // apply heuristic: sort the 4 moves by ascending cost
        moves.sort(function (a,b) { return a.cost - b.cost });
        for (i = 0; i < 4; i++) {
            //console.log('=== move === ' +  moves[i].dir);
            path = recurse(moves[i]);
            if (path !== false) return [moves[i].dir].concat(path);
        }
        return false; // no solution found
    }
    // Enrich initial position with cost, and start recursive search 
    return recurse(evaluatedPosition({
        marbles: maze.marbles
    }, visited));
}


// # = wall
// * = target
// . = marble

var mazeStr = `
###########
#   #   #*#
# # #.#  .#
# #.  #.# #
# # # ### #
#   #     #
###########
`.trim();

var maze = createMaze(mazeStr);
setDistances(maze);
console.log('#=wall, .=marble, *=target\n\n' + mazeStr);

var moves = solve(maze);
console.log('moves (0=north,1=east,2=south,3=west): ' + moves);

找到的解决方案不一定是最优的。它进行了深度为1的评估。为了获得更好的解决方案，算法可以在更大的深度上进行评估。

- trincot

---

这个回答在很多方面都比我的回答好太多了。我明白它是如何解决的，也知道为什么深度更大会更好，但是那不会消耗更多的计算能力吗？也许是指数级的增长？ - Eric

当然，深度应该受到限制，不应该任意增加，否则评估将需要太多时间。每增加1个深度，要查看的位置数量就会增加三倍。但是，您可以使用其他启发式方法来“修剪”评估搜索树中的一些分支，当一个位置的评估导致成本与其他位置相比过高时。您可能会意外地修剪掉一个好的分支，因为最优解可能需要经过一个“山丘”（暂时的高成本）。 - trincot

非常抱歉回复晚了，最近工作比较忙 :/ 答案非常好，经过我查看了一些关于剪枝的YouTube视频后，我明白了你提高复杂度的意思。再次感谢你的解答！ - Eric

Answer 2

迷宫和允许的移动可以建模为一个由四个符号组成的确定性有限自动机（DFA）。迷宫中的每个单元格都是DFA状态，当在单元格x处的球发出命令s时，单元格x上的转移将导致球移动到单元格y。

该算法分为三个阶段：

1. 构造一个DFA，其中只包含迷宫中任何球通过某些命令可达的状态。

2. 找到DFA的任何同步词。同步词或“复位词”是指所有初始状态均以相同状态结束的任何符号序列。请注意，我们实际上只需要一种同步所有球的初始状态而不是DFA中的每个状态的词。

3. 找到从复位词的最终状态到迷宫目标位置的最短移动序列。这可以使用任何最短路径算法完成，例如广度优先搜索（BFS）。

这需要一些解释。

首先，不是每个确定有限状态自动机都有重置词，但如果在第一步构建的DFA中没有重置词，则根据定义，没有任何命令序列可以将所有球带到同一个目标单元格。因此，该算法将解决问题的每个可解实例。

其次，找到最短的重置词是一个困难的问题，在最坏情况下需要指数时间。但是问题只要求“算法必须有效（比随机移动球更好）”，因此任何重置词都可以。

构造重置词最简单的方法可能是在DFA与自身的笛卡尔积上使用广度优先搜索。对于具有n个状态的DFA，找到同步两个状态的单词需要O（n²）的时间；这必须重复k-1次以同步球的k个初始状态，从而给出O（kn²）的运行时间和长度为O（kn²）的重置词。

---

更简单的说，这个算法的最简形式使用BFS将两个球放在同一位置，然后再次使用BFS将第三个球放在与这两个球相同的位置上，以此类推，直到所有球都在同一位置上。然后使用BFS将它们全部同时移动到目标位置。但是，通过插入一个更好的重置词查找算法可以改进该算法；通常情况下，即使在最坏情况下也应该存在比n²符号更短的重置词（这是被认为但未经证明的），这比kn²要好得多。

- kaya3