本文介绍了搜索与回溯算法在计算机解题中的应用，这是一种常用的算法，适用于那些无法根据确定的计算法则来求解的问题。回溯是搜索算法中的一种控制策略，其基本思想是先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。本章还以迷宫问题为例，详细介绍了搜索与回溯算法的应用过程。

15-搜索算法---回溯.ppt

可以帮助大家对搜索算法的更加深入一步了解，帮助大家熟练地掌握这种算法思想

汉诺塔 题目描述： 约19世纪末，在欧洲的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到中间的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。 这是一个著名的问题，几乎所有的教材上都有这个问题。由于条件是一次只能移动一个盘，且不允许大盘放在小盘上面，所以64个盘的移动次数是：(18,446,744,073,709,551,615)这是一个天文数字，若每一微秒可能计算(并不输出)一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但很难用计算机解决64层的汉诺塔。 假定圆盘从小到大编号为1, 2, ... 输入为一个整数(小于20）后面跟三个单字符字符串。整数为盘子的数目，后三个字符表示三个杆子的编号。 输出每一步移动盘子的记录。一次移动一行。每次移动的记录为例如 a->3->b 的形式，即把编号为3的盘子从a杆移至b杆。 样例输入 2 a b c 样例输出 a->1->c a->2->b c->1->b

给定1个1000行×20列的0-1矩阵，对于该矩阵的任意1列，其中值为1的元素的数量不超过10%。设有两个非空集合A和B，每个集合由矩阵的若干列组成。集合A和B互斥是指对于矩阵的任意一行，同时满足下列2个条件：1）若A中有一个或多个元素在这一行上的值是1，则B中的元素在这一行全部是0；2）若B中有一个或多个元素在这一行上的值是1，则A中的元素在这一行全部是0。请你设计一个算法，找出一对互斥集合A和B，使得A和B包含的列的总数最大。

给定1个1000行×20列的0-1矩阵，对于该矩阵的任意1列，其中值为1的元素的数量不超过10%。设有两个非空集合A和B，每个集合由矩阵的若干列组成。集合A和B互斥是指对于矩阵的任意一行，同时满足下列2个条件：1）若A中有一个或多个元素在这一行上的值是1，则B中的元素在这一行全部是0；2）若B中有一个或多个元素在这一行上的值是1，则A中的元素在这一行全部是0。请你设计一个算法，找出集合A、B和C，满足：1）A、B、C两两互斥，且2）A、B和C包含的列的总数最大。

信息学奥赛一本通-教程PPT课件（第五版）算法部分