两军问题

1. 问题描述

两军问题(Two Generals' Problem),也叫两军悖论(Two Generals Paradox)或协同进攻问题(Coordinated Attack Problem)。

摘自维基百科:

两支军队由不同将军领导,准备进攻一座坚固的城市。军队在城市附近的两个山谷扎营。由于有另一个山谷将两山隔开,两名将军只能透过派信使穿越山谷通信,但这山谷由城市护卫占领,有可能俘虏途径山谷传递消息的任何信使。

虽然两军已约定要同时进攻,但尚未约定进攻时间。要顺利攻击,两军必须同时进攻。如果同一时间仅一支军队进攻就会战败,因此两名将军须约定攻击时间,并确保对方知道自己同意了进攻计划。

File:2-generals.svg

军队位置示意图:军队甲(A1)与乙(A2)派遣信使互相通信,但信使可能被敌军(B)俘虏。

问题:如何在两名将军派出的任何信使都可能被俘虏的情况下,就进攻时间达成共识。

本文系Spark & Shine原创,转载需注明出处本文最近一次修改时间 2023-03-02 21:52

results matching ""

    No results matching ""