算法分析与设计

算法分析与设计回溯法回溯法回溯法有“通用的解题法”之称，用它可以系统地搜索一个问题的所有解或任一解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先策略搜索。回溯法求问题的所有解时，要回溯到问题的一个解就可结束。这种以深度优先方式系统搜索问题解的算法称为回溯法，它适用于解组合数较大的问题。算法框架回溯法解问题时，首先应定义问题的解空间。问题的解空间中应至少包含问题的一个解。对0-1背包问题来讲，当n=3时，其解空间为：000 010001 100011 101110 111回溯法求0-1背包问题ABCDFEGHIJKLMNO11111110000000W=[16,15,15]P=[45,25,25]C=30回溯法求TSP问题1234306102054ACDEBFGHIJKLMNOPQ1234342423434232算法存在的问题对解空间的组织采用树结构，导致算法的效率比较低下。为了提高算法的效率，通常采用两种策略来避免无效搜索，提高回溯法的效率。（1）利用约束函数在扩展结点处，剪去不满足约束的子树；（2）用限界函数剪去得不到最优解的子树。回溯法的基本步骤（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。递归回溯voidBacktrack(intt){ if(t>n)output(x); else{ for(i=f(n,t);i<=g(n,t);i++){ x[t]=h(i); if(constraint(t)&&bound(t)) Backtrack(t+1); } }}子集树与排列树ABCDFEGHIJKLMNO11111110000000voidBacktrack(intt){if(t>n)output(t);else{for(inti=0;i<=1;i++){ x[t]=i; if(constaint(t) &&bound(t)) Backtrack(t+1);}} }子集树与排列树ACDEBFGHIJKLMNOPQ1234342423434232voidbacktrack(intt){if(t>n)output(x);else{for(i=t;i<=n;i++){swap(x[t],x[i]); if(constraint(t)&&bount(t)) backtrack(t+1); swap(x[t],x[i]);}}}装载问题有一批共n个集装箱要装上2艘重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且当n=3，c1=c2=50，w=[10,40,40]时，可以装船；如果w=[20,40,40]，无法装船。划分问题装载问题基本策略：首先将第1艘船尽可能装满，然后将剩余的集装箱尽可能装到第二艘轮船。约束条件李白打酒话说大诗人李白，一生好饮。幸好他从不开车。一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱：无事街上走，提壶去打酒。逢店加一倍，遇花喝一斗。这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。n后问题在n*n的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n*n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。幻方是把一些数字填写在方阵中，使得行、列、两条对角线的数字之和都相等。欧洲最著名的幻方是德国数学家、画家迪勒创作的版画《忧郁》中给出的一个4阶幻方。他把1,2,3,...16这16个数字填写在4x4的方格中。16??13??11?9??*?15?1表中有些数字已经显露出来，还有些用?和*代替。请你计算出?和*所代表的数字。并把*所代表的数字作为本题答案提交。幻方数素数环是一个计算机程序问题，指的是将从1到n这n个整数围成一个圆环，若其中任意2个相邻的数字相加，结果均为素数，那么这个环就成为素数环。现在要求输入一个n，求n个数围成一圈有多少种素数环，规定第一个数字是1。14325616523412385674125834761476583216743852素数环问题数字排列

将1到20排一列，要求每相邻两位数的和是质数，试求排列的种数。连续邮资问题假设某国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。连续邮箱问题要求对于给定的n和m，给出邮票面值的最佳设计，在1张信封上贴出从邮资1开始，增量为1的最大连续邮资区间。例如当n=5，m=4时，面值为1，3，11，15，32的5种邮票可以贴出邮资的最大连续区间是1到70。回溯法通用的解题法核心在于构造解空间树：子集树排列树回溯法是优化的暴力搜索：不满足限制条件；当前解与最优解进行预计算；学习回溯法：心中有树动态规划适合两个连续步骤之间有联系的问题；回溯法几乎适用于所有的问题，但问题之间最好有明确的层次。总结39级台阶问题小明看完电影《第39级台阶》，离开电影院的时候，他数了数视觉的台阶数，恰好是39级。

站在台阶前，他突然又想起一个问题：如果我每一步只能迈上1个或2个台阶，先迈左脚，然后左右交替，最后一步迈右脚，也就是说一共要迈偶数步。那么，上完39级台阶，有多少种不同的上法呢？

