射击队状态同步问题

在阅读 《通灵芯片》 的时候, 书中提到一个关于有限状态机的冷门但是有趣的问题,叫做 射击队同步问题

假设你是一名将军,指挥排成长长一行队伍的士兵。由于队伍太长, 你无法大声下达「开火」命令,于是你只好向队伍中的第一名士兵下达命令,要他传给第二个, 再依次传递下去。难的是,全队士兵必须同时开火。虽然有节奏的战鼓响个不停,但你不能指望规定在多少点鼓声之后一齐开火, 因为你并不清楚到底有多少士兵。

这个问题的实质就是设计一排相同的有限状态机,每个状态机只能看到其相邻状态机的情况。 在每一帧时钟前进时,每个状态机都可以跳转一次状态。 需要满足,对于无论多少个士兵的情况,当一端收到开始命令后,总能在时钟前进有限次数后, 所有士兵都运转到同一个状态。

这个问题并不容易,是一个有名的难题

射击队同步问题在 1957 年提出,第一个解决方案由计算机科学家 约翰·麦卡锡马文·闵斯基 在 1962 年给出,包含 15 个状态,也就是本文中讲述的方案。

解决思路

推荐一个此问题的视频:Firing Squad synchronization problem - Youtube , 结合此视频看,对于理解这个问题本身、和此解决方案有许多帮助。

首先介绍士兵的几种状态:

图 1.1 - 士兵的几种状态

  • I - 静止状态 Idle
  • F - 开火状态 Fire
  • R - 举起右手 Hand right raised.
  • L - 举起左手 Hand left raised.
  • A - 右腿迈一步 Right leg at step 1st.
  • B - 右腿迈两步 Right leg at step 2nd.
  • C - 右腿迈三步 Right leg at step 3rd.
  • a - 左腿迈一步 Left leg at step 1st.
  • b - 左腿迈两步 Left leg at step 2nd.
  • c - 左腿迈三步 Left leg at step 3rd.

最开始所有人都出于静止状态。

如果一个士兵看到他左边的人举起右手,那么他就举起右手

图 1.2 - 左边的人举右手,我就举右手

如果右手边没有人,那么换举左手。

图 1.3 - 如果右手边没有人,那么换举左手

就是说, 举右手的动作一路向右传播,到队尾后,换举左手

同理对于左手的情况,会向左一路传到队头,换举右手,不再赘述。

不像举手的动作那样简单,迈腿的动作则分为三步:

图 1.4 - 迈腿的动作分为三步

如果一个士兵看到他左边的人在 C 状态,那么他就进入 A 状态。 通俗点说,左边的人迈右腿快结束了,我才开始迈右腿。

图 1.5 - 迈右腿动作的传播

ABC 是迈右腿、向右传播,abc 则是迈左腿,向左传播。

可以知道,迈腿的传播速度更慢,是举手的传播速度的三分之一。

最开始的时候,让队头的士兵举右手、抬右腿,此时称他是一个将军 General,即处于 G 状态; 同样,对于举左手、抬左腿的情况,也是 G 状态。 凡是手脚并用的情况,都叫将军状态。

图 1.6 - G 状态

现在我们看下 8 个士兵的情况下,一帧一帧地推演,会发生什么?

图 1.7 - 推演 8 个士兵的情况

这是一幅很长的图,可以看到,由于举手比迈腿的传播快三倍,举手的动作传播到队尾后, 又反射回来,正好和迈腿动作在队列中点相遇。 此时,我们让这两个士兵都成为将军,进入 G 状态:

图 1.8 - 迈腿和举手相遇,两个人都成为将军

同样,对于 Rc 相遇的情况,也会使得两个士兵都成为将军。

凡是举手和迈腿两种信号相遇的情况,都会促发将军的诞生。

一个将军会把举手和迈腿的信号向相应方向传播,G 是传播的起点。

如此一来,动作可以分别向左右传播,整个队伍一分为二,左右开弓!

现在,套用前面所说的规则,继续对 8 个士兵的情况推演:

图 1.9 - 继续推演 8 个士兵的情况

可以看到,经过不断的二分,最终所有士兵都成为了将军。

如果一个士兵自己是将军,且两边的士兵也都是将军,那么他可以开火。

图 1.10 - 所有士兵成为将军,即可开火

最后把所有步骤连起来看一下:

图 1.11 - 8 个士兵的情况动图

至此,我们已经知道 8 个士兵的队伍如何运作了。

8 是个特殊的数字,它是 2 的次幂。我们知道 8 个士兵的情况后, 也就知道了 4 个、16 个、32 个士兵 … 的情况了。

不过,奇数个士兵的情况要稍微复杂一点。我们如果知道奇数个士兵的情况如何解决, 那么就知道所有的情况了。

奇数个士兵的情况

来推演一下 7 个士兵的情况。

在最开始的阶段,和前面 8 个士兵的情况差不多,不同的是,这一次是 AL 相遇。

图 2.1 - 7 个士兵的情况

