田忌赛马

来自计算思维百科
跳转至: 导航搜索

中国古代历史故事“田忌赛马”是大家所熟知的。战国时期,齐威王与大将田忌赛马,齐威王和田忌各有三匹好马:上马,中马与下马。比赛分三次进行,每赛马以千金作赌。由于两者的马力相差无几,而齐威王的马分别比田忌相应等级的马要好,所以一般人都以为田忌必输无疑。但是田忌采纳了门客孙膑的意见,用下马对齐威王的上马,用上马对齐威王的中马,用中马对齐威王的下马,结果田忌以2比1胜齐威王而得千金。

这里孙膑所采用的策略就是贪心法。将齐王的马、田忌的马均按上、中、下马顺序排列,齐王依次出马,田忌的贪心选择策略是:

  1. 若剩下的最强的马都赢不了齐王剩下的最强的马,选择用最差的一匹马对阵齐王最强的马;
  2. 若剩下的最强的马可以赢齐王剩下的最强的马,选择用这匹马去赢齐王剩下的最强的马;
  3. 若剩下的最强的马和齐王剩下的最强的马打平的话,可以选择打平或者用最差的马输掉比赛。