今天在POJ做了一道博弈题..进而了解到了阶梯博弈...下面阐述一下我对于阶梯博弈的理解..
<wbr>首先是对阶梯博弈的阐述...博弈在一列阶梯上进行...每个阶梯上放着自然数个点..两个人进行阶梯博弈...每一步则是将一个集体上的若干个点( >=1 )移到前面去..最后没有点可以移动的人输..<br><div>
<img src="http://hi.csdn.net/attachment/201108/16/0_1313488616cRqz.gif" alt=""><br>
</div>
</wbr>
如这就是一个阶梯博弈的初始状态 2 1 3 2 4 ... 只能把后面的点往前面放...如何来分析这个问题呢...其实阶梯博弈经过转换可以变为Nim..把所有奇数阶梯看成N堆石子..做nim..把石子从奇数堆移动到偶数堆可以理解为拿走石子..就相当于几个奇数堆的石子在做Nim..( 如所给样例..2^3^4=5 不为零所以先手必败)为什么可以这样来转化?
<wbr><wbr>假设我们是先手...所给的阶梯石子状态的奇数堆做Nim先手能必胜...我就按照能赢的步骤将奇数堆的石子移动到偶数堆...如果对手也是移动奇数堆..我们继续移动奇数堆..如果对手将偶数堆的石子移动到了奇数堆..那么我们紧接着将对手所移动的这么多石子从那个偶数堆移动到下面的奇数堆...两次操作后...相当于偶数堆的石子向下移动了几个..而奇数堆依然是原来的样子...即为必胜的状态...就算后手一直在移动偶数堆的石子到奇数堆..我们就一直跟着他将石子继续往下移..保持奇数堆不变...如此做下去..我可以跟着后手把偶数堆的石子移动到0..然后你就不能移动这些石子了...<span style="color:#ED1C24; word-wrap:normal; word-break:normal; line-height:21px">所以整个过程..将偶数堆移动到奇数堆不会影响奇数堆做Nim博弈的过程..整个过程可以抽象为奇数堆的Nim博弈...</span></wbr></wbr>
<wbr><wbr>其他的情况...先手必输的...类似推理...只要判断奇数堆做Nim博弈的情况即可...</wbr></wbr>
<wbr><wbr>为什么是只对奇数堆做Nim就可以...而不是<span style="color:#FF0000; word-wrap:normal; word-break:normal; line-height:21px">偶数堆</span>呢?...因为如果是对偶数堆做Nim...对手移动奇数堆的石子到偶数堆..我们跟着移动这些石子到下一个奇数堆...那么最后是对手把这些石子移动到了0..我们不能继续跟着移动...就只能去<span style="color:#FF0000; word-wrap:normal; word-break:normal; line-height:21px">破坏原有的Nim而导致胜负关系的不确定</span>...所以<span style="color:#FF0000; word-wrap:normal; word-break:normal; line-height:21px">只要对奇数堆做Nim</span>判断即可知道胜负情况...</wbr></wbr>
分享到:
相关推荐
Algorithm-StairCase-Sequence.zip,2016年初出现的一个数字序列。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Seamless Staircase Electrical Contact to Semiconducting Graphene Nanoribbons
python库。 资源全名:staircase-2.0.3.tar.gz
Number of ways to reach to nth stair using dynamic programming
python库,解压后可用。 资源全名:staircase-0.3.3-py3-none-any.whl
资源来自pypi官网。 资源全名:staircase-0.3.3-py3-none-any.whl
资源分类:Python库 所属语言:Python 资源全名:staircase-2.3.0-py3-none-any.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
knn手写数字识别代码实现,本实验首先使用基于Python实现kNN算法实现手写字识别,然后使用sklearn库的kNN算法实现手写字识别。通过本实验掌握kNN算法的原理,熟悉kNN算法如何应用在真实世界问题中,同时掌握sklearn...
建筑师和设计师的计算工具,可帮助设计楼梯。 软件可以计算出适合于建筑的阶梯的适当高度和高度。 它还可以3D可视化整个楼梯。 语言英语和泰语
Though many millimeter wave (mmWave) channel models have been proposed, few of them concern about staircase environments. This paper analyzes the statistical characteristics of 60 GHz channels in a ...
提出一种消除阶梯效应与增强细节的变分Retinex红外图像增强新算法。将高斯曲率正则项应用到变分Retinex模型的构建中,采用一阶微分对模型添加细节增强约束项,实现细节信息的自适应增强。结合邻域差分,引入曲率滤波...
例如,房屋中有一个阶梯很高的楼梯。戴维斯可以按以下步骤顺序进行操作: 1 1 1 1 1 1 1 1 1 2 2 1 2 1 1 1 2 1 1 2 1 1 1 1 1 2 2 2 2 1 2 1 2 1 1 3 1 3 1 3 1 3 1 1 2 3 3 2这些步骤。 功能说明 在下面的编辑器...
一个MIMO信道仿真实现的例子,有详细的文档说明和完整的代码
楼梯-LED-照明 正在进行的项目:用于 13 个 5050 RGB 条带的控制器电子设备,由 9 个使用并行输出的 TLC5940 驱动
我已经尝试了各种事件,按钮,叠加层,甚至基于注视的交互来提供控件,最后我只是选择了raycaster,然后单击某些带有纹理的浮动对象上的事件。 我也没有使用任何VR耳机进行测试,也无法使用任何VR耳机。 不仅仅是...
hough变换检测直线matlab代码楼梯检测 这是一个图像处理项目,旨在识别图像中是否存在楼梯。 捕获了实时图像的数据集,其中包括一些基本障碍物,例如楼梯,纸箱等。以2秒的间隔拍摄图像以测试检测过程的效率。...
and also a handrail both side of staircase. Slect CE (of cylinder) to get details of spiral staircase height/dia/center of tank details OR you can key in the values. you can select CE for model ...
无尽的楼梯Unity中的一个虚拟现实项目。 玩家可以在虚拟环境中上下楼梯。 需要HTC Vive耳机,并将追踪器固定在鞋子上,以实现平稳的攀爬。 视频演示: :
matlab代码影响Rahnev&Fleming题为“实验程序如何影响元认知能力的估计”的论文数据和代码。 数据和代码都在MATLAB中(已在2018b版上测试)。 这是文件/文件夹的准则: analysis.m:执行所有分析的主要可执行文件 ...