请利用计算机的优势，帮助小明寻找答案。数字排列问题今有7对数字：两个1，两个2，两个3，...两个7，把它们排成一行。要求，两个1间有1个其它数字，两个2间有2个其它数字，以此类推，两个7之间有7个其它数字。如下就是一个符合要求的排列：17126425374635当然，如果把它倒过来，也是符合要求的。请你找出另一种符合要求的排列法，并且这个排列法是以74开头的。注意：只填写这个14位的整数，不能填写任何多余的内容，比如说明注释等。74****4*7*******squareproblem

Givenasetofsticksofvariouslengths,isitpossibletojointhemend-to-endtoformasquare?

4111151020304050817264435yesnoyes回溯法通用的解题法核心在于构造解空间树：子集树排列树回溯法是优化的暴力搜索：不满足限制条件；当前解与最优解进行预计算；学习回溯法：心中有树迷宫系列迷宫问题给定一个m×n(m行,n列)的迷宫，迷宫中有两个位置，gloria想从迷宫的一个位置走到另外一个位置，当然迷宫中有些地方是空地，gloria可以穿越，有些地方是障碍，她必须绕行，从迷宫的一个位置，只能走到与它相邻的4个位置中，当然在行走过程中，gloria不能走到迷宫外面去。令人头痛的是，gloria是个没什么方向感的人，因此，她在行走过程中，不能转太多弯了，否则她会晕倒的。我们假定给定的两个位置都是空地，初始时，gloria所面向的方向未定，她可以选择4个方向的任何一个出发，而不算成一次转弯。gloria能从一个位置走到另外一个位置吗？迷宫问题55...***.**...........*....1113

155...***.**...........*....2113

1

3x3的格子中填写了一些整数。剪格子我们沿着图中的红色线剪开，得到两个部分，每个部分的数字和都是60。本题的要求就是请你编程判定：对给定的mxn的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。如果无法分割，则输出0。罗密欧与朱丽叶的迷宫问题

罗密欧与朱丽叶身处一个m*n的迷宫中，每一个方格表示迷宫中的一个房间。这m*n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8个方向进入未封闭的房间。罗密欧位于迷宫的(p,q)方格中，他必须找出一条通向朱丽叶所在的(r,s)方格中的路。在抵达朱丽叶之前，他必须走遍所在所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数最少。每改变一次前进方向算作转弯一次。请设计一个算法帮助罗密欧找出这样一条道路。罗密欧与朱丽叶的迷宫问题

输入：3(n行数)4(m列数)2(k封闭房间数)1234以上k行表示被封闭房间所在行列1122最后2行分别表示罗密欧和朱丽叶所在的方格输出：6（最少转弯次数）7（不同的最少转弯道路数）1-19821067345-1以上n行m列表示迷宫的一条最少转弯道路。k表示第k步到达，-1表示封闭房间总结构造心中的解空间树是关键；回溯法与函数的局部变量；访问解空间树的优化处理；迷宫问题中的回溯法四邻域八邻域图论问题

最大团问题无向图：连通不连通有向图：弱连通单向连通强连通连通子图（分支）

给定无向图G=(V,E)，如果U

V，且对任意的u,v

U，都有(u,v)

E，则称U是G的完全子图。G的完全子图U是G的一个团当且仅当U不包含在G的更大的完全子图中。G中的最大团是指G中所含顶点数最多的团。

最大团问题符号三角形问题++-+-+++----+-+++--++--+---+右图所示的三角形中，有14个“+“和14个“-”。2个同号下面是+，两个异号下面是-。在一般情况下，符号三角形的第一行有n个符号。符号三角形问题，要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”相同。符号三角形问题++-+-+++----+-+++--++--+---+++-+-+++----+-+++--++--+---+填数字第五届蓝桥杯软件类省赛B组第7题图的m着色问题

