贵阳企业做网站,寿光专业做网站的公司有哪些,为什么我网站打不开,中国五大网站建设公司博弈之威佐夫博弈详解 标签#xff1a; 数学博弈游戏威佐夫algorithm2014-03-21 10:40 5330人阅读 评论(1) 收藏 举报分类#xff1a;博弈#xff08;6#xff09; 版权声明#xff1a;本文为博主原创文章#xff0c;未经博主允许不得转载。 威佐夫博弈是博弈中的另一个经… 博弈之威佐夫博弈详解 标签 数学博弈游戏威佐夫algorithm 2014-03-21 10:40 5330人阅读 评论(1) 收藏 举报 分类 博弈6 版权声明本文为博主原创文章未经博主允许不得转载。 威佐夫博弈是博弈中的另一个经典模型。 问题首先有两堆石子博弈双方每次可以取一堆石子中的任意个不能不取或者取两堆石子中的相同个。先取完者赢。 分析首先我们根据条件来分析博弈中的奇异局势 第一个0 0先手输当游戏某一方面对 0 0时他没有办法取了那么肯定是先手在上一局取完了那么输。 第二个 1 2 先手输先手只有四种取法 1取 1 中的一个那么后手取第二堆中两个。 2取 2 中一个那么后手在两堆中各取一个。 3在 2 中取两个那么后手在第一堆中取一个。 4两堆中各取一个那么后手在第二堆中取一个。 可以看出不论先手怎么取后说总是能赢。所以先手必输 第三个 3 5 先手必输。首先先手必定不能把任意一堆取完如果取完了很明显后手取完另一堆先手必输那么 假如看取一堆的情况假设先手先在第一堆中取。 取 1 个后手第二堆中取4个变成1 2了上面分析了是先手的必输局。 取 2 个后手第二堆中取3个也变成 1 2局面了。 假设先手在第二堆中取取 1 个那么后手在两堆中各取 2 个也变成 ( 1 , 2 )局面了。 取 2 个 那么后手可以两堆中都去三个 变成 0 0局面上面分析其必输。 取 3 个后手两堆各取 1 个 变成 1 2局面了。 取 4 个后手在第一堆中取一个变成 1 2局面了。 可见不论先手怎么取其必输 第四个4 7先手必输。 自己推理可以发现不论第一次先手如何取那么后手总是会变成前面分析过的先手的必输局面。 那么到底有什么规律没有呢我们继续往下写。 第四个 6 10 第五个 8 13 第六个 9 15 第七个 11 18 会发现他们的差值是递增的为 0 1 2 3 4 5 6 7.....n 而用数学方法分析发现局面中第一个值为前面局面中没有出现过的第一个值比如第三个局面前面出现了 0 1 2那么第三个局面的第一个值为 3 比如第五个局面前 面出现了 0 1 2 3 4 5 ,那么第五个局面第一个值为6。 再找规律的话我们会发现第一个值 差值 * 1.618 而1.618 sqrt5 1 / 2 。 大家都知道0.618是黄金分割率。而威佐夫博弈正好是1.618这就是博弈的奇妙之处 下面来看看威佐夫博弈常见的三类问题 1给你一个局面让你求是先手输赢。 有了上面的分析那么这个问题应该不难解决。首先求出差值差值 * 1.618 最小值 的话后手赢否则先手赢。注意这里的1.618最好是用上面式子计算出来的否则精 度要求高的题目会错 2给你一个局面让你求先手输赢假设先手赢的话输出他第一次的取法。 首先讨论在两边同时取的情况很明显两边同时取的话不论怎样取他的差值是不会变的那么我们可以根据差值计算出其中的小的值然后加上差值就是大的一个值当 然能取的条件是求出的最小的值不能大于其中小的一堆的石子数目。 加入在一堆中取的话可以取任意一堆那么其差值也是不定的但是我们可以枚举差值差值范围是0 --- 大的石子数目然后根据上面的理论判断满足条件的话就是一种合理的取法。
