《算法合集之染色法和构造法在棋盘上应用用.pptx》由会员分享,可在线阅读,更多相关《算法合集之染色法和构造法在棋盘上应用用.pptx(22页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、构造法直接列举出某种满足条件的数学对象或反例导致结论的肯定与否定,或间接构 造某种对应关系,使问题根据需要进行转化的方法,称之为构造法。染色法用不同颜色对棋盘格子进行染色,起到分类的效果。类似国际象棋盘上的黑白二染色,称为“自然染色”。棋盘 所谓m*n棋盘,指由m行n列方格构成的m*n矩形。每个方格成为棋盘的格,位于 第i行j列的格记为a(i,j)。当i+j为奇(偶)数时,称a(i,j)为奇(偶)格。1 1 基本概念第1页/共22页2 2 棋盘的覆盖棋盘的覆盖指用若干图形去覆盖棋盘。覆盖的每个图形也由若干格子组成,称为覆盖形。约定任两个覆盖形互不重叠,任一覆盖形中任一格总与棋盘上某格重合。按覆
2、盖效果,可分为完全覆盖、饱和覆盖、无缝覆盖和互异覆盖。完全覆盖:各个覆盖形的总格子数等于棋盘的总格子数按覆盖形,可分为同形覆盖(只有一种覆盖形)和异形覆盖(有多种覆盖形)。第2页/共22页2-1 2-1 同形覆盖例1 给出m,n,k,试用若干1*k的矩形覆盖m*n的棋盘。l分析l有定理1:m*n棋盘存在1*k矩形的完全覆盖的充分必要 条件是k|m或k|n。l证明:l充分性是显然的。用构造法。当k|n时,每一行用n/k个1*k的矩形恰好完全覆盖。k|m情况类似。l必要性。当n,m均不能被k整除时,设lm=m1*k+r,0rkln=n1*k+s,0s=s(否则旋转90)第3页/共22页2-1 2-
3、1 同形覆盖m=m1*k+rn=n1*k+sr=s第4页/共22页2-1 2-1 同形覆盖由上面的定理1,可彻底解决m*n棋盘的p*q矩形完全覆盖问题定理2 m*n棋盘存在p*q矩形的完全覆盖充分必要条件是m,n满足下列条件之一:(i)p|x且q|y(ii)p|x,q|x,且存在自然数a,b,使y=ap+bq其中x,y=m,n第5页/共22页2-2 2-2 异形覆盖 例2 设有m*n的棋盘,当m*n为奇数时,尝试删去一个格子,剩下部分用若干1*2的矩形覆盖;当m*n为偶数时,尝试删去两个格子,剩下部分用若干1*2的矩形覆盖。l分析:l1先来考虑m*n为奇数的情况l一方面,将棋盘自然染色。无论怎
4、么放,一个1*2的矩形必盖住一个黑格和一个白格,而棋盘上的黑格比白格多1,于是只能去掉一个黑格(即偶格)。第6页/共22页2-2 2-2 异形覆盖 另一方面,设去掉偶格为a(i,j),用构造法必能得到可行解li与j同为奇数li与j同为偶数第7页/共22页2-2 2-2 异形覆盖 再考虑m*n为偶数的情况 类似地,由自然染色法得知,去掉的两格必定异色,即一个奇格,一个偶格(不然两种格子总数不等)另一方面,用构造法,总可以用一些粗线将棋盘隔成宽为1的长条路线,使从任一格出发可以不重复地走遍棋盘并回到出发点。第8页/共22页2-2 2-2 异形覆盖 针对染色法,上面的例子都是利用“各类颜色格子总数必
5、须相等”这一条件推出矛盾,但有些时候,只考虑这个条件是不够充分的。l例38*8棋盘剪去哪个方格才能用21个1*3的矩形覆盖?l分析l考虑到对称性,只有剪去a(3,3)、a(3,6)、a(6,3)、a(6,6)中的某一个才能满足题意。蓝色:21个白色:22个黑色:21个第9页/共22页覆盖类问题其实是一个难度较大的课题,这里只讨论了一些简单的情况,以说明染色法与构造法的应用需要补充的是,染色法的种类形形色色、五花八门。考虑到可推广性和易操作性,本文只着重研究了“间隔染色法”(即自然染色法的推广)2-3 2-3 小结 第10页/共22页3 3 马的遍历 马行走规则 从2*3的矩形一个角按对角线跳到
6、另一个角上马的遍历 从一个格出发按跳马规则不重复地走遍所有格棋盘中马的遍历问题分两类 (1)马的哈密尔顿链 (2)马的哈密尔顿圈 第11页/共22页3-2 3-2 马的哈氏链通常有三种方法 贪心法每一步跳向度最小的点(度数指可一步到达且未经过的点的个数)分治法将棋盘分成几个小棋盘,分别找哈氏链,再接起来 镶边法先在一个小棋盘中找到哈氏链,然后在棋盘四周镶边,已产生大棋盘的哈氏链。按上述方法不难得到下面结论:n*n棋盘存在哈氏链的充要条件是n3。第12页/共22页3-2 3-2 马的哈氏圈例4 求n*n棋盘的哈氏圈 l分析:l将棋盘自然染色,考察无解情况。l马无论怎么走,都必须按黑格白格黑格白格
7、如此循环。由于要回到起点(起点与终点同色),途经两种颜色的格子数必相等,可知n为奇数时无解。l因为大小限制,n=6且为偶数时,用镶边法构造ln*n的大矩形是由(n-4)*(n-4)的小矩形套上一个宽为2的环组成的。而宽为2的环有一个特点,就是可用四条回路A、B、C、D刚好覆盖l假设(n-4)*(n-4)的棋盘已找到哈氏圈l那么只要设法将A、B、C、D四条回路嵌入其中,则n*n的矩形的哈式圈就构造出来了第14页/共22页3-2 3-2 马的哈氏圈l1)n除以4余2时,l在内矩形四个角(A、E、I、M)上分别开口。l1将C与D所在的外回路与“内矩形”的回路在A、B上对接,变成A-C-D-Bl2将G
8、与H所在的外回路与“内矩形”的回路在E、F上对接,变成E-G-H-Fl3将K与L所在的外回路与“内矩形”的回路在I、J上对接,变成I-K-L-Jl4将O与P所在的外回路与“内矩形”的回路在M、N上对接,变成M-O-P-N116192674202525182715261783624213211289351423303312223134131029第15页/共22页3-2 3-2 马的哈氏圈l2)n除以4余0时l在内矩形四个角(A、E、I、M)上分别开口。l1将C与D所在的外回路与“内矩形”的回路在A、B上对接,变成A-C-D-Bl2将G与H所在的外回路与“内矩形”的回路在E、F上对接,变成E-G
9、-H-Fl3将K与L所在的外回路与“内矩形”的回路在I、J上对接,变成I-K-L-Jl4将O与P所在的外回路与“内矩形”的回路在M、N上对接,变成M-O-P-N15447384952312646392533227225155643748350253040455633282342163366144572029246041341512581935624358171013642591611147189第16页/共22页3-2 3-2 马的哈氏圈l一个猜想:lm*n(m=n)棋盘不存在不存在哈氏圈的充要条件是:lm,n满足下列条件之一l(1)m,n都是奇数l(2)m=1,2或4l(3)m=3且n=4,
10、6,8l还没有证明第17页/共22页 其它应用例5 蠕虫世界(Uva)蠕虫在一张N*N的网上爬行。每个网格上有一个数字,蠕虫不能经过相同的数字两次。开始的时候,蠕虫任意选择一个格子作为起始点。它爬行只能沿水平或竖直方向,且不能超出网外。蠕虫如何移动才能到达尽可能多的网格呢?右面是一个样例。第18页/共22页 其它应用 分析:采用“染色法”贪心出一个上界。1 自然染色 2 设Tfree,Tblack,Twhite分别记录三类格子数量 对每一种数字(1,2,3)分析 1)只 存 在 标 有 该 数 字 的 白 色 格 子,TwhiteTwhite+1 2)只 存 在 标 有 该 数 字 的 黑 色 格 子,TblackTblack+1 3)存 在 标 有 该 数 字 的 黑 白 两 色 格 子,TfreeTfree+1 3 估价上界 Lmax=(Twhite+Tfree)*2+1(Twhite+TfreeTblack)Twhite+Tfree+Tblack(Twhite+TfreeTblack)(假设Twhite=Tblack,否则交换即可)第19页/共22页5 5 结语存在性问题 l染色法l可行性问题l构造法l在以棋盘为模型的问题中,综合运用这两种方法,双管齐下,往往能收到事半功倍的效果!第20页/共22页 谢谢!第21页/共22页感谢您的观看!第22页/共22页