给定无向连通图和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的两个顶点有不同的颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边相连接的两个顶点着不同颜色，称这个数m为这个图的色数。求一个图的色数m称为图的m可着色优化问题。给定一个图以及m种颜色，请计算出涂色方案数。图的m着色问题垒骰子问题赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。经过长期观察，atm发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！我们先来规范一下骰子：1的对面是4，2的对面是5，3的对面是6。假设有m组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。atm想计算一下有多少种不同的可能的垒骰子方式。两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。第六届蓝桥杯A组第9题垒骰子问题「输入格式」第一行两个整数nmn表示骰子数目接下来m行，每行两个整数ab，表示a和b数字不能紧贴在一起。「输出格式」一行一个数，表示答案模10^9+7的结果。「样例输入」2112「样例输出」544总结动态规划由小到大构造，不能优化；动态规划适合数据规模较小的问题；回溯由大向小分解，可以优化；回溯可以处理数据规模较大的问题。电路板排列

将n块电路板以最佳排列方案插入带有n个插槽的机箱中，n块电路板的不同的排列方式对应在于不同的电路板插入方案。设B={1,2,...,n}是n块电路板的集合，集合L={N1,N2,...,Nm}是n块电路板的m个连接块。其中每个连接块Ni是B的一个子集，且Ni中的电路板用同一根导线在一起。例如，设n=8,m=5，给定n块电路板及其m个连接块如下：B={1,2,3,4,5,6,7,8}，L={N1,N2,N3,N4,N5}N1={4,5,6},N2={2,3},N3={1,3},N4={3,6},N5={7,8}

电路板排列问题

设x表示n块电路板的排列，即在机箱的第i个插槽中插入电路板x[i]，x所确定的电路板排列密度density(x)定义为跨越相邻电路板插槽的最大连线数。在设计机箱时，插槽一侧的布线间隙由电路板排列的密度所决定，因此电路板排列问题要求对于给定电路板连接条件（连接块），确定电路板的最佳排列，使其具有最小密度。

电路板排列问题最小长度电路板问题

最小长度电路板排列问题是大规模电子系统设计中提出的实际问题。该问题是：将n块电路板以最佳排列方案插入带有n个插槽的机箱中。n块电路板的不同的排列方式对应于不同的电路板插入方案。设B={1,2,...,n}是n块电路板的集合，集合L={N1,N2,...,Nm}是n块电路板的m个连接块，其中每个连接块Ni是B的一个子集，且Ni中的电路板用同一根导线连在一起。在最小长度电路板排列问题中，连接块的长度是指该连接块中第1块电路板到最后一块电路板之间的距离。算法设计：设计一个回溯法，找出所有给n个电路板的最佳排列，使得m个连接块中最大长度达到最小。最小长度电路板问题

输入：8（n）5（m）1111101010011101011010100110100000101001输出：454316287

第k行的第j个数为0表示电路板k不在连接块j中，为1表示电路板k在连接块中。布线问题假设要将一组元件安装在一块线路板上，为此需要设计一个线路板布线方案。各元件的连线数由连线矩阵conn给出。元件i和j之间的连线数为conn(i,j)。如果将i安装在线路板上位置r处，将j安装在位置s处，则元件i和j之间的距离为dist(r,s)。确定了n个元件的位置，就确定了一个布线方案，此方案相应的成本为林含OK设计算法，对于给定的n个元件，计算最佳布线方案，使费用最小。输入：3（n）233输出：10（最少费用）132（最佳布线方案）宝石排列拉丁矩阵问题现有n种不同形状的宝石，每种宝石有足够多颗。欲将这些宝石排列成m行n列的一个矩阵，m<=n，使矩阵中每一行和每一列的宝石都没有相同的形状。试设计一个算法，计算出对于给定的m和n，有多少种不同的宝石排列方案。衣冠坤输入： 33输出： 12排列宝石问题现有n种不同形状的宝石，每种宝石有n颗，共有n2。同一种形态的n棵宝石具有n种不同的颜色。现将n2颗宝石排列成n行n列的一个方阵，使方阵中的每一行和每一列都具有n种不同形状和n种不同颜色。试设计一个算法，计算出对于给定的n，有多少种不同的宝石排宝石列方案。刘士新OK输入： 1输出： 1重复拉丁矩阵问题现有k种不同价值的宝石，每种宝石有足够多颗。欲将这些宝石排列成m行n列的一个矩阵，m<=n，使矩阵中每一行和每一列的宝石数都没有超过规定的数量。另外规定，宝石阵列的第1行从左向右和第1列从上到下的宝石按宝石的价值最小字典序从小到大排列。试设计一个算法，计算出对于给定的k，m和n以及每种宝石的规定数量，有多少种不同的宝石排列方案。衣冠坤输入：4(m)7(n)3(k)223（共k个数，第j个数表示第j种宝石在每行列出现的最多次数）输出：84309

