解决带有 n 个球的迷宫的通用算法

Question

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

为此我做了一些假设，即

迷宫是standard/perfect
球不能互相阻挡
球可以到达要求的位置
一个命令会让球滚动直到撞到墙上
一个命令只能是N/S/E/W
迷宫是随机建造的，每次重置时球都是随机分布的
迷宫操作员可以同时观察所有迷宫

并且，让我的算法工作

球不相同（例如球上有数字或其他东西）
迷宫操作员具有过目不忘的记忆力

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

随机（或以智能方式）移动球，直到两个球到达目标位置
保存从他们的起始位置到结束位置的路径。
认出这些球以及它们的来源，然后对每个球执行 1。

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

这个有用吗？还有其他人有更好的算法吗？

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

另一个想法是生成一个图（即图论），其中球的所有稳定点都是一个节点，而移动是一条边，但我看不出这是怎么回事'不需要很多蛮力就可以完成。

Answer 1

我建议使用以下算法：

为迷宫创建一个数据结构，其中每个空闲单元格（正方形）的以下信息是已知的：

一个。坐标（行、列）
b. 4 个移动的目标单元格（北、东、南、西）
C。 b 的反面：弹珠可以到达此单元格的单元格（如果有）。
从目标单元格开始执行 BFS，用一个假想的弹珠执行反向移动，为每个访问的单元格分配从该单元格到达目标单元格所需的最少移动次数。请注意，某些单元格可能不会以这种方式访问，这意味着如果将弹珠放置在那里，则无法通过执行合法移动将其到达目标单元格。这些单元格将获得归因于它们的无限距离（初始值）。
创建一个评估函数，为弹珠的特定配置分配成本。建议的评估函数将对至少一个弹珠占据的每个单元格的距离的平方求和。通过取正方形，更高的距离将带来相对更高的成本，因此算法将倾向于改善位置最差的弹珠位置的移动。此函数不会将被多个弹珠占据的单元格加倍计数。这样，弹珠共享一个单元格的配置将受到青睐。
从起始位置，生成 4 个可能的移动及其评估成本。按成本升序对它们进行排序，并按此顺序执行 DFS，递归地重复此步骤。当成本变为零时，找到解决方案，并且在递归的立即回溯期间，返回 "path" 的移动。当成本为无穷时，则停止搜索，并尝试下一步，...等等
在搜索过程中保留一份访问过的职位列表。当再次访问一个位置时，评估函数会给它一个无穷大的值，这样搜索就会回溯。

下面是上述算法的 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 的评估。为了获得更好的解决方案，该算法可以在更大的深度进行评估。

Answer 2

迷宫和允许的运动可以在四个符号的字母表上建模为 deterministic finite automaton (DFA)。迷宫中的每个单元格都是一个 DFA 状态，并且当发出命令 s 时，只要单元格 x 中的球移动到单元格 y，单元格 x 就会在符号 s 上转换到单元格 y。

算法分为三个阶段：

构造一个 DFA，仅包含迷宫中任何球可通过某些命令序列到达的那些状态。
为 DFA 找到任何 synchronizing word。同步字或 "reset word" 是所有初始状态都以相同状态结束的任何符号序列。请注意，我们实际上只需要一个词来同步球的所有初始状态，而不是 DFA 中的每个状态。
找到从重置词的结束状态到迷宫中目标位置的最短移动序列。这可以使用任何最短路径算法来完成，例如breadth-first search (BFS).

这需要一些解释。

首先，并非每个 DFA 都有一个重置词，但如果在步骤 1 中构建的 DFA 没有重置词，那么根据定义，没有任何命令序列可以将所有球带到同一个目标单元格。所以这个算法将解决问题的每个可解决实例。

其次，找到一个最小长度的重置字是一个难题，在最坏的情况下需要花费指数时间。但问题只说 "the algorithm must be effective (better than randomly moving the balls)"，所以任何重置字都可以。

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

的重置字

换句话说，这个算法的最简单形式是使用 BFS 将两个球放到同一个位置，然后再次 BFS 将第三个球放到与这两个球相同的位置，依此类推，直到所有的球都在同一个地方。然后它使用 BFS 让它们一致地到达目标。但是可以通过插入更好的重置词查找算法来改进算法；通常，即使在最坏的情况下（据信但未经证实），也应该存在短于 n² 符号的重置字，这比 kn² 好得多。

解决带有 n 个球的迷宫的通用算法

General algorithm to solve a maze with n balls

algorithm

conceptual