面向线迷宫机器人的 LSRB 路径化简

左手法则的线迷宫车总能到终点，路线却荒唐地长——每一个死胡同都进一次出一次，压根不管哪条岔路值得走。LSRB 让第一次笨拙的探索跑完之后，第二次跑就变成最优路线，而它几乎不占内存，也几乎不用地图。

需要的数据结构只有一个：一个字符数组。整个东西就这么多。

四种符号

车每离开一个路口就追加一个字符，记录它做了什么：

• L——左转
• S——直行
• R——右转
• B——掉头，只在死胡同出口出现

探索跑完之后，这个串就是走过的路径。而它里面其实埋着应该走的那条路径。

一个洞见

给串里每一个 B 标上：车是在一个无处可去的岔路口掉头的。一个 B 前面和后面的两个转弯合起来，是一次白走的绕行，分成两半。

把 B 和它的邻居一起看——一个 L B L 的三字符窗口。三个动作是“进死胡同再出来”，并且从某个朝向离开。**同样的绕行永远不可能由单个转弯达到。**换成三合一的这个窗口，就没有“进死胡同再出来”这种路线了。

举一个实际的例子。车在中途一个路口朝东到达，走了左岔（L），往北进入一条支路。在死胡同掉头（B）。回到路口时朝南，再走左岔（L），这时车朝东。净效果是：朝东进、朝东出。也就是 S——直穿过去。

六种代换

这六个窗口出现的唯一条件是中间那个字符永远是 B；B 的旁边永远不会出现另一个 B，因为那没有意义：

把左转算作 −90°、直行 0°、右转 +90°、掉头 180°，每一行都是从转弯角相加推出来的。L B L 是 −90 + 180 − 90 = 0°，也就是 S。S B S 是 0 + 180 + 0 = 180°，也就是 B。这张表不值得背——它是算出来的。

反复化简到收敛

一遍是不够的。把一段绕行折叠成两个转弯之后，会产生新的可化简窗口，所以要一遍遍扫描，直到整串不再变化：

void simplify(String& path) {
  bool changed = true;
  while (changed) {                       // a collapse can expose another
    changed = false;
    for (int i = 0; i + 2 < path.length(); i++) {
      if (path[i + 1] != 'B') continue;   // only windows centred on a turn-back
      path = path.substring(0, i) + fold(path[i], path[i + 2])
                                   + path.substring(i + 3);
      changed = true;
      break;
    }
  }
}

主走廊很长也没关系：每折叠一处岔路，就再来一遍，直到无事可做。循环退出的判据是串里再也没有 B——那既证明了收敛，也顺带证明了剩下的每一段绕行都是必要的。

把优化后的路线跑一遍

第二趟就简单得多。决策都没了：车跟着线走，每个路口把化简后的串里下一个字符取出来，照着转对应的弯就行。路口的分类仍然重要——因为到达路口时你得知道自己在哪——但路口的选择现在只是读一个符号。

迷宫车第二趟快得多，原因就在这里。不只是路线变短了；每个路口也不需要再想。要提高基准速度就重放，路线是提前就知道的。

LSRB 做不到什么

LSRB 在完美迷宫上是有效的——没有环，任意两点之间恰好一条路。如果迷宫里有环，左手法则会永远兜圈，而代换规则也无法折叠一个死胡同。

有环是真实存在的，那就需要图搜索。洪水填充正合适：给整座迷宫建一个距离场然后沿梯度下降，迷宫求解模拟器在探索阶段之后就这么跑。LSRB 在迷宫是一棵树时才是对的工具——而胶带线迷宫几乎总是这样——它只花几十字节，而洪水填充要花掉整张栅格的代价。