AL 相遇,也算是迈腿和举手两种动作传播的碰撞,不同的是这一次只需要 A 变为 G , 这样,才得以使队伍一分为二。

可以看到这个将军状态和前面的不太一样,他双手举起、双腿迈出。

图 2.2 - A 和 L 相遇的情况

我们可以把这种 G 状态,看成两个将军的综合:

图 2.3 - 这个将军可以看做两个将军的综合

这样,两个将军将分别向左右传播举手和迈腿的动作,达到二分的目的!

同样地,Ra 相遇,也会让 a 变为 G

现在继续推演,可以看到新增了两个状态:

图 2.4 - 继续推演 7 个士兵的情况

新增的两个状态是 bBcC ,它们也可以看做两个士兵的综合:

图 2.5 - `bB` 和 `cC` 也可以看做综合状态

回到图 2.1 继续推演 7 个士兵的情况:

图 2.6 - 继续推演 7 个士兵的情况

最终,7 个士兵全部运转到同一个状态。

其中,可以看到两个新的状态 RLLR ,这两个组合状态,也可以看做两个士兵的综合, 状态转变就是交换左右手,不再赘述。

图 2.7 - `RL` 和 `LR` 虚拟为两个士兵的综合状态

最后把所有步骤连起来看一下:

图 2.7.1 - 7 个士兵的情况动图

奇数个士兵的情况已经解决,综合前面 2 的次幂的情况下的思路, 我们已经完成全部情况的思路。

至此,我们一共使用了 15 个状态 (三个将军状态算作一种),让它们集中亮个相吧!

图 2.8 - 15 个状态

我们真的可以把三种 G 状态算作一个吗?

事实上,三种 G 的传播方向不同,有向左传播的、有向右传播的,还有两边传播的; 并且,三种 G 状态的后续状态也不一样。

但是,可以根据左右邻居的状态判断接下来的传播方向和后续状态。

如果当前士兵处于 G 状态,那么:

  • 如果两边的士兵都是静止状态,那么就是双向传播,也即转换为 bB 状态。
  • 如果只有左边的士兵是静止状态,那么就向左传播,也即转换到 b 状态。
  • 如果只有右边的士兵是静止状态,那么就向右传播,也即转换到 B 状态。

更多的示例

下面分别是 8 个、7 个、13 个士兵 的情况:

图 3.1 - 8 个士兵、7个士兵的情形

图 3.2 - 13 个士兵的情形

可以看到,这个解决方案的精髓,就是用两个信号的碰撞,不断二分的过程。

时间复杂度

图 4.1 - 15 个状态方案下 n 个士兵的情况下的时间开销

假设士兵的总人数是 n ,那么采用当前方案,到达开火状态的时间开销可以计算得出, 注意 几何级数 收敛:

\[time = \frac {3n} {2} + \frac {3n} {4} + \frac {3n} {8} + \ldots \\= 3n \sum^{\infty }_{n=1} \frac{1}{2^n} \\= 3n\]

也就是说,n 个士兵的队伍,在当前方案下,需要 3n 帧时间后才可以开火。

程序实现

思路清楚后,程序实现并不难, 分析出每个状态机的跳转函数是关键的, 不止需要关注前面所讲的跳转条件,还有 “放下手”、”收回腿” 等隐性的状态跳转。

射击队问题 - 状态跳转函数 - Python
def next(l, s, r):
    if s == A:
        if r[0] == "L":
            return G
        return B
    if s == B:
        return C
    if s == C:
        if r[0] == "L":
            return G
        return I
    if s == a:
        if l[-1] == "R":
            return G
        return b
    if s == b:
        return c
    if s == c:
        if l[-1] == "R":
            return G
        return I
    if s == "bB":
        return cC
    if s == "cC":
        if l[-1] == "R":
            return G
        if r[0] == "L":
            return G
        return I
    if s == G:
        if (l + r) in ("$$", "$G", "G$", "GG"):
            return F
        if r == I and l == I:
            return bB
        if r == I:
            return B
        if l == I:
            return b
    if s == L:
        if l == "$":
            return R
        if l[-1] == "R":
            return R
        if l[-1] == "C":
            return G
        if r == G:
            return L
        return I
    if s == R:
        if r == "$":
            return L
        if r[0] == "L":
            return L
        if r[0] == "c":
            return G
        return I
    if s == LR:
        if l[-1] == "C" or r[0] == "c":
            return G
        return I
    if s == RL:
        return LR
    if s == I:
        if l == G or l[-1] == "R":
            if r == G or r[0] == "L":
                return RL
            return R
        if r == G or r[0] == "L":
            if l == G or l[-1] == "R":
                return RL
            return L
        if l[-1] == "C":
            return A
        if r[0] == "c":
            return a
    return s

源码参见 Firing_squad_synchronization_problem - github


最后,这个问题非常有趣!

参考链接:

(完)

本文原始链接地址: https://writings.sh/post/firing-squad-synchronization-problem

王超 ·
微信扫码赞赏
评论 首页 | 归档 | 算法 | 订阅