当前位置：文档之家 › 国际大学生程序设计竞赛试题与算法分析(二) 回溯算法

国际大学生程序设计竞赛试题与算法分析(二) 回溯算法

  • 格式：pdf
  • 大小：269.76 KB
  • 文档页数：4

信意章赛

令毋次豢绪常寻

嗽

分潇寥

试题与算法分析二回溯

耳法

郭篙山吴汉荣中山大学信息科技学院计算机科学系广州我们在日常生活中经常会遇到一些要求最优解的问题比如说从一个城市到另一个城市怎么走才最快怎么走才最省钱但是在处理一些最优解的问题方面没有任何的理论也无法采用精确的数学公式来帮助我们找到最优解我们只能求助于穷举搜索方法在这里我们介绍一种系统化的穷举搜索技术称为回溯技术所谓的回溯技术就是像人走迷宫一样先选择一个前进方向尝试一步步往前试探在遇到死胡同不能再往前的时候就回退到上一个分叉点选另一个方向尝试而在前进和回撤的路上都设置一些标记以便能正确返回直到达到目标或者所有的可行方案都已经尝试完为止在通常的情况下我们使用递归方式来实现回溯技术也就是在每一个分叉点进行递归尝试在回溯时通常采用栈来记录回溯过程使用栈可使穷举过程能回溯到所要位置并继续在指定层次上往下穷举所有可能的解回溯算法可以用伪码描述如下当前状态当前状态等于目标状态对所有可能的新状态新状态回溯算法是一种十分常用的算法象一些经典问题如八皇后问题骑士周游问题地图着色问题都可以采用回溯算法来解本期将刊登题历年的国际决赛

和区域赛试题供读者分析和学习每道题都先给

出题目然后是算法分析由于篇幅所限我们

只

给出主要的解题思路和算法分析具体的程序实现留给读者自行完成

第一题骨牌矩阵问题描述

多米诺骨牌是一个小正方形方块每个骨牌都标有一个数字一现在有组骨牌每组两

个各组编号为一每组编号对应的两个骨牌数

值如下

骨牌组组骨牌牌骨牌组骨牌牌骨牌组骨牌骨牌组骨牌编号编号编号编号

】现将这组骨牌排成一个矩阵此时只能看到每个骨牌上的数字一而不能知道每组

的组号如图所示请编程将每组骨牌分辨出来见图图中数字为对应图每组骨牌的编号骨牌摆放可旋转例如第组骨牌经旋转可得以

种放法万了

第届亚洲台匕赛区中山大学队教

练

第届亚洲台能赛区中山大学队队长

晦卫卫

翻钧仆伪“仲”曾并翎饥︵匕心公未”从杏少﹄湘用︾骨牌矩阵骨牌组编号矩

阵

图图

如场比代曰曰什州替异知饥︵匕心兮术”片未少毛如剐︶输入格

式

从键盘输人一个文本文件的文件名该文件包含了一个行列的骨牌矩阵每行有个一的整数每个整数之间用空格分开每行的行首

行末无多余空格榆出格式

答案输出到一个文本文件中文件名由键盘输人若问题无解则输出忆

”

若问题有解则将所有可能的解输出每个解之间用一个空行分开最后输出解的总数数字间用空格分开算法分析

这题的算法比较简单只需使用标准的回溯算

法而且由于本题的规模比较小不需要对算法进行优化既可满足时间上的要求

在骨牌矩阵中每组骨牌既可以横放也可以竖放我们可以按从左到右从上到下的顺序对骨牌矩阵中的每个位置进行回溯判断相应的骨牌组应该是横放还是竖放最终目标就是要求二十八组骨牌组都能够不重复地排成一个的矩阵而且每个骨牌上的数字和输人的骨牌矩阵一一对应还要求每组骨牌不互相重叠例程中的过程就是用于回溯的递归过程它先查找下一个还没放置骨牌的位置较如已经超过矩阵的范围而且所有的骨牌组已经放置好则表示已经找到一个解将它输出否则按四

种方式尝试放置个骨牌组假如成功则尝试放置

下一个骨牌组假如不成功就回溯

核心算法是递归放置一个骨牌组

信息穿赛

查找下一个还没放置骨牌的位置

,力

若没有则表示已经找到一个解输出返

