我来将这段关于A*搜索算法的教程内容翻译成简体中文:
我来到Myth引擎团队。这是一个我们的免费教程, engines 已经被移除,所以它可以在任何引擎中工作。代码是纯粹的JavaScript。
想象一位由黄铜制成的框架,放在昏暗的木质桌面上。框架中摆满八块奶油色的砖块,位置杂乱无章,围绕着一块空白方块。卡片旁边显示目标:1 2 3,4 5 6,7 8,空白方块最后。
5 4 2
7 _ 3
8 1 6
你可以用手指滑动砖块回到原位。或者你可以按一下“求解”按钮。卡片上的计数器爬升到20,砖块暂时不动。然后它们开始依次滑动。经过十二次移动,棋盘匹配卡片上的目标。没有更短的路径 exists。
这就是A*搜索算法,这篇文章将在五个步骤中构建它,从棋盘开始,到求解按钮。
1. 将整个棋盘用一个值表示
以阅读页面的方式读取棋盘。从上行开始,然后是中间行,最后是下行,对空白方块写0。得到542703816,这就是棋盘状态。目标是123456780,所有砖块按顺序排列,空白方块在最后。
每个棋盘位置都是槽位,编号为0到8,按照相同的阅读顺序。一次移动是一块砖块滑动进入空白方块。在字符串中,这是两个字符的交换。
为什么要这样做得很小?搜索会书写下来数十个棋盘,并检查每个新的棋盘是否与其它棋盘相同。一个字符串很快可以复制和比较,并且可以作为Map的键。屏幕上显示的砖块只显示这个值。它们永远不会决定它们在哪里。
const GOAL = '123456780';
// 两个槽位之间的行数和列数 (0到8,按照阅读顺序)
const slotDistance = (a, b) => Math.abs(a % 3 - b % 3) + Math.abs(Math.floor(a / 3) - Math.floor(b / 3));
// 砖块从槽位fromSlot滑动到空白槽位blankSlot后的棋盘
function boardAfterMove(board, fromSlot, blankSlot) {
const tiles = board.split('');
[tiles[fromSlot], tiles[blankSlot]] = [tiles[blankSlot], tiles[fromSlot]];
return tiles.join('');
}
// 每个棋盘的一个合法移动后的邻居状态 (按照槽位顺序)
function neighbors(board) {
const blank = board.indexOf('0'), found = [];
for (let slot = 0; slot < 9; slot++)
if (slotDistance(slot, blank) === 1) found.push(boardAfterMove(board, slot, blank));
return found;
}
2. 拒绝无法解答的拼图
在一个已解的棋盘上交换7和8,你得到123456870。它看起来只差一步,但无论如何滑动都永远无法完成。
原因在于计数。按照顺序读取砖块,跳过空白方块。big砖块出现在小砖块前的逆序。目标中没有逆序。你的拼图有14个,123456870只有1个。
一次合法的滑动永远不会改变这个计数是偶数还是奇数。左右滑动的砖块保持阅读顺序。上下滑动的砖块穿过两个其他砖块,所以计数改变2,或不变。你的拼图的14是偶数,正如目标的0一样,所以它可以到达。在4×4棋盘上,空白方块的行号也计入这个计数。
// 较大砖块出现在较小砖块前的配对数 (不包括空白方块)
function countInversions(board) {
const tiles = board.replace('0', '');
let inversions = 0;
for (let i = 0; i < tiles.length; i++)
for (let j = i + 1; j < tiles.length; j++)
if (tiles[i] > tiles[j]) inversions++;
return inversions;
}
const canReachGoal = board => countInversions(board) % 2 === countInversions(GOAL) % 2;
由随机合法操作得到的拼图总是可以解的。每个合法操作都可以撤销。
3. 一个笔记本和一条规则
搜索保留一个笔记本。每个棋盘找到时都有一行记录,包含两个数字。第一个是迄今为止的移动次数。第二个是估计值,对剩余剩余移动次数的估计。在两者相加得到该行的得分。
估计值来自砖块。对于每一块,计算它所在位置到目标位置的行数和列数之和。砖块1到 home 位置需要3个槽位。砖块5和4各需2个槽位,其余五块各需1个槽位。总共需要12步。
一次合法的滑动只会让一块砖块移动一个槽位。所以没有任何路径需要的移动次数少于这个估计值,估计值永不高估。这正是它让搜索在目标被选中时能够确定的最短路径的关键所在。
// 曼哈顿距离:每块砖块到 home 位置的行数和列数之和
function estimateMovesLeft(board) {
let total = 0;
for (let slot = 0; slot < 9; slot++)
if (board[slot] !== '0') total += slotDistance(slot, GOAL.indexOf(board[slot]));
return total;
}
现在规则是:每一步,取得分最低的开放行,展开它。关闭该行,记录所有法定移动后的新棋盘。教科书上将已走步数记为g,将估计值记为h,得分记为f = g + h。
你的拼图的第一步发现四个邻居。砖块4向下滑动,砖块1向上滑动各带来一块砖块接近 home 位置,所以它们的得分都是12。砖块7和3的滑动会让砖块远离 home 位置,它们的得分是14。
三个小小的选择决定了算法是否能正确工作:在得分相同的情况下,估计值较小的优先,随后是最早写入的行。目标被选中时才被接受,而非发现时。笔记本还有数量限制。
中间一个选择常常会让人感到惊讶。目标在第20步作为邻居出现。搜索不会在此时停止。在第21步,它选中目标作为最佳开放行,此时才接受它。每个得分都是实际步数加上永不高估的估计值。所以当目标具有最低得分时,笔记本中剩余的任何路径都不可能更短。若在第一次发现时就停止,那么返回的路径可能不包含最短解。
限制是4096行。你的拼图只写了35行。需要更多行的搜索会停止并要求换一个新拼图,这样游戏就不会卡住。
function createSearch(start, estimate = estimateMovesLeft, maxStates = 4096) {
// 笔记本:每个棋盘一行记录,按照写入顺序排列 (Map保持顺序)
const notebook = new Map([[start, { movesSoFar: 0, movesLeft: estimate(start), parent: null, isOpen: true }]]);
// 一步:返回 'searching'(搜索中)、'found'(找到)或 'stopped'(停止)
function step() {
let best = null, bestLine = null;
for (const [board, line] of notebook) {
if (!line.isOpen) continue;
const score = line.movesSoFar + line.movesLeft;
const bestScore = bestLine && bestLine.movesSoFar + bestLine.movesLeft;
// 最低得分获胜;得分相同时,估计值小的优先;然后是最早写入的
if (!bestLine || score < bestScore || (score === bestScore && line.movesLeft < bestLine.movesLeft)) {
best = board;
bestLine = line;
}
}
if (!best) return 'stopped'; // 没有开放的行
if (best === GOAL) return 'found'; // 目标在被选中时才被接受
bestLine.isOpen = false;
for (const next of neighbors(best)) {
const movesSoFar = bestLine.movesSoFar + 1, seen = notebook.get(next);
if (seen) {
// 之前看到的棋盘保持原有记录,除非这条路径更短
if (movesSoFar < seen.movesSoFar) Object.assign(seen, { movesSoFar, parent: best, isOpen: true });
} else if (notebook.size < maxStates) {
notebook.set(next, { movesSoFar, movesLeft: estimate(next), parent: best, isOpen: true });
} else return 'stopped'; // 笔记本已满:请求新拼图
}
return 'searching';
}
return { step, notebook };
}
4. 沿足迹回家
笔记本不存储完整路径。每行记录记住一个额外信息:到达该棋盘的来源棋盘,即其父节点。父节点的链条形成一条足迹——从目标倒回到你的拼图。
所以从目标开始,沿着父节点一路向前,然后反过来读取这条路径。
// 从目标沿父节点倒推,然后正向读取路径
function route(notebook) {
const boards = [];
for (let board = GOAL; board; board = notebook.get(board).parent) boards.unshift(board);
return boards;
}
const search = createSearch('542703816');
let result;
do result = search.step(); while (result === 'searching');
console.log(result, route(search.notebook).length - 1); // found 12
你的拼图的路径包含13个棋盘,即12次移动,砖块按以下顺序滑动:1,8,7,5,4,1,5,4,1,2,3,6。广度优先搜索验证没有更短的路径。这组数字也正好是你的提示按钮:显示第一步,或播放全部移动。
5. 求解是对步进按钮的轻触
求解并未创建新的搜索类型。它只是帮你连续按下步进按钮。每0.05秒按一次,最多连续按8次,计数器在你的眼睛跟随前就达到20。在找到路径后,每一步滑动一块砖块,所以手指在砖块正在滑动时抬起。暂停停止计时器,任何信息都不会丢失。
每一步都会保留笔记本的完整性。所以搜索可以在任意两步之间停止,然后稍后继续。步进、求解和暂停在代码中走同一路,错误也以相同方式表现。一个缓慢的求解(每半秒一步)让你可以观察搜索的工作原理。
估计值是否重要?
尝试一个较弱的估计值,“错误位置计数”。它只询问每块砖块它是否已经到位,任何不在正确位置的砖块计为1,无论它们相距多远。对于你的拼图,它估计为8,而曼哈顿距离估计为12。
两种估计值都是诚实的,都找到相同的12步路径。但“错误位置计数”估计较弱。更多的棋盘看起来都和最佳路径一样好,搜索必须检查它们才能确定。它检查了84个棋盘,而不只是20个。
该搜索在每一步都读取整个笔记本来找到最佳行。在35行规模下没问题,你仍然可以跟踪每一步。规模为数千行的笔记本需要使用优先队列代替,一种保持开放行排序的结构。
完整版本
该教程所来源的教程构建了整个游戏的五个章节。每个章节都有一个可直接在浏览器中使用的可玩版本。你可以自己按步进按钮并观察计数爬升到20再去实现。它使用Myth引擎和可视化逻辑块构建。该教程是免费的,你可以在引擎的免费版本中完成它。导出完成后的游戏需要付费的完整版。
8-Puzzle Solver: Learn A* Search by Building a Sliding Puzzle Game
你在自己的拼图游戏中如何处理提示?这种类似求解器的 live solver(提前计算好的解),还是手动编写的提示?
评论 (0)