放硬币问题的解空间结构
【摘要】
ACM中很多问题，不仅仅是博弈问题，都会涉及到解空间的结构的问题。 了解解空间结构，对于了解问题的本质，非常重要。 放硬币问题： 有一个圆桌，2人轮流在上面放硬币。硬币可以放在桌面上的任何地方，但是不能超出桌面的范围（极端情况是内切） 而且，硬币和硬币不能互相重合（极端情况是外切） 只要桌面上还能继续放，就必须放。如果不能再放，那么游...
ACM中很多问题，不仅仅是博弈问题，都会涉及到解空间的结构的问题。
了解解空间结构，对于了解问题的本质，非常重要。
放硬币问题：
有一个圆桌，2人轮流在上面放硬币。硬币可以放在桌面上的任何地方，但是不能超出桌面的范围（极端情况是内切）
而且，硬币和硬币不能互相重合（极端情况是外切）
只要桌面上还能继续放，就必须放。如果不能再放，那么游戏结束。
现在定义：最后一个放硬币的人是胜者，请问谁有必胜策略，必胜策略是什么。
一，对可行状态的说明
有些地方出现的这个题目没有明确定义，怎么样才算桌面上可以放硬币。
有的人自行脑补，只要硬币放在桌面上不会掉下去即可，还有的人自行脑补，是硬币被桌面覆盖。
我这里采用的是后者，但是实际上，因为两者是一样的。
假设桌面的半径是R，硬币的半径是r，不用说，R自然比r大很多，虽然这并不影响题目的复杂性，但是会影响叙述答案的繁琐程度，所以我先说明R比r大很多。
前者（只要硬币放在桌面上不会掉下去即可）对于可行状态的定义是，桌面和硬币的距离不超过R，
后者（硬币被桌面覆盖）对于可行状态的定义是，桌面和硬币的距离不超过R-r
但是R和r根本没给，所以到底是哪一种无关紧要。
二，对题目合理性的说明
首先，很明显这个题目是没有平局的。
其次，很明显在有限的（比如[R*R/r/r]，[]是高斯函数）步数之内，博弈必将结束。
所以，肯定有一个人有必胜策略。
（对于中国象棋，是否有一个人有必胜策略目前还未知）
三，分析解空间结构，求出解
这个题目，稍微一想就能发现，解空间的结构炒鸡复杂。
我大致能感觉到，解空间是一个无限维的空间。
可惜我不是数学专业的学生，高等代数学的一团糟，这个只是我的推测。
（我所有的博客，里面所有的内容，除了像这样专门说明的，都是我确定的，而不是猜的，当然，不一定正确）
即使如此，本题的关键，仍然是探索解空间结构。
有个十分值得注意的地方，R和r的大小，对于解空间的影响十分巨大，但是题目却没有给出来。
这是很奇怪的，除非——解空间存在一个子集，R和r的大小对这个子集没有影响。
（之所以说子集，而不用子空间这个概念，是因为解空间不是线性空间，我几乎可以确定，它是没有非平凡子空间的。）
既然如此，那么答案就呼之欲出了，很容易就能找到这个子集。
答案便是：先手有必胜策略。
必胜策略是：先手首先在桌面正中间放一枚硬币，然后每次不管后手把硬币放哪里，先手都把硬币放在和它成中心对称的地方。
答案揭晓了，好像没感觉到解空间结构有什么用，不过，继续看就不一样了。
很多博弈问题，将胜负反过来定义，会变得复杂很多，这个问题也是如此。
要求解这个问题，首先得定义3个概念。
1，闭区域的特征值集合：
（这个特征值大致可以理解为能够放下的硬币的数量）
1）如果一个闭区域无法再放硬币，那么它的特征值集合为{0}
（闭区域要想放下一个硬币，必须要覆盖这个硬币，题目中的桌面就是极大的闭区域）
2）如果一个闭区域可以在一个地方放一个硬币，那么放下这个硬币之后剩下的地方仍然是一个闭区域，是原区域的子区域。
如果一个区域的特征值集合是单元集，那它就是固定区域。否则，它就是不固定区域。
不能发现，不固定区域的特征值集合一定是由连续的整数构成的集合。
3，固定区域的奇偶性：固定区域的特征值集合是单元集，我们用其中唯一的那个元素的奇偶性来定义固定区域的奇偶性。
对于圆这个闭区域来说，如果半径较小，那就是固定区域，如果半径较大，那就是不固定区域。
桌面明显比硬币大的多，所以是不固定区域。而且不管在哪放一个硬币，子区域仍然是不固定子区域。
现在关键来了，分析解空间。
（从这里开始，区域都特指，桌面在放了若干个硬币之后得到的子区域。）
不管如何，总会有一个人，某一步操作，将不固定区域变成固定区域。
因为最后将不固定区域变成固定区域的这个人，可以控制这个固定区域的奇偶性，而奇偶性直接对应了胜负，所以这个人就是胜者。
那么，这个人到底是先手还是后手呢？
很巧，这个人仍然是先手，而且先手的必胜策略几乎不变。
必胜策略：
首先在桌面正中间放一枚硬币，
然后每次不管后手把硬币放哪里，先手都把硬币放在和它成中心对称的地方，
最后到了先手将不固定区域变成固定区域的时候，只要选择一个地方放硬币，使得子区域为奇区域，那么他就是胜者了。
无论后面每次两人把硬币放在哪里，放的数量都是固定的，结果也是固定的。
了解解空间结构，对于了解问题的本质，非常重要。
放硬币问题：
有一个圆桌，2人轮流在上面放硬币。硬币可以放在桌面上的任何地方，但是不能超出桌面的范围（极端情况是内切）
而且，硬币和硬币不能互相重合（极端情况是外切）
只要桌面上还能继续放，就必须放。如果不能再放，那么游戏结束。
现在定义：最后一个放硬币的人是胜者，请问谁有必胜策略，必胜策略是什么。
一，对可行状态的说明
有些地方出现的这个题目没有明确定义，怎么样才算桌面上可以放硬币。
有的人自行脑补，只要硬币放在桌面上不会掉下去即可，还有的人自行脑补，是硬币被桌面覆盖。
我这里采用的是后者，但是实际上，因为两者是一样的。
假设桌面的半径是R，硬币的半径是r，不用说，R自然比r大很多，虽然这并不影响题目的复杂性，但是会影响叙述答案的繁琐程度，所以我先说明R比r大很多。
前者（只要硬币放在桌面上不会掉下去即可）对于可行状态的定义是，桌面和硬币的距离不超过R，
后者（硬币被桌面覆盖）对于可行状态的定义是，桌面和硬币的距离不超过R-r
但是R和r根本没给，所以到底是哪一种无关紧要。
二，对题目合理性的说明
首先，很明显这个题目是没有平局的。
其次，很明显在有限的（比如[R*R/r/r]，[]是高斯函数）步数之内，博弈必将结束。
所以，肯定有一个人有必胜策略。
（对于中国象棋，是否有一个人有必胜策略目前还未知）
三，分析解空间结构，求出解
这个题目，稍微一想就能发现，解空间的结构炒鸡复杂。
我大致能感觉到，解空间是一个无限维的空间。
可惜我不是数学专业的学生，高等代数学的一团糟，这个只是我的推测。
（我所有的博客，里面所有的内容，除了像这样专门说明的，都是我确定的，而不是猜的，当然，不一定正确）
即使如此，本题的关键，仍然是探索解空间结构。
有个十分值得注意的地方，R和r的大小，对于解空间的影响十分巨大，但是题目却没有给出来。
这是很奇怪的，除非——解空间存在一个子集，R和r的大小对这个子集没有影响。
（之所以说子集，而不用子空间这个概念，是因为解空间不是线性空间，我几乎可以确定，它是没有非平凡子空间的。）
既然如此，那么答案就呼之欲出了，很容易就能找到这个子集。
答案便是：先手有必胜策略。
必胜策略是：先手首先在桌面正中间放一枚硬币，然后每次不管后手把硬币放哪里，先手都把硬币放在和它成中心对称的地方。
答案揭晓了，好像没感觉到解空间结构有什么用，不过，继续看就不一样了。
很多博弈问题，将胜负反过来定义，会变得复杂很多，这个问题也是如此。
现在重新定义：如果最后一个放硬币的人是败者，请问谁有必胜策略，必胜策略是什么。
（这个想法来自知乎点击打开链接）
要求解这个问题，首先得定义3个概念。
1，闭区域的特征值集合：
（这个特征值大致可以理解为能够放下的硬币的数量）
1）如果一个闭区域无法再放硬币，那么它的特征值集合为{0}
（闭区域要想放下一个硬币，必须要覆盖这个硬币，题目中的桌面就是极大的闭区域）
2）如果一个闭区域可以在一个地方放一个硬币，那么放下这个硬币之后剩下的地方仍然是一个闭区域，是原区域的子区域。
闭区域的所有子区域的特征值集合的并集就是这个闭区域的特征值集合。
如果一个区域的特征值集合是单元集，那它就是固定区域。否则，它就是不固定区域。
不能发现，不固定区域的特征值集合一定是由连续的整数构成的集合。
3，固定区域的奇偶性：固定区域的特征值集合是单元集，我们用其中唯一的那个元素的奇偶性来定义固定区域的奇偶性。
对于圆这个闭区域来说，如果半径较小，那就是固定区域，如果半径较大，那就是不固定区域。
桌面明显比硬币大的多，所以是不固定区域。而且不管在哪放一个硬币，子区域仍然是不固定子区域。
现在关键来了，分析解空间。
（从这里开始，区域都特指，桌面在放了若干个硬币之后得到的子区域。）
不管如何，总会有一个人，某一步操作，将不固定区域变成固定区域。
因为最后将不固定区域变成固定区域的这个人，可以控制这个固定区域的奇偶性，而奇偶性直接对应了胜负，所以这个人就是胜者。
那么，这个人到底是先手还是后手呢？
很巧，这个人仍然是先手，而且先手的必胜策略几乎不变。
必胜策略：
首先在桌面正中间放一枚硬币，
然后每次不管后手把硬币放哪里，先手都把硬币放在和它成中心对称的地方，
最后到了先手将不固定区域变成固定区域的时候，只要选择一个地方放硬币，使得子区域为奇区域，那么他就是胜者了。
无论后面每次两人把硬币放在哪里，放的数量都是固定的，结果也是固定的。
可惜，我在思考另外一个问题（点击打开链接）的时候，发现本文的思路有一点问题，估计结果是不正确的。
文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nameofcsdn/article/details/52615119
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）