论文部分内容阅读
摘要：本文讨论了利用贪心算法求解五连珠问题，建立无限棋盘模型并从局部最优解逐渐过渡到全局最优解。并讨论了模型的优点和局限性。模型能较好地解决五连珠这一数学问题。
关键词：五子连珠问题；单位元棋盘模型；贪心算法
引言
所谓五连珠问题，即在二维平面，有一个大小为m×n的棋盘，如果两个棋子所在的小方格共边或共顶点，那么称这两个棋子相连。称五个棋子在一条直线（横、竖、斜方向）上依次相连为五连珠。相应地，在三维空间中，有一个大小为m×n×p的立方体阵列，如果两个棋子所在的立方体共棱、共面或共顶点，那么称这两个棋子相连。据此，提出以下问题：二维情况下，针对任意规模m×n的棋盘，去掉一些棋子使剩下棋子不构成五连珠。
1 定义与符号说明
1.四面子：在二维平面若所取棋子满足横、竖、斜（包含主对角线、次对角线两个方向）共四个方向达到最优取法，称之为“四面子”；相应地，若满足三个方向达到要求，我们称之为“三面子”，同理可得“二面子”、“一面子”。
2.单位元棋盘：满足要求的二维或三维棋盘中去掉棋子的分布是一种有规律的循环排列，最小的循环排列元称之为“单位元棋盘”。
3.初值棋子：在单位元棋盘中需要去掉棋子使棋盘达到要求，而每选取下一个棋子均是由上一个棋子根据一定的方法递推过去的，因此称选取的第一个去掉棋子为“初值棋子”。
4.必去棋子：初值棋子选取好之后，递推出的满足最优解的必定要去掉的棋子称之为“必去棋子”。
5.必不去棋子：必去棋子选取好之后，可以推算出满足最优解的必定不去掉的棋子称之为“必不去棋子”。
6.非必去棋子：必去棋子及非必去棋子确定好之后，剩下的棋子称之为非必去棋子。
2 二维问题的建模与求解
2.1贪心算法
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，每次循环所做出的是在某种意义上的局部最优解。
在使用贪心算法时，我们先把求解的问题分成若干个子问题。再对每一子问题求解，得到子问题的局部最优解。最后把子问题的解局部最优解合成原来解问题的一个解。从下面的流程图可以直观看到贪心算法的建立过程：
2.2 模型的建立——无限棋盘空间的建立
问题二给出的是一个大小为m×n的二维棋盘。为了方便问题解决，我们可以将棋盘抽象为一个没有边界的二维棋盘空间，称为无限棋盘空间Map。这样任意一个棋子的横、竖、斜方向都有五连珠棋子。当算法完成后，我们可以构造一个m×n的观察窗口，截取其中的一部分，即有限棋盘空间Mapm×n作为问题的一个解。
Map的任意方格可以处于三种状态：S0为未确定状态，S1为该方格为棋子，S2为该方格为拿走棋子后的空位。每一方格和棋子均有一相对直角坐标（x，y），规定x正方向为右，y正方向为下。
2.3 模型算法的设计和实现——由局部最优解到全局最优解
首先令Map中所有位置的状态为S0。选取并移去Map上的任意一个状态为S0棋子Cp（x0，y0）。为使Cp的利用率最大化（局部最优），则需要Cp在横、竖、斜一共八个方向上均与连续四个棋子相连。将Cp所在位置标记为S2，再令n=1，2，3，4，{（x0-n，y0），（x0-n，y0-n），（x0，y0-n），（x0+n，y0-n），（x0+n，y0），（x0+n，y0+n），（x0，y0+n），（x0-n，y0+n）}这些棋子所在位置均标记为S1（如图2-1）。再令n=5，对上述集合中的棋子C1～C8重复对Cp的一切操作（若C1～C8中有状态已经为S2的棋子，则直接跳过）。以上步骤中移去的所有棋子记为L（Cp）.对尚处于S0状态的网格重复以上步骤，分别得到L（Cp），L（Cq），L（Cr），L（Cs），L（Ct）.当执行五遍操作后整个棋盘已经被填满，即所有位置处于S1或S2中的一种状态（如图2-2）。由于L（Cp），L（Cq），L（Cr），L（Cs），L（Ct）均为局部最优的取子位置，五者并无冲突，且没有S0狀态的未确定的棋子，则Map中的取子方式一定为全局最优。可以注意到，只有L（Cp），L（Cq）有机会设置S1，而剩余的组只是填补空缺，但不影响算法。
2.4回归有限棋盘空间
当前已经得到了Map中的最优解。当由Map转换到Mapm×n时根据窗口位置的不同，含在窗口内的空位数量并不相同。为了找出Mapm×n下的最优解，需要进一步计算。注意到Map中的图形具有T=5×5的周期性图案。一个周期中网格相对于周期左上角的位置（x’，y’）作为Mapm×n的左上角点，在这25种情况中必有Mapm×n的最优解。
3 模型的评价
3.1 模型的优点
I普适性
很显然，该模型利用编程完成各阶棋盘的计算，在不考虑计算机运算能力的情况下，对棋盘阶数、行列关系等没有任何要求。因此，该模型能够完美地解决任意二维棋盘的五子连珠问题。
II简洁性
模型的输入输出均简洁明了。
3.2 模型缺点
在我们论述过模型的三维扩展性，尽管从理论上讲利用此模型是能够计算三维情况的，但是很遗憾，在实际试验中，我们发现在计算三维情况时，算法出现了问题：我们发现输出的S2情况下棋子坐标总是位于顶层平面上，且当运算进行到下一层时便自动停止了，由此得出的棋子数远小于正确解的个数。这个模型假设每个棋子都能达到最优状态，而这在三维或更高维上是不可行的。
参考文献：
[1]唐益鸣. 2007年全国高中数学联赛五子棋的放置问题[J]. 数学教学，2008，No.25006：44+50.
关键词：五子连珠问题；单位元棋盘模型；贪心算法
引言
所谓五连珠问题，即在二维平面，有一个大小为m×n的棋盘，如果两个棋子所在的小方格共边或共顶点，那么称这两个棋子相连。称五个棋子在一条直线（横、竖、斜方向）上依次相连为五连珠。相应地，在三维空间中，有一个大小为m×n×p的立方体阵列，如果两个棋子所在的立方体共棱、共面或共顶点，那么称这两个棋子相连。据此，提出以下问题：二维情况下，针对任意规模m×n的棋盘，去掉一些棋子使剩下棋子不构成五连珠。
1 定义与符号说明
1.四面子：在二维平面若所取棋子满足横、竖、斜（包含主对角线、次对角线两个方向）共四个方向达到最优取法，称之为“四面子”；相应地，若满足三个方向达到要求，我们称之为“三面子”，同理可得“二面子”、“一面子”。
2.单位元棋盘：满足要求的二维或三维棋盘中去掉棋子的分布是一种有规律的循环排列，最小的循环排列元称之为“单位元棋盘”。
3.初值棋子：在单位元棋盘中需要去掉棋子使棋盘达到要求，而每选取下一个棋子均是由上一个棋子根据一定的方法递推过去的，因此称选取的第一个去掉棋子为“初值棋子”。
4.必去棋子：初值棋子选取好之后，递推出的满足最优解的必定要去掉的棋子称之为“必去棋子”。
5.必不去棋子：必去棋子选取好之后，可以推算出满足最优解的必定不去掉的棋子称之为“必不去棋子”。
6.非必去棋子：必去棋子及非必去棋子确定好之后，剩下的棋子称之为非必去棋子。
2 二维问题的建模与求解
2.1贪心算法
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，每次循环所做出的是在某种意义上的局部最优解。
在使用贪心算法时，我们先把求解的问题分成若干个子问题。再对每一子问题求解，得到子问题的局部最优解。最后把子问题的解局部最优解合成原来解问题的一个解。从下面的流程图可以直观看到贪心算法的建立过程：
2.2 模型的建立——无限棋盘空间的建立
问题二给出的是一个大小为m×n的二维棋盘。为了方便问题解决，我们可以将棋盘抽象为一个没有边界的二维棋盘空间，称为无限棋盘空间Map。这样任意一个棋子的横、竖、斜方向都有五连珠棋子。当算法完成后，我们可以构造一个m×n的观察窗口，截取其中的一部分，即有限棋盘空间Mapm×n作为问题的一个解。
Map的任意方格可以处于三种状态：S0为未确定状态，S1为该方格为棋子，S2为该方格为拿走棋子后的空位。每一方格和棋子均有一相对直角坐标（x，y），规定x正方向为右，y正方向为下。
2.3 模型算法的设计和实现——由局部最优解到全局最优解
首先令Map中所有位置的状态为S0。选取并移去Map上的任意一个状态为S0棋子Cp（x0，y0）。为使Cp的利用率最大化（局部最优），则需要Cp在横、竖、斜一共八个方向上均与连续四个棋子相连。将Cp所在位置标记为S2，再令n=1，2，3，4，{（x0-n，y0），（x0-n，y0-n），（x0，y0-n），（x0+n，y0-n），（x0+n，y0），（x0+n，y0+n），（x0，y0+n），（x0-n，y0+n）}这些棋子所在位置均标记为S1（如图2-1）。再令n=5，对上述集合中的棋子C1～C8重复对Cp的一切操作（若C1～C8中有状态已经为S2的棋子，则直接跳过）。以上步骤中移去的所有棋子记为L（Cp）.对尚处于S0状态的网格重复以上步骤，分别得到L（Cp），L（Cq），L（Cr），L（Cs），L（Ct）.当执行五遍操作后整个棋盘已经被填满，即所有位置处于S1或S2中的一种状态（如图2-2）。由于L（Cp），L（Cq），L（Cr），L（Cs），L（Ct）均为局部最优的取子位置，五者并无冲突，且没有S0狀态的未确定的棋子，则Map中的取子方式一定为全局最优。可以注意到，只有L（Cp），L（Cq）有机会设置S1，而剩余的组只是填补空缺，但不影响算法。
2.4回归有限棋盘空间
当前已经得到了Map中的最优解。当由Map转换到Mapm×n时根据窗口位置的不同，含在窗口内的空位数量并不相同。为了找出Mapm×n下的最优解，需要进一步计算。注意到Map中的图形具有T=5×5的周期性图案。一个周期中网格相对于周期左上角的位置（x’，y’）作为Mapm×n的左上角点，在这25种情况中必有Mapm×n的最优解。
3 模型的评价
3.1 模型的优点
I普适性
很显然，该模型利用编程完成各阶棋盘的计算，在不考虑计算机运算能力的情况下，对棋盘阶数、行列关系等没有任何要求。因此，该模型能够完美地解决任意二维棋盘的五子连珠问题。
II简洁性
模型的输入输出均简洁明了。
3.2 模型缺点
在我们论述过模型的三维扩展性，尽管从理论上讲利用此模型是能够计算三维情况的，但是很遗憾，在实际试验中，我们发现在计算三维情况时，算法出现了问题：我们发现输出的S2情况下棋子坐标总是位于顶层平面上，且当运算进行到下一层时便自动停止了，由此得出的棋子数远小于正确解的个数。这个模型假设每个棋子都能达到最优状态，而这在三维或更高维上是不可行的。
参考文献：
[1]唐益鸣. 2007年全国高中数学联赛五子棋的放置问题[J]. 数学教学，2008，No.25006：44+50.