给定n个大小不等的圆，现要将这n个圆排列成一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如，当n=3时，且所给3个圆的半径分别为1，1，2时，这3个圆的最小长度的圆排列如下图所示，其最小长度为

圆排列问题批处理作业调度给定n个作业的集合J={J1,J2,…,Jn}。每一个作业有两项任务分别在两台机器上完成。每个作业必须先由机器1处理，再由机器2处理。作业Ji需要机器j的处理时间为tji，i=1,2,…n，j=1,2。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。则所有作业在机器2上完成处理的时间和f=F21+F22+…+F2n称为该作业调度的完成时间和。批处理作业调度问题要求，对于给定的n个作业，制定最佳的作业调度方案，使其完成时间和最小。批处理作业调度tji机器1机器2作业121作业231作业3231，2，3：3+6+10=192，3，1：4+8+9=21数独问题145327698839654127672918543496185372218473956753296481367542819984761235521839764课后习题子集和问题子集和问题的一个实例为<S,c>。其中S={x1,x2,…,xn}是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得S1中所有元素的和为c。试设计一个解子集和问题的回溯法。魏云鹏OK样例输入： 510 22654样例输出： 226最小重量机器设计问题设某一机器由n个部件组成，每一种价格都可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量，cij是相应的价格。试设计一个算法，给出总价格不超过d的最小重量机器设计。曹琦OK3(n)3(m)4(d)1233212221233212224131价格重量运动员最佳配对问题

羽毛球队有男女运动员各n人，给定2个n*n矩阵P和Q，P[i][j]是男运动员i和女运动员j组成混合双打的男运动员竞赛优势，Q[i][j]是女运动员i和男运动员j配合的女运动员竞赛优势。由于技术配合和心理状态等各种因素的影响，P[i][j]不一定等于Q[j][i]。男运动员i和女运动员j本队组成混合双打的男女双方竞赛优势为P[i][j]*Q[j][i]，设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。高扬OK运动员最佳配对问题输入：3（n）1023234345222353451输出：52PQ无分隔符字典问题

设

={a1,a2,...,an}是n个互不相同的符号组成的符号集。Lk={b1b2...bk|bi

}是中字符组成的长度为k的字符串全体。SLk是Lk的1个无分隔符字典是指对任意的a1a2...akS和b1b2...bkS，有{a2a3...akb1,a3a4...b1b2,...,akb1b2...bk-1}∩S=Φ

无分隔符字典问题要求对给定的n和及正整数k，计算Lk的最大无分隔符字典。张豪输入：2（n）2（k）输出：2n色方柱问题

设有n个立方体，每个立方体的每一面用红、黄、蓝、绿等n种颜色之一染色。要把这n个立方体叠成一个方形柱体，使得柱体的4个侧面的每一侧均有n种不同的颜色。设计一个回溯算法，计算出n个立体的一种满足要求的叠置方案。王彬OK输入：4（n）RGBY021300302101210213133022输出：RBGYRRYRBGRGBGRBGYGYYRBB整数变换问题问题描述：对于整数i的变换f和g分别定义如下：f(i)=3i,g(i)=i/2。设计一个算法，对于给定的2个整数n和m，用最少的f和g变换次数将n变换为m。王鑫例如，可以将整数15用4次变换将它变换为整数4，4=gfgg(15)。输入：15（n）4（m）输出：4gfgg工作分配问题设有n件工作分配给n个人。将工作i分配给第j个人所需要的费用为cij。试设计一个算法，为每个人分配1件不同的工作，并使总费用达到最小。王浩丞OK输入： 3 1023 234 345输出： 9最佳调度问题设有n个任务由k个可并行工作的机器来完成，完成任务i需要的时间为ti。设计一个算法找出完成这n个任务的最佳调度，使得完成所有任务的时间最早。李珊珊OK输入：7（n）3（k）214416653（完成n个任务的时间）输出：17无优先级运算问题给定n个正整数和4个运算符+、-、*、/，且运算符无优先级，如2+3*5=25。对于任意给定的整数m，试设计一个算法，用以上给出的n个数和4个运算符，产生整数m，且用的运算次数最少。给出的n个数中每个数最多只能用1次，但每种运算符可