回

把在,处的骨牌作为当前骨牌组的一个骨牌把在川处的骨牌作为当前骨牌组的另一个骨牌判断当前骨牌组是否未被使用如果未被使用则递归放置下一个骨牌组把在,处的骨牌作为当前骨牌组的另一个骨牌

判断当前骨牌组是否未被使用如果未被使用则递归放置下一个骨牌组

两种尝试都失败进行回溯

第二题求马的不同走法总数问题描述

在一个的棋盘上马的起始位置坐标纵横位置由键盘输人求马能返回初始位置的所有不同走法的总数马走过的位置不能重复马走旧”字算法分析由于棋盘的大小只有所以只需使用回溯算法搜索马能返回初始位置的所有不同走法效率基本上能达到要求

递归的回溯算法可描述为

是当前位置

马从当前位置出发走一步到位置的每一种走法在棋盘内位置没有走过出发点不同走法总数加

标记已经走过了

取消位置‘的标记

下面讨论算法的具体实现棋盘用坐标表示点表示棋盘上任一个点的范围是‘‘‘‘

从,出发下一步最多有个位置记为……若用表示这个方向则

,

…即马从点出发首先沿的方向行进当

在此方向走完所有的不同走法后就进行回溯改变二方向继续行进

……

。。。乃信窟章赛

各点坐标的计算设点坐标为,则能到达点的坐标分别为一一…

一,一一一为简化坐标的计算引人增

量数组【二一一一一一一一一则按方向能到达点的坐标是

霎入才、、、么夕

产

产门卜、

夕侧

图马的八种不同走法第三题求不连续重复字符序列问题描述

由大写字母中前个字母‘‘组成字符序列所谓不连续重复字符序列是指字符序列中无连续重复的子串例如以下为有连续重复字串的字符序列

又如以下为没有连续重复字串的字符序列

输入和输出请编写程序读人整数和其中‘‘‘输出第个由前个字母组成的不连

续重复字符序列以及这个序列的长度显然第

个不连续重复字符序列为假定由给出的和

中至少存在个不连续重复序列例如当时前个不连续重复序列为

由于所输出序列可能很长因此输出时以每

个字母为组每组用个空格分开每行个字

符输人以两个时用空格分开结束输人样例

输出样例

算法分析由于只要求最大为所以只需使用回溯

算法搜索生成前个不连续重复字符序列并输出第个不连续重复字符序列即可测试时保证不会超时本题的关键在于判断字符序列有无连续重复字串由于我们是一面搜索一面判断的因此当需要判断一个长度为的字符序列有无连续重复字

串时可以确保前一个字符的序列没有连续重复字串只需检查包含第个字符的字串即可因

为如果这个字符序列含有连续重复字串则必定是

由第个字符造成的判断字符序列有无连续重复字串的函数可描述为

检查长度为的字串一一返回有连续

重复字串

返回没有连续重复字串

需要注意的一点是本题最好使用非递归的搜索算法否则容易造成堆栈溢出可以考虑的优化措施有

为了提高信息的利用率对每个字符序列若没有搜索过可搜索至生成前个不连续重

’。。乃

翻场少找曰什州枯豆︸翎饥︵匕心琶未“八上下七湘用︶信息竟赛

复字符序列并用一个字符串数组记录搜索过程然后从中还原出第个字符序列输出若已经搜索

过直接从中还原出第个字符序列并输出当‘时所产生的前个序列是相同的所以可以直接调用的结果求不连续重复字符序列可描述为

初始化

读人新的

和

输人合

法

协声迁的字申还未产生产生的字串

还原出第个序列并输出

二二

把新的序列添加人记录字

串田

已经产生了个字符序列停止搜索

二二,的前一个字符初始化下一层的搜索

一回退一层

把添加人记录字串田

还原的过程可描述为

记录搜索过程和还原出第个字串的实现方法有很多这里对我使用的方法做简单说明非递归的搜索过程可描述为

当前搜索的深度二的前一个字符【当前生成的字符序列

连还未生成个字符序列

二‘前个字母

没有连续重复字串

”让,

一

删除的最后一个字符

二口,

中存放的是还原出来的字串例如二时搜索结束后记录以下字符串一

一一”表示往回退一位

此字串可表示二时的个序列

