发布于 

⌈贪心算法⌋田忌赛马策略

田忌赛马

齐使者如梁,孙膑以刑徒阴见,说齐使。齐使以为奇,窃载与之齐。齐将田忌善而客待之。忌数与齐诸公子驰逐重射。孙子见其马足不甚相远,马有上、中、下、辈。于是孙子谓田忌曰:“君弟重射,臣能令君胜。”田忌信然之,与王及诸公子逐射千金。及临质,“孙子曰:‘今以君之下驷与彼上驷,取君上驷与彼中驷,取君中驷与彼下驷。’既驰三辈毕,而田忌一不胜而再胜,卒得王千金。”

思考一个问题: 田忌和齐威王有相同数量的马,他们要在一场比赛中决出胜负,规则是:每匹马只能和对手比赛一次,胜者得一分,负者得零分,最后得分高的一方获胜。田忌和齐威王都是聪明的人,他们都会采用最优策略,田忌想要赢得齐威王的千金,那么田忌应该怎么安排马匹的顺序呢?

贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择,从而希望导致结果是全局最好或最优的算法。贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择,不能回退。动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。

田忌赛马策略

田忌赛马策略是一种贪心算法,它的基本思想是:在每一轮比赛中,田忌都会选择一匹自己最强的马和对手最弱的马进行比赛,这样可以保证自己的马在每一轮比赛中都有机会获胜,使得优势最大化。

所以,田忌在每一次选择时都采取在当前状态下最好的选择,从而希望导致结果是全局最好的算法。

策略如下:
田忌在每一次安排马匹的顺序时,都会选择一匹自己最弱的马和对手最弱比赛,

  • 如果田忌的马赢了,就加一分
  • 如果田忌的马输了,就把这匹下等马送去给对方上等马当炮灰(注意:每一匹马只能比赛一次)

优势洗牌