贪心算法求解五连珠问题

来源 :科技信息·上旬刊 | 被引量 : 0次 | 上传用户:yyy021
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
  摘要:本文讨论了利用贪心算法求解五连珠问题,建立无限棋盘模型并从局部最优解逐渐过渡到全局最优解。并讨论了模型的优点和局限性。模型能较好地解决五连珠这一数学问题。
  关键词:五子连珠问题;单位元棋盘模型;贪心算法
  引言
  所谓五连珠问题,即在二维平面,有一个大小为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.
其他文献
摘要:本论文试图为虹桥机场某时段的航班建立智能调度系统,在保证机场飞机绝对安全的情况下,最大化提高起降效率,降低延误率。通过动态优先级原理及插值函数方法建立的模型能较好地解决提出的问题,并在此基础之上有较好的扩展性,在适当改进后能解决更加一般的问题。  关键词:调度优化;动态优先级  引言  当今,民航业越来越发达,飞机成为许多人出行的一种选择,人们的出行越 来越方便。但随着飞机流量的增加,机场的
期刊
企业是职工群众最主要的生产生活场所。加强企业工会帮扶工作,使工会帮扶工作重心下移、关口前移,进一步贴近基层、贴近职工,可以使工会帮助和服务职工的工作更及时、更有效、更富有针对性,对于延伸工会帮扶链条,扩大帮扶覆盖面,密切工会与职工群众的联系;对于增强基层工会活力,充分发挥企业工会在协调劳动关系、促进企业发展、服务职工群众中的积极作用;对于促使企业更好地履行社会责任,尽量把职工的困难解决在基层、解决
期刊
摘要:现如今国家不断的发展,不断的推进信息技术对。高职应用文写作教师应当利用多媒体技术、聊天软件、博客网页、精品课网站、微课等信息技术手段来提高学生的学习兴趣,帮助他们开拓视野、提高人文精神、增强职业能力。  关键词:信息技术;高职;中文教学;应用研究  引言  信息技术是学习活动的认知工具,信息技术可以作为课程学习内容和学习资源的获取工具、情境探究和发现学习工具、协作学习和交流讨论的通讯工具、作
期刊
摘要:堤防防渗属于水利工程施工中的核心部分之一,目前在堤防施工中其所应用的防渗技术得到了极大的改进及完善,在日益成熟的技术推动下,使得水利工程的质量也进一步的得到提升。本文通过对水利工程中堤防施工的特点进行分析,指出其中防渗技术使用所起到的作用,在此基础上研究了现今在水利工程中常用的几种防渗技术的要点及其应用方向,以此来为堤防防渗施工提供一点参考建议。  关键词:水利工程;堤防施工;防渗技术  水
期刊
摘要:目前在水利工程的建设中其各类施工技术也在不断的完善,其中土石坝及围堰作为水利工程中的重点施工部分其技术的应用也受到了极大的重视。为此本文通过对土石坝及围堰中的技术要点进行分析来提出在实际的施工中需要注意的技术内容及施工要求,并立足于此研究如何将其施工技术更好的应用于水利工程建设之中,以此来确保水利工程的建设质量可以达到相关的规定标准要求。  关键词:水利工程;土石坝;围堰;施工技术  在水利
期刊
摘要:建筑行业是我国经济发展的支柱型产业,为我国国民经济发展创造了巨大价值。在建筑施工过程中钢筋的应用关系到工程整体质量,钢筋加工及连接施工技术的成熟发展对于我国建筑事业的发展具有强大的推动作用,建筑施工企业应当给予高度重视。本文对钢筋的应用及相关技术做出探究,希望能够为建筑施工企业提供借鉴参考。  关键词:建设进程;社会效益;工程质量;施工需求  引言:  我国社会经济快速发展,城市化建设进程不
期刊
摘要:李煜,作为一代君主他没有建丰功立伟业,但作为一代才子,却留下了不少脍炙人口的传世之作。他的词不管写盛世,还是亡国,都真实纯粹,感人至深。尤其在经历了大风大浪以后淬成的后期作品,思想更加深刻。这主要表现为他此期的作品所渗透的宗教气息。本文将从他对灵魂的忏悔,对命运人生的关注、探索,对精神家园的寻觅与追求方面加以论述。当然,本文所讨论的宗教色彩,是一种非宗教教义的广泛精神的精神现象,是一种真诚地
期刊
摘要:介绍了准格尔盆地中部区块的地层特点,分析了此区块井壁失稳的原因,提出了钻井施工中钻井液技术难点,并总结了对应的钻井液技术措施和现场应用情况。现场施工中,针对地层特点,结合现场小型实验,强化钻井液的抑制防塌、携岩洗井和润滑防卡等措施,保证了董704井的钻进顺利。  关键词:井壁失稳;有机胺;强抑制;造壁性;流变性  准噶尔盆地中部4区块勘探程度较低,仅钻探几口探井。由于对地质构造及地层岩性的认
期刊
摘要:在实际对现代科技以及建筑水平进行衡量时可将玻璃幕墙作为主要标志,这可在一定程度上对我国高层建筑美学的发展进行直观体现,在建筑工程外部防护方面玻璃幕墙所起作用不可替代。但玻璃幕墙也存在一定的局限性,会对人民群众的生命安全以及财产安全造成严重威胁。为实现对上述现象的改善必须在严格执行每一道施工工序的基础上对质量监控工作进行不断的加强,促使玻璃幕墙施工工作得以顺利进行。  关键词:高层建筑;幕墙施
期刊
摘要:基于Deform-3D建立钻削有限元模型,探讨了模拟参数的设置,生成数据库并对成形过程进行了数值模拟。从后处理器处获得了成形过程中的等效应力和应变云图;分析了温度、钻削轴向力和切屑的形态图。  关键词:钻削;有限元模型;Deform-3D;数值模拟  Finite Element simulation on Drilling  (College of Mechanical,Guiyang U
期刊