我来将这段关于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(提前计算好的解),还是手动编写的提示?