然后还原出第个序列并输出收稿日期一一

北女女女北流流女女流女女流女女流女流女女北北女女女女北女流流女女交流流北女女北北流女北北

上接第

页

翻坏饰样践曰仲们曹开知仇︵匕心分未

”从山少七湘用︶

数据库包含了主数据库以及帐号权限统计汇总等辅助数据库系统管理模块的功能包含系统初始化原始数

据的录人和修改数据定期备份定期统计收费额并自动划款发送电子邮件等子功能安全维护模

块有帐号管理权限管理操作跟踪用日志记录

等功能实现用户安全性数据安全性操作安全性的全面管理这种系统结构模块化程度高可按资金投人情

况技术水平分步实现较为切实可行小结

综上所述笔者认为远传水表的选用与安装并不复杂工程造价也不高而它可多路集中显示大大减少了抄表的工作量也避免了对住户的

干

扰尤其适用于多层和高层住宅的能源计量管理采用这种科学化的管理方式将会产生相当可观的经济效益和良好的社会效益对我国现行的城市公用事业管理模式的改变起到极大的推动作用收稿日期

一一

合集下载

回溯法_ppt课件

回溯法_ppt课件

//h(i)表示在当前扩展节点处x[t]的第i个可选值
实 现 递 归
} }
if (Constraint(t) &&Bound(t) ) { if (Solution(t)) Output(x); else t ++; } else t --;
if (Constraint(t) &&Bound(t) ) { if (Solution(t)) Output(x); else t ++; } else t --; 分析：
算法设计与分析 >回溯法
5、回溯法解题步骤: 1).针对所给问题,定义问题的解空间 2).确定解空间结构. 3).以深度优先方式搜索解空间.
算法模式 Procedure BACKTRACK(n)； {k:=l； repeat if TK (x1,x2,...xK-1 )中的值未取遍 then { xK:＝TK (x1，x2，..., x K-1 )中未取过的一个值； if BK (x1, x2, ..., x K) then //状态结点(x1,...xk)被激活 if k＝n then output(x1, x2, ..., xk) //输出度优先 e1se k:＝k-l； //回溯 until k＝0； end；{BACKTRACK}
if (Constraint(t)&&Bound(t) ) Backtrack(t + 1)； if语句含义：Constraint(t)和Bound(t)表示当前扩展 节点处的约束函数和限界函数。 Constraint(t): 返回值为true时，在当前扩展节点处 x[1:t]的取值问题的约束条件，否则不满足问题的约束条 件，可剪去相应的子树 Bound(t): 返回的值为true时，在当前扩展节点处 x[1：t]的取值为时目标函数越界，还需由Backtrack(t+1) 对其相应的子树做进一步搜索。否则，当前扩展节点处 x[1：t]的取值是目标函数越界，可剪去相应的子树 for循环作用：搜索遍当前扩展的所有未搜索过的 子树。 递归出口：Backtrack(t)执行完毕，返回t-1层继续 执行，对还没有测试过的x[t-1]的值继续搜索。当t=1时， 若以测试完x[1]的所有可选值，外层调用就全部结束。
第一章回溯法(习题二

第一章回溯法(习题二

1.5 走迷宫(maze.pas)*【问题描述】有一个m * n格的迷宫（表示有m行、n列），其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这m * n个数据和起始点、结束点（起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号）。

现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向（搜索顺寻：左上右下）。

如果一条路都不可行，则输出相应信息（用-1表示无路）。

【输入】第一行是两个数据m，n（1<m，n<15），接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点。

【输出】所有可行的路径，描述一个点时用（x，y）的形式，除开始点外，其它的都要用“->”表示方向。

如果没有一条可行的路则输出-1。

【样例】maze,in5 61 0 0 1 0 11 1 1 1 1 10 0 1 1 1 01 1 1 1 1 01 1 1 0 1 11 15 6Maze.out(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5 )->(5,6)(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5 )->(5,6)(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)1.6 单向双轨道(track.pas)***【问题描述】如图1-1，某火车站有B，C两个调度站，左边入口A处有n辆火车等待进站（从左到右以a、b、c、d编号），右边是出口D，规定在这一段，火车从A进入经过B、C只能从左向右单向开，并且B、C调度站不限定所能停放的车辆数。

回溯算法的基本步骤

回溯算法的基本步骤

回溯算法的基本步骤第一篇嘿，亲爱的小伙伴们！今天咱们来聊聊回溯算法的基本步骤。

第一步呢，就像是要出发去冒险，得先明确目标，知道自己到底要干啥。

比如说，是要找出所有可能的组合，还是要找到满足特定条件的那个唯一答案。

然后呀，咱们得给自己准备一个“背包”，这里面装的就是各种可能的选择。

可别小看这个背包，它可是咱的宝贝。

在这个过程中，还得随时记着自己走过的路。

要是不小心走岔了，还能找回来重新走。

有时候可能会觉得有点迷茫，怎么都找不到对的路。

别灰心，这就是回溯算法的魅力所在，不断尝试，总会有惊喜。

呀，一旦找到了目标，那就欢呼吧！感觉自己就像个超级英雄，成功完成了艰巨的任务。

怎么样，小伙伴们，是不是觉得回溯算法也没那么难啦？第二篇嗨喽！今天来和大家讲讲回溯算法的基本步骤哟！一开始呢，咱们得先把问题看清楚，心里有个底，知道要往哪个方向努力。

这就好比出门前要先搞清楚目的地是哪儿。

接着，就像整理自己的小抽屉一样，把所有可能的办法都整理出来，放在一起。

然后，勇敢地迈出第一步，挑一个办法试试看。

要是这个办法行得通，那就太棒啦，继续往前走。

可要是不行，别着急，赶紧换一个。

在尝试的过程中，要多留个心眼，记住自己试过哪些办法，别在同一个地方摔倒两次。

有时候可能会感觉像是在迷宫里打转，怎么都走不出去。

别害怕，咱们可以回头，重新选择其他的路。

而且呀，每走一步都要问问自己，离目标是不是更近了。

如果不是，那就要重新思考啦。

一直这样不断尝试，不断调整，说不定突然就找到那个完美的答案啦！是不是很有趣呢？好啦，这就是回溯算法的基本步骤，大家明白了吗？。

经典算法题解

经典算法题解

经典算法题解经典算法题解涵盖了各种计算机科学和编程领域的经典问题。

这些题目不仅具有代表性，而且在算法设计和分析方面具有较高的价值。

以下是一些经典算法题解的例子：1. 动态规划：动态规划是一种解决复杂问题的方法，通过将问题分解成子问题，并求解子问题的最优解，从而找到原问题的最优解。

经典动态规划问题包括背包问题、最长公共子序列（LCS）问题、最长递增子序列（LIS）问题等。

2. 贪心算法：贪心算法是一种解决复杂问题的方法，它总是选择局部最优解，以期望达到全局最优解。

经典贪心算法问题包括哈夫曼编码问题、最小生成树（Kruskal算法、Prim算法等）、最短路径（Dijkstra算法等）等。

3. 分治算法：分治算法是一种解决复杂问题的方法，它将原问题分解成规模较小的子问题，并在子问题上求解，最后合并子问题的解得到原问题的解。

经典分治算法问题包括归并排序、快速排序、归并查找等。

4. 回溯算法：回溯算法是一种解决复杂问题的方法，它通过递归的方式，从一条路线上不断地尝试，直到找到一条可行的路径。

经典回溯算法问题包括八皇后问题、数独问题、背包问题等。

5. 深度优先搜索（DFS）和广度优先搜索（BFS）：DFS和BFS 是解决复杂问题的搜索算法，它们通过搜索树或图的方式，寻找问题的解。

经典DFS和BFS问题包括无序集合问题、图的遍历、最短路径等。

6. 字符串匹配算法：字符串匹配算法是解决在文本中查找某个子串的问题。

经典字符串匹配算法包括朴素匹配算法、KMP算法、Boyer-Moore算法等。

7. 数据结构：数据结构是解决计算机科学问题的重要工具。

经典数据结构问题包括链表、栈、队列、树、图等数据结构的操作和应用。

8. 算法复杂度分析：算法复杂度分析是研究算法时间复杂度和空间复杂度的问题。

经典算法复杂度分析问题包括大O标记、大Ω标记、大Ω标记、大Ω标记等。

这些经典算法题解对于提高编程能力和解决实际问题具有很大的帮助。