Eri*_*ric 4 algorithm conceptual
前几天我被问到" 概述用n球解决迷宫的一般算法,其目标是将所有球送到迷宫中的给定位置(迷宫没有出口) ".唯一的规则是算法必须有效(优于随机移动球)并且所有发出的命令都将影响所有球,因此一个球向北移动,如果它们没有被阻挡,所有其他球也将移动.
为此,我做了一些假设,即那些
并且,使我的算法工作
鉴于此,我认为最好的想法是
这个递归算法中的"中断"是当所有的球都有办法到达给定目标时(我认为是O(log(n))递归？)
这有用吗？有没有其他人有更好的算法呢？
我有另一个想法,包括将所有球移动到相同的随机位置,然后将它们全部移动为一个球,但这似乎是一个更糟糕的算法.
另一个想法是生成一个图形(图形理论),其中球的所有稳定点都是一个节点,并且移动将是一个边缘,但我看不出它是如何不需要很多蛮力待做.
我会建议以下算法:
为迷宫创建数据结构,对于每个空闲单元格(正方形),已知以下内容:
一个.坐标(行,列)
b.4个移动的目标细胞(北,东,南,西)
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, *=target\n\n' + mazeStr);
var moves = solve(maze);
console.log('moves (0=north,1=east,2=south,3=west): ' + moves);找到的解决方案不一定是最佳的.它执行深度为1的评估.为了获得更好的解决方案,该算法可以在更深的位置进行评估.