我前几天被问到了有关" 概述用N球解决迷宫的一般算法，目标是将所有球都带到迷宫中的给定位置（迷宫没有出口）"。唯一的规则是，算法必须有效（比随机移动球更好），并且发出的所有命令都会影响所有球，因此，这是一个球向北移动，如果其他球没有被阻止，则所有球都会。
为此，我做了一些假设，即
- 迷宫是标准/完美
- 球不能互相阻挡
- 球可以到达问的位置
- 命令会让球滚动直到撞墙
- 命令只能是n/s/e/w
- 迷宫是随机构造的，每次重置球随机分布
- 所有迷宫都可以立即被迷宫操者观察到
和，使我的算法工作
- 球并不相同（例如，上面有一个数字或某物）
- 迷宫操作员有摄影记忆
给出了这个，我认为最好的主意是
- 随机（或以明智的方式）移动球，直到两个球到达目标位置
- 将路径从起步位置保存到最终位置。
- 识别那些球及其来自何处，对每个球都做1.
这种递归算法中的"中断"是当所有球都可以达到给定目标（o（log（log（log（n））递归）时，我认为？）
这个有效吗？其他人是否有更好的算法？
我还有另一个想法，涉及将所有球移到相同的随机位置，然后将它们全部移动为一个球，但这似乎是一种更糟糕的算法。
另一个想法是生成图形（图形），其中所有稳定的球都将是一个节点，而动作将是一个边缘，但是我看不出它不需要
我建议以下算法：
-
为迷宫创建一个数据结构，其中每个自由单元（平方）以下是已知的：
a。坐标（行，列）
b。四个动作的目标细胞（北，东，南，西）
C。B的反面：大理石可以到达该单元的细胞（如果有）。 -
从目标细胞开始执行BFS，用一个虚构的大理石进行反向移动，分配给每个访问的单元格，从该单元格到达目标细胞所需的最少移动。请注意，某些单元可能不会以这种方式访问，这意味着如果将大理石放在那里，则无法通过执行法律动作将其进入目标单元。这些单元将获得归因于它们的无限距离（初始值）。
-
创建一个评估功能，将成本分配给大理石的某些配置。建议的评估函数将总结至少一个大理石占据的每个单元的距离的平方。通过采用广场，更高的距离将带来相对较高的成本，因此该算法将有利于改善大理石位置最差位置的举动。该功能不会计算被多个大理石占据的单元格的两倍。这样，大理石共享单元格的配置就会受到青睐。
-
从起始位置，以评估成本生成4个可能的动作。按他们的成本排序，并按照该顺序执行DFS，并递归地重复此步骤。当成本变为零时，会找到解决方案，并在立即退出递归期间，返回"路径"。当成本是无限的时，搜索就会停止，然后尝试了下一步，...等等。
-
在搜索过程中保留访问的位置列表。当再次访问职位时，评估功能将使其具有无穷大的值，以便在发生这种情况时进行搜索。
这是上述算法的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, *=targetnn' + mazeStr);
var moves = solve(maze);
console.log('moves (0=north,1=east,2=south,3=west): ' + moves);发现的解决方案不一定是最佳的。它具有深度1的评估。对于更好的解决方案，算法可以在更深入的情况下进行评估。
迷宫和允许的运动可以建模为四个符号字母上的确定性有限自动机（DFA）。迷宫中的每个单元格是一个DFA状态，每当发出命令时，小区X每当单元x上的球移至单元y时，都会在符号上过渡。
该算法有三个阶段：
- 构建一个DFA，仅由迷宫中的任何球都可以到达的那些状态，以某种命令。
- 为DFA找到任何同步词。同步单词或"重置单词"是所有初始状态在同一状态结束的任何符号序列。请注意，我们实际上只需要一个单词来同步球的所有初始状态，而不是DFA中的每个状态。
- 找到从重置词的末端状态到迷宫中目标位置的最短移动顺序。可以使用任何最短路径算法来完成此操作，例如广度优先搜索（BFS）。
这需要一些解释。
首先，并非每个DFA都有一个重置单词，但是如果步骤1中构造的DFA没有重置单词，则根据定义，没有命令序列可以将所有球带到同一目标单元。因此，该算法将解决问题的每个可解决实例。
其次，找到最小的重置单词是一个困难的问题，在最坏的情况下需要指数时间。但是问题只说"算法必须有效（比随机移动球更好）" ，因此任何重置单词都会做。
构建重置单词的最简单方法可能是在DFA的笛卡尔产品上使用广度优先搜索。对于具有n个状态的DFA，需要花费时间才能找到一个使两个状态同步的单词。必须将其重复为k -1次，以同步球的初始状态，给出O（kn²）的运行时间和一个长度o（kn²）的重置单词。
使用更简单的语言，该算法的最简单形式使用BFS将两个球带入同一位置，然后再次将BFS降低到与这两个球相同的位置，依此类推，直到所有球在同一个地方。然后，它使用BFS将它们全部带入目标。但是，可以通过插入更好的重置单词算法来改进算法；通常，即使在最坏的情况下，也应该存在比n²符号短的复位单词（认为这是未经证实的），它比kn²好得多。