当前位置:首页 >> 高中教育 >> 算法设计与分析第五章1 图的搜索算法

算法设计与分析第五章1 图的搜索算法


第五章 图的搜索算法
5.1 图搜索概述 5.1.1 图及其术语 5.1.2 图搜索及其术语 5.2 广度优先搜索 5.2.1 算法框架 5.2.2 广度优先搜索的应用 . . 广度优先搜索的应用

图是一种限止最少的数据结构,因此更接近现实,实际问 是一种限止最少的数据结构,因此更接近现实, 题中很多数据关系都可以抽象成图, 题中很多数据关系都可

以抽象成图,相关问题则可利用图的基 本算法进行求解,很早就有专门研究图的是一门数学学科“ 本算法进行求解,很早就有专门研究图的是一门数学学科“图 论”;其中的计算问题包括图的搜索、路径问题、连通性问题、 其中的计算问题包括图的搜索、路径问题、连通性问题、 可平面性检验、着色问题、网络优化等。图论中的著名算法有: 可平面性检验、着色问题、网络优化等。图论中的著名算法有: 求最小生成树的Kruskal算法、求最短路径的Dijkstra算法 算法、求最短路径的 求最小生成树的 算法 算法 算法、 和Floyd算法、求二部图最大匹配(指派问题)的匈牙利算法、 算法 求二部图最大匹配(指派问题)的匈牙利算法、 求一般图最大匹配的Edmonds“花”算法、求网络最大流和最 花 算法、 求一般图最大匹配的 小割的算法等。 小割的算法等。其中的一些算法在数据结构课程中已经学习过 了。 上一页· 下一页· 返回首页

5.1.1 图及其术语
1.显式图与隐式图 .
在路径问题、连通性问题、可平面性检验、着色 在路径问题、连通性问题、可平面性检验、 问题和网络优化等问题中,图的结构是显式给出的, 问题和网络优化等问题中,图的结构是显式给出的, 包括图中的顶点、边及权重,这类图我们称为显式图 显式图, 包括图中的顶点、边及权重,这类图我们称为显式图, 也就是一般意义上的图 也就是一般意义上的图。 隐式图是由问题的初始结点,为了求解或求证 隐式图是由问题的初始结点, 是由问题的初始结点 问题,根据题目的规则( 问题,根据题目的规则(一般是由题目的意思隐含 给出的),也就是生成子结点的约束条件, ),也就是生成子结点的约束条件 给出的),也就是生成子结点的约束条件,逐步扩 展结点,直到得到目标结点为止的一个隐式的图 隐式的图。 展结点,直到得到目标结点为止的一个隐式的图。

2.显式图的常用术语
v1 v4 v1 v2 v2 v1 v2


v4 v5

v1 4 3 v2 2 9 6

v4

v3

v3

v3



v4



v3

图 5-1

图 5-2

如图5-1所示的 如图 所示的 ⑴, ⑵, ⑶均为显式图 (Graph)。图 。 中的这些点(v1,v2, ,vn)被称为 (v1,v2,…,vn)被称为顶点 中的这些点(v1,v2, ,vn)被称为顶点 (vertex)或结点,连 或结点, 接顶点的曲线或直线称为边 接顶点的曲线或直线称为边 (edge)。 。 通常将这种由若干个顶点以及连接某些顶点的边所组 成的图形称为图 顶点通常被称作是图中的数据元素 成的图形称为图,顶点通常被称作是图中的数据元素 . 上一页· 下一页· 返回首页



带权图: 即图 即图5 给图 带权图:j即图 -2给图 5-1中各图的边上附加一个代表性数据 中各图的边上附加一个代表性数据 (比如表示长度、流量或其他 ),则称其为带权图 。 比如表示长度、 比如表示长度 , 点本身也有边相连, 环 (cycle):图5-1中 ⑶图中的 v 1点本身也有边相连,这种边 : 中 点本身也有边相连 称为环。 称为环。 有限图:顶点与边数均为有限的图, 有限图:顶点与边数均为有限的图,如图 5-1中的三个图均属 中的三个图均属 于有限图。 于有限图。 简单图:没有环且每两个顶点间最多只有一条边相连的图, 简单图:没有环且每两个顶点间最多只有一条边相连的图,如 图 5-1中的 ⑴图。 中的 邻接与关联: 邻接与关联:当( v 1, v 2) ∈E,或 <v 1, v 2 >∈E,即 v , ) , , ∈ , 1, v 2间有边相连时,则称 v 1和 v 2是相邻的,它们互为邻 间有边相连时, 是相邻的, , 间有边相连时 和 是相邻的 接点( ),同时称 接点( adjacent),同时称( v 1, v 2)或 <v 1, v 2 >是与 ),同时称( , ) , 是与 相关联的边。 顶点 v 1、 v 2相关联的边。 、 相关联的边 上一页· 下一页· 返回首页

顶点的度数 (degree):从该顶点引出的边的条数,即与该顶点相 :从该顶点引出的边的条数, 关联的边的数目,简称度。 关联的边的数目,简称度。 入度( 入度( indegree):有向图中把以顶点 v为终点的边的条数称为 ) 为终点的边的条数称为 的入度。 是顶点 v的入度。 的入度 出度( 出度( outdegree):有向图中把以顶点 v为起点的边的条数称 ) 为起点的边的条数称 的出度。 为是顶点 v的出度。 的出度 终端顶点: 的顶点称为终端顶点, 终端顶点:有向图中把出度为 0的顶点称为终端顶点,如图 5-1 的顶点称为终端顶点 中 ⑵图的 v 3。 。 路径与路长:在图 G=( V, E)中,如果存在由不同的边 (v i0, 路径与路长: , 中 , v i1 ), (v i1, v i2 ), …, (v in-1, v in )或是 <v i0, v i1 >, , , , , , 或是 , , <vi 1, v i 2>, …, < v in-1, v in >)组成的序列,则称顶点 v 组成的序列, , , , , 组成的序列 i0, v in是连通的,顶点序列( v i0, v i1, v i2, …, v in) 是连通的, , 是连通的 顶点序列( , , , , ) 的一条道路。 是从顶点 v i0到顶点 v in的一条道路。路长是道路上边的数目, 到顶点 的一条道路 路长是道路上边的数目, v i0到 v in的这条道路上的路长为 n。 到 的这条道路上的路长为 。 连通图: 连通图:对于图中任意两个顶点 v i、 v j ∈V, v i、 v j之间有 、 , 、 之间有 道路相连,则称该图为连通图。 道路相连,则称该图为连通图。如 5-1中的 ⑴图。 中的 网络:带权的连通图, 所示。 网络:带权的连通图,如图 5-2所示。 所示

3.隐式图术语
1)子集树
当要求解的问题需要是在n 个元素的子集中进行搜索, 当要求解的问题需要是在n 个元素的子集中进行搜索,其搜 索空间树被称作子集树 子集树( tree)。 )。这 索空间树被称作子集树(subset tree)。这n个元素都有在子 集中或被选取记为1 不在子集中或被舍去记为0 集中或被选取记为1,不在子集中或被舍去记为0,这样搜索空 间为: 间为: ……, ),(0 ……, (0,0,……,0,0),(0,0,……,0,1), ……, ),(0 ……, (0,0,……,1,0),(0,0,……,1,1), ……( ……, ……(1,1,……,1,1)。 树形结构就是一棵有 个状态。若表示为树形结构就是一棵有2 共2n 个状态。若表示为树形结构就是一棵有2n个叶结点的二叉 对树中所有分支进行遍历的算法都必须耗时O( 树,对树中所有分支进行遍历的算法都必须耗时 (2n)。 上一页· 上一页 下一页· 下一页 返回首页

图5-3

n=3的子集树 的子集树

上一页·

下一页·

返回首页

2)排列树 )
当要求解的问题需要在n 元素的排列中搜索问题的解时, 当要求解的问题需要在 n 元素的排列中搜索问题的解时 , 解空间树被称作排列树 排列树( tree) 解空间树被称作排列树(permutation tree)。 搜索空间为: 搜索空间为: ……, ……, ( 1 , 2 , 3 , …… , n-1 , n ) , ( 2 , 1 , 3 , …… , n-1 , n ) , (2,3,1,……,n-1,n),(2,3,4,1,……,n-1,n), ……, ……, ……, (n,n-1,……,3,2,1) 第一个元素有n 种选择,第二个元素有n-1种选择 种选择, 第一个元素有 种选择,第二个元素有 种选择,第三个 元素有n-2种选择 种选择, 个元素有1种选择 个状态。 元素有 种选择,……,第n个元素有 种选择,共计 个状态。 , 个元素有 种选择,共计n!个状态 若表示为树形就是一个n度树 这样的树有n! 个叶结点, 度树, 若表示为树形就是一个 度树,这样的树有 个叶结点,所以每 一个遍历树中所有节点的算法都必须耗时O(n! ) 一个遍历树中所有节点的算法都必须耗时 上一页· 上一页 下一页· 下一页 返回首页· 返回首页

1 X1=1 2 18 4 13 4 2 3 3 1 29 4 1 35 2 3 34 2 40 4 45 51 4 50

X2=2 3 3 4 4 5 4 6 3 7 2 9 4

3 8

1 19 4 1

3 24

4

1

2 56

3 61

X3=3 … … x4=1 … …

11 14 16 20 22 25 27 30 32 2 3 2 4 3 4 1 3

1o 12 15 17 21 23 26 28 31 33

图5-3

n=4的部分子集树 的部分子集树

上一页·

下一页·

返回首页

4.图的存储
1)邻接矩阵法
邻接矩阵是表示顶点之间相邻关系的矩阵, 邻接矩阵是表示顶点之间相邻关系的矩阵, 是表示顶点之间相邻关系的矩阵 设G=(V,E)是具有n个顶点的图,则G的邻接矩阵可定义为: G=(V,E)是具有n个顶点的图 是具有 的邻接矩阵可定义为: A[i,j]=1 Vi,Vj)或<Vi,Vj>是E(G)中的边 中的边。 A[i,j]=1, 若(Vi,Vj)或<Vi,Vj>是E(G)中的边。 A[i,j]=0 (Vi,Vj)或<Vi,Vj>不是E(G)中的边 不是E(G)中的边。 A[i,j]=0, 若 (Vi,Vj)或<Vi,Vj>不是E(G)中的边。 若G是网络,则邻接矩阵可定义为: 网络,则邻接矩阵可定义为: A[i,j]=Wij 若(Vi,Vj)或<Vi,Vj>属于E(G); Vi,Vj)或<Vi,Vj>属于E(G); 属于E(G) A[i,j]=0或∞ 若(Vi,Vj)或<Vi,Vj> 不属于 或 不属于E(G); ) 其中, 表示边上的权值, 表示一个计算机允许的 表示一个计算机允许的, 其中 , Wij表示边上的权值 , ∞表示一个计算机允许的, 大于 所有边上权值的数; 所有边上权值的数; 上一页· 上一页 下一页· 下一页 返回首页· 返回首页

上一页· 上一页

下一页· 下一页

返回首页· 返回首页

2)邻接表
对于图G中的每个结点Vi, 把所有邻接于Vi的顶点Vj Vi的顶点Vj链成一个 对于图G中的每个结点Vi, 把所有邻接于Vi的顶点Vj链成一个 单链表,这个单链表就称为顶点Vi的邻接表。 Vi的邻接表 单链表,这个单链表就称为顶点Vi的邻接表。 邻接表由边表和顶点两部分组成。 邻接表由边表和顶点两部分组成。 边表为一个单链表,每个表结点均有两个域: 为一个单链表 边表为一个单链表,每个表结点均有两个域: ① 邻 接 点 域 adjvex , 存 放 与 vi 相 邻 接 的 顶 点 vj 的 序 号 j 。 ② 链 域 next , 将 邻 接 表 的 所 有 表 结 点 链 在 一 起 。 顶 点 表 为 一 数 组 , 每 个 元 素 均 有 两 个 域 : ① 顶 点 域 vertex , 存 放 顶 点 vi 的 信 息 指针域firstedge firstedge, 的边表的头指针。 ② 指针域firstedge, vi的边表的头指针。 对于无向图来说,Vi的邻接表中每个表结点都对应于与Vi相 对于无向图来说,Vi的邻接表中每个表结点都对应于与Vi相 的邻接表中每个表结点都对应于与Vi 关联的一条边, 关联的一条边, 对于有向图来说,Vi的邻接表中每个表结点对应于Vi为始点 的邻接表中每个表结点对应于Vi 对于有向图来说,Vi的邻接表中每个表结点对应于Vi为始点 射出的一条边。 射出的一条边。 上一页· 上一页 下一页· 下一页 返回首页· 返回首页 例1·

图7.1

图5-5

图5-1中(1)图的邻接表 中 )

上一页· 上一页

下一页· 下一页

返回首页· 返回首页

5.1.2 图搜索及其术语
1.穷举搜索与启发式搜索
穷举搜索是对图的最基本的搜索算法, 穷举搜索是对图的最基本的搜索算法,是蛮力策略的一种 是对图的最基本的搜索算法 表现形式。即不考虑给定问题的特有性质,按事先定好的顺序, 表现形式。即不考虑给定问题的特有性质,按事先定好的顺序, 依次运用规则,盲目搜索的方法。 依次运用规则,盲目搜索的方法。 启发式搜索是利用一些启发信息, 启发式搜索是利用一些启发信息,提前判断出先搜索哪些 是利用一些启发信息 状态可能尽快找到问题的解或某些情况不可能取到最优解, 状态可能尽快找到问题的解或某些情况不可能取到最优解,从 而可以提前舍弃对这些状态的尝试。 而可以提前舍弃对这些状态的尝试。即考虑给定问题的特有性 选用合适的细则,提高搜索的效率。 质,选用合适的细则,提高搜索的效率。

上一页·

下一页·

返回首页

2.相关概念和术语
问题状态:树中的每一个结点确定所求解问题的一个问题状态。 问题状态:树中的每一个结点确定所求解问题的一个问题状态。 状态空间:由根结点到其它结点的所有路径(分支),就确定 状态空间:由根结点到其它结点的所有路径(分支),就确定 ), 了这个问题的状态空间。 了这个问题的状态空间。 解状态:是这样一些问题状态S,对于这些问题状态,由根到S 解状态:是这样一些问题状态 ,对于这些问题状态,由根到 的那条路径确定了这解空间中的一个元组。 的那条路径确定了这解空间中的一个元组。 答案状态:是这样的一些解状态S,对于这些解状态而言,由 答案状态:是这样的一些解状态 ,对于这些解状态而言, 根到S的这条路径确定了这问题的一个解 根到 的这条路径确定了这问题的一个解 状态空间树:解空间的树结构又称隐式图。 状态空间树:解空间的树结构又称隐式图。

上一页· 上一页

下一页· 下一页

返回首页· 返回首页

活结点: 活结点:如果已生成一个结点而它的所有儿子结点还没有 全部生成,则这个结点叫做活结点。 全部生成,则这个结点叫做活结点。 E-结点:当前正在生成其儿子结点的活结点叫E-结点(正 结点:当前正在生成其儿子结点的活结点叫 结点 结点( 结点 扩展的结点)。 扩展的结点)。 死结点 :不再进一步扩展或者其儿子结点已全部生成的生 成结点就是死结点 。

5.2.1 算法框架
1.算法的基本思路 . 算法设计的基本步骤为:
1)确定图的存储方式; )确定图的存储方式; 2)图的遍历过程中的操作,其中包括为输 )图的遍历过程中的操作, 出问题解而进行的存储操作; 出问题解而进行的存储操作; 输出问题的结论。 3)输出问题的结论。

上一页·

下一页·

返回首页

2.算法框架
从广度优先搜索定义可以看出活结点的扩展是按先来先处 理的原则进行的,所以在算法中要用“ 来存储每个E 理的原则进行的,所以在算法中要用“队”来存储每个E-结点 扩展出的活结点。为了算法的简洁,抽象地定义: 扩展出的活结点。为了算法的简洁,抽象地定义: queue为队列类型 为队列类型, queue为队列类型, 为队列初始化函数, InitQueue( ) 为队列初始化函数, EnQueue(Q,k)为入队函数, EnQueue(Q,k)为入队函数, 为入队函数 为判断队空函数, QueueEmpty(Q) 为判断队空函数, 为出队函数。 DeQueue(Q) 为出队函数。 实际应用中,用数组或链表实现队列。 实际应用中,用数组或链表实现队列。 开辟数组visited记录visited结点的搜索情况 数组visited记录visited结点的搜索情况。 开辟数组visited记录visited结点的搜索情况。 在算法框架中以输出结点值表示“访问” 在算法框架中以输出结点值表示“访问”。 上一页· 上一页 下一页· 下一页 返回首页· 返回首页 例1·

1)邻接表表示图的广度优先搜索算法
int visited[n]; 为结点个数/ /n 为结点个数/ bfs(int k,graph head[]) {int i; queue Q ; edgenode *p; /定义队列 定义队列/ ; ; 定义队列 InitQueue(Q); /队列初始化 队列初始化/ ; 队列初始化 print(“visit vertex”,k); / 访问源点 k/ 访问源点v , ; visited[k]=1; ; EnQueue(Q,k); /vk已访问,将其入队。/ 已访问,将其入队。 , ; while(!QueueEmpty(Q)) /队非空则执行 队非空则执行/ 队非空则执行 { i=DeQueue(Q); / vi出队为 结点 出队为E-结点 结点/ ; p=head[i].firstedge; /取vi的边表头指针 ; 取 的边表头指针/ while(p<>null) /扩展 结点 / 扩展E-结点 扩展 {if(visited[p->adjvex]=0) /若vj未访问过 若 未访问过/ { print (“visitvertex”,p->adjvex);/访问 j/ 访问v , ; 访问 visited[p->adjvex]=1; ; EnQueue(Q,p->adjvex);} /访问过的 j人队 访问过的v , ; 访问过的 人队/ p=p->next ; } /找vi的下一邻接点 找 的下一邻接点/ }

2)邻接矩阵表示的图的广度优先搜索算法 ) bfsm(int k, graph g[][100],int n) , {int i,j; ,; CirQueue Q; InitQueue(Q); ; ; print ("visit vertex", k); /访问源点 k/ 访问源点v , ; 访问源点 visited[k]=1; EnQueue(Q,k); ; , ; while(not QueueEmpty(Q)) {i=DeQueue(Q); ; /vi出队/ 出队 for(j=0;j<G->n;j++) /扩展结点 扩展结点/ 扩展结点 if(g[i][j]==1 and visited[j]=0) {print("visit vertex",j); , ; visited[j]=1; ; EnQueue(Q,j);} , ; /访问过的 j人队/ 访问过的v 人队 访问过的 } } 上一页· 上一页 下一页· 下一页 返回首页· 返回首页

5.2.2 广度优先搜索的应用
【例1】已知若干个城市的地图,求从一个 城市到另一个城市的路径,要求路径中经过的 城市最少 【例2】走迷宫问题

上一页·

下一页·

返回首页·

【例1】已知若干个城市的地图,求从一个城市到 另一个城市的路径,要求路径中经过的城市最少。 算法设计: 图的广度优先搜索类似与树的层次遍历, 图的广度优先搜索类似与树的层次遍历, 逐层搜索正好可以尽快找到一个结点与另一个 结点相对而言最直接的路径。 结点相对而言最直接的路径。

上一页·

下一页·

返回首页·

例2·

例3·

如图5-6表示的是从城市 到城市 的交通图。 如图 表示的是从城市A到城市 的交通图。 表示的是从城市 到城市H的交通图 从图中可以看出,从城市A到城市 到城市H要经过若干个城 从图中可以看出,从城市 到城市 要经过若干个城 现要找出一条经过城市最少一条路线。 市。现要找出一条经过城市最少一条路线。

图5-6

表5-1

图5-6的邻接距阵

上一页· 上一页

下一页· 下一页

返回首页· 返回首页

例2·

例3·

具体过程如下:
将城市A 编号1 入队,队首qh qh置 1)将城市A(编号1)入队,队首qh置 队尾qe置为1 qe置为 为0、队尾qe置为1。 2)将队首所指的城市所有可直通的城 市入队( 市入队(如果这个城市在队中出现过就不 入队),然后将队首加1 ),然后将队首加 入队),然后将队首加1,得到新的队首城 重复以上步骤,直到城市H入队为止。 市。重复以上步骤,直到城市H入队为止。 当搜到城市H 搜索结束。 当搜到城市H时,搜索结束。 3)输出最少城市线路 )输出最少城市线路。

上一页·

下一页·

返回首页·

例2·

例3·

数据结构设计:
线性数组 作为活结点队的存储空间。 数组a作为活结点队的存储空间 1)线性数组 作为活结点队的存储空间。 队列的每个结点有两个成员: 2 ) 队列的每个结点有两个成员 : a[i].city记录入队 记录入队 的城市,a[i].pre记录该城市的前趋城市在队列中的 的城市, 记录该城市的前趋城市在队列中的 下标,这样通过a[i].pre就可以倒推出最短线路 就可以倒推出最短线路。 下标,这样通过a[i].pre就可以倒推出最短线路。 设置数组visited[]记录已搜索过的城市。 记录已搜索过的城市。 3)设置数组 记录已搜索过的城市

上一页·

下一页·

返回首页·

例2·

例3·

算法如下:
search( ) {qh=0; qe=1;sq[1].city=1;sq[1].pre=0;visited[1]=1; while( qh<>qe) /当队不空 当队不空/ 当队不空 {qh=qh+1; /结点出队 结点出队/ 结点出队 for(i=1;i<=n,i++) /扩展结点 扩展结点/ 扩展结点 if (jz[sq[qh].city][i]=1 and visited[i]=0) ) { qe=qe+1; /结点入队 结点入队/ 结点入队 sq[qe].city=i;sq[qe].pre=qh;visited[qe]=1; if (sq[qe].city=8) out( ); } } print(“No avaliable way.”); } 上一页· 下一页· 返回首页· 例2· 例3·

out( ); /输出路径 输出路径/ 输出路径 {print(sq[qe].city); while(sq[qe].pre<>0) {qe=sq[qe].pre; print('--',sq[qe].city);} }

算法分析:时间复杂度是 ( ); );空间复杂性为 算法分析:时间复杂度是O(n);空间复杂性为 ),包括图本身的存储空间和搜索时辅助空间 包括图本身的存储空间和搜索时辅助空间“ (n2),包括图本身的存储空间和搜索时辅助空间“队” 的存储空间。 的存储空间。

【例2】走迷宫问题
迷宫是许多小方格构成的矩形,在每个小方格中有的是墙( 迷宫是许多小方格构成的矩形,在每个小方格中有的是墙(图中的 )。走迷宫就是从一个小方格沿上 “1”)有的是路(图中的“0”)。走迷宫就是从一个小方格沿上、下、左、 )有的是路(图中的“ )。走迷宫就是从一个小方格沿上、 右四个方向到邻近的方格,当然不能穿墙。设迷宫的入口是在左上角(1,1) (1,1), 右四个方向到邻近的方格,当然不能穿墙。设迷宫的入口是在左上角(1,1), 出口是右下角(8,8)。根据给定的迷宫,找出一条从入口到出口的路径。 出口是右下角(8,8)。根据给定的迷宫,找出一条从入口到出口的路径。 (8,8)

上一页·

下一页·

返回首页·

例1·

例3·

算法设计:
从入口开始广度优先搜索可到达的方格入队, 从入口开始广度优先搜索可到达的方格入队,再扩展 队首的方格,直到搜索到出口时算法结束。 队首的方格,直到搜索到出口时算法结束。 对于迷宫中任意一点A( , ),有四个搜索方向: ),有四个搜索方向 对于迷宫中任意一点 (Y,X),有四个搜索方向: 向上A( , ) 向上 (Y-1,X) 向下A( 向下 (Y+1,X) , ) 向左A( , 向左 (Y,X-1) ) 向右A( , 向右 (Y,X+1) ) 当对应方格可行(值为0),就扩展为活结点。 ),就扩展为活结点 当对应方格可行(值为 ),就扩展为活结点。

上一页·

下一页·

返回首页·

例1·

例3·

数据结构设计: 数据结构设计:
数组做队的存储空间 队中结点有三个成员: 做队的存储空间, 用数组做队的存储空间,队中结点有三个成员: 行号、 列号、 前一个方格在队列中的下标。 行号 、 列号 、 前一个方格在队列中的下标 。 搜索过 的方格不另外开辟空间记录其访问的情况, 的方格不另外开辟空间记录其访问的情况 , 而是用 迷宫原有的存储空间置元素值为“ 迷宫原有的存储空间置元素值为 “ -1” 时 , 标识已 经访问过该方格。 经访问过该方格。 fx={1,为了构造循环体,用数组fx={1, 1,0,0}、 为了构造循环体,用数组fx={1,-1,0,0}、 0,0,}模拟上下左右搜索时的下标的变化 fy={ 0,0,-1,1 }模拟上下左右搜索时的下标的变化 过程。 过程。

上一页·

下一页·

返回首页·

例1·

例3·

int jz[8][8]= {{1,0,0,0,1,0,1,1},{0,1,1,1,1,0,1,1}, {0,1,1,0,0,1,1,1}, {0,1,0,1,1,1,0,1}, {1,1,0,1,1,1,0,0},{0,0,1,1,1,1,1,0}, {1,1,1,0,0,1,1,0}, {1,1,1,1,0,0,0,1}}; struct {int city, pre;} sq[100]; int qh,qe,i,visited[100]; main( ) {int i,n=8; for(i=1;i<=n,i=i+1) visited[i]=0; search( ); }

search( ) {qh=0; qe=1;sq[1].city=1; sq[1].pre=0; visited[1]=1; while( qh<>qe) /当队不空 当队不空/ 当队不空 {qh=qh+1; /结点出队 结点出队/ 结点出队 for(i=1;i<=n,i=i+1) /扩展结点 扩展结点/ 扩展结点 if (jz[sq[qh].city][i]=1 and visited[i]=0) ) { qe=qe+1; /结点入队 结点入队/ 结点入队 sq[qe].city=i; sq[qe].pre=qh; visited[qe]=1; if (sq[qe].city=8) out( ); } } print(“No avaliable way.”); }

out( ); {print(sq[qe].city); while(sq[qe].pre<>0) { qe=sq[qe].pre;

/输出路径 输出路径/ 输出路径

print('--',sq[qe].city);} } 算法分析: 算法分析: 算法的时间复杂度并不复杂是 ( ), ),算法的空间复杂性为 算法的时间复杂度并不复杂是O(n),算法的空间复杂性为 的时间复杂度并不复杂是 O(n2),包括图本身的存储空间和搜索时辅助空间“队”的 ( ),包括图本身的存储空间和搜索时辅助空间“ 包括图本身的存储空间和搜索时辅助空间 存储空间。 存储空间。

上一页·

下一页·

返回首页·

例1·

例3·

5.3 深度优先搜索
深度优先遍历首先访问出发点v 深度优先遍历首先访问出发点v,并将其标记为 首先访问出发点 已访问过;然后依次从v出发搜索v的每个邻接点w 已访问过;然后依次从v出发搜索v的每个邻接点w。 未曾访问过,则以w 若w未曾访问过,则以w为新的出发点继续进行深度 优先遍历,直至图中所有和源点v 优先遍历,直至图中所有和源点v有路径相通的顶点 均已被访问为止。 均已被访问为止。 若此时图中仍有未访问的顶点, 若此时图中仍有未访问的顶点,则另选一个尚 未访问的顶点作为新的源点重复上述过程, 未访问的顶点作为新的源点重复上述过程,直至图 中所有顶点均已被访问为止。 中所有顶点均已被访问为止。

深度搜索与广度搜索的相近, 深度搜索与广度搜索的相近,最终都要 扩展一个结点的所有子结点. 扩展一个结点的所有子结点. 区别在于对扩展结点过程, 区别在于对扩展结点过程,深度搜索扩 展的是E 结点的邻接结点中的一个, 展的是E-结点的邻接结点中的一个,并将其 作为新的E 结点继续扩展,当前E 作为新的E-结点继续扩展,当前E-结点仍为 活结点,待搜索完其子结点后, 活结点,待搜索完其子结点后,回溯到该结 点扩展它的其它未搜索的邻接结点。 点扩展它的其它未搜索的邻接结点。而广度 搜索,则是扩展E 结点的所有邻接结点, 搜索,则是扩展E-结点的所有邻接结点,E结点就成为一个死结点。 结点就成为一个死结点。

5.3.1 算法框架

1.算法的基本思路 . 2.算法框架 .

1.算法的基本思路 算法设计的基本步骤为: 算法设计的基本步骤为: 确定图的存储方式; 1)确定图的存储方式; 遍历过程中的操作, 2)遍历过程中的操作,其中包括为输出 问题解而进行的存储操作; 问题解而进行的存储操作; 输出问题的结论。 3)输出问题的结论。 4)一般在回溯前的应该将结点状态恢复 为原始状态,特别是在有多解需求的问题中。 为原始状态,特别是在有多解需求的问题中。

?2.算法框架 . ? ? 1)用邻接表存储图的搜索算法 ) 2)用邻接矩阵存储图的搜索算法 )

head[100]; graph head[100]; dfs(int k) { edgenode *ptr head图的顶点数组 图的顶点数组/ / head图的顶点数组/ ptr图的边表指针 图的边表指针/ / ptr图的边表指针/

visited[k]=1; /* 记录已遍历过 */ print(“访问 print( 访问 ”,k); /* 印出遍历顶点值 */ ptr=head[k].firstedge; /* 顶点的第一个邻接点 */ while ( ptr <> NULL ) /* 遍历至链表尾 */ visited[ptr{if ( visited[ptr->vertex]=0) /* 如过没遍历过 */ dfs(ptrdfs(ptr->vertex); ptrptr = ptr->nextnode; } } 算法分析:n图中有 n 个顶点,e 条边。扫描边的时间为O(e)。 n 个顶点, 条边。扫描边的时间为O(e) O(e)。 遍历图的时间复杂性为O(n+e) O(n+e)。 遍历图的时间复杂性为O(n+e)。 返回 /* 递归遍历 */ /* 下一个顶点 */

?graph graph

n; g[100][100],int n;

?dfsm(int k) dfsm(int j; {int j; print(“访问 print( 访问 ”,k); visited[k]=1; visited[k]=1; for(j=1;j<=n; //依次搜索vk的邻接点 依次搜索vk for(j=1;j<=n;j++) //依次搜索vk的邻接点 if(g[k][j]=1 and visited[j]=0) dfsm(g,j) //(vk,vj)∈E, vj未访问过, vj为新出发点 //(vk,vj)∈E,且vj未访问过,故vj为新出发点 未访问过 } 算法分析:查找每一个顶点的所有的边,所需时间为O(n),遍 查找每一个顶点的所有的边, O(n), 查找每一个顶点的所有的边 所需时间为O(n) 历图中所有的顶点所需的时间为O(n2) O(n2)。 历图中所有的顶点所需的时间为O(n2)。 ? 返回

5.3.2 深度优先搜索的应用
?【例1】走迷宫问题:问题同 .2.2【例2】 【 】走迷宫问题:问题同5. . 【 】 ?1、算法设计:深度优先搜索,就是一直向 :深度优先搜索, 着可通行的下一个方格行进, 着可通行的下一个方格行进,直到搜索到出 口就找到一个解。若行不通时, 口就找到一个解。若行不通时,则返回上一 个方格,继续搜索其它方向。 个方格,继续搜索其它方向。

?2、数据结构设计:我们还是用迷宫本身的存储 : 空间除了记录走过的信息,还要标识是否可行: 空间除了记录走过的信息,还要标识是否可行: ? ? maze[i][j]=3 标识走过的方格 ; maze[i][j]=2 标识走入死胡同的方格, 标识走入死胡同的方格,

?这样,最后存储为“3”的方格为可行的方格。 这样,最后存储为“ 的方格为可行的方格 的方格为可行的方格。 这样 而当一个方格四个方向都搜索完还没有走到出口, 而当一个方格四个方向都搜索完还没有走到出口, 说明该方格或无路可走或只能走入了“死胡同” 说明该方格或无路可走或只能走入了“死胡同”。

?3、算法 int maze[8][8]={{0,0,0,0,0,0,0,0}, {0,11,1,1,0,1,0},{0,0,0,0,1,0,1,0}, {0,1,0,0,0,0,1,0},{0,1,0,1,1,0,1,0}, {0,1,0,0,0,0,1,1},{0,1,0,0,1,0,0,0}, {0,1,1,1,1,1,1,0}};fx[4]={1,{0,1,1,1,1,1,1,0}};fx[4]={1,-1,0,0}, fy[4]={0,0,-1,1}; fy[4]={0,0,main( ) { int total=0; maze[1][1]=3; search(1,1); /入口坐标设置已走标志/ /入口坐标设置已走标志/ 入口坐标设置已走标志 /统计总步数/ /统计总步数/ 统计总步数 int i,j,k,total;

print(“Total is”,total); print( Total is ,total); }

?search(int i, int j) search(int {int k,newi,newj; /搜索可达的方格 搜索可达的方格/ for(k=1;k<=4;k++) /搜索可达的方格/ check(i,j,k)=1) if(check(i,j,k) if(check(i,j,k)=1) {newi=i+fx[k]; newj=j+fy[k]; /来到新位置后 设置已走过标志/ 来到新位置后, maze[newi][newj]=3; /来到新位置后,设置已走过标志/ /到出口则输出 否则下一步递归/ 到出口则输出, if (newi=8 and newj=8) /到出口则输出,否则下一步递归/ else } maze[i][j]=2; } /某一方格只能走入死胡同/ /某一方格只能走入死胡同/ 某一方格只能走入死胡同 Out( ); search(newi,newj);

? Out( ) ? { int i,j; for( i=1;i<=8;i++) ? print(“换行符 换行符” { print( 换行符”); ? for(j=1;j<=8;j++) ? if(maze[i][j]=3) if(maze[i][j]=3) ? {print(“V ); {print( V”); ? /统计总步数 统计总步数/ total++;} /统计总步数/ ? else ? print(“* ); print( *”); ? } ? }

check(int i,int j,int k) {int flag=1; i= i+fx[k]; j= j +fy[k]; /是否在迷宫内 是否在迷宫内/ if(i<1 or i>8 or j<1 or j>8) /是否在迷宫内/ flag=0; else /是否可行 是否可行/ if(maze[i][j]<>0) /是否可行/ flag=0; return(flag); }

? 4、算法说明: : ? 1)和广度优先算法一样每个方格有四个方 ) 向可以进行搜索,这样一点结点(方格) 向可以进行搜索,这样一点结点(方格) 就可多次成为“活结点”,而在广度优先 就可多次成为“活结点” 算法一点结点(方格)就可一次成为“ 算法一点结点(方格)就可一次成为“活 结点” 一出队就成了死结点。 结点”,一出队就成了死结点。 ? 2)用广度优先算法,搜索出的是一条最短 )用广度优先算法, 的路径, 的路径,而用深度优先搜索则只能找出一 条可行的路径,而不能保证是最短的路径。 条可行的路径,而不能保证是最短的路径。 ? 3)在空间效率上二者相近。都需要辅助空 )在空间效率上二者相近。 间。

?【例2】 有如图1所示的七巧板,试编写一 【 】 有如图 所示的七巧板, 所示的七巧板 源程序如下,使用至多四种不同颜色对七巧 源程序如下, 板进行涂色(每块涂一种颜色 每块涂一种颜色), 板进行涂色 每块涂一种颜色 ,要求相邻区域 的颜色互不相同, 的颜色互不相同,打印输出所有可能的涂色 方案。 方案。 ?

?1、问题分析:为了让算法 为了让算法 能识别不同区域间的相邻关 系,我们把七巧板上每一个 区域看成一个顶点若两个区 域相邻, 域相邻,则相应的顶点间用 一条边相连,这样该问题就 一条边相连, 转化为图一个图的搜索问题 了。

?2、算法设计: ? 按顺序分别对1 ......、 按顺序分别对1号、2号、......、7号区域 进行试探性涂色, 号代表4 进行试探性涂色,用1、2、3、4号代表4种颜 色。 ? 则涂色过程如下: 则涂色过程如下: ? 对某一区域涂上与其相邻区域不同的颜色。 1)对某一区域涂上与其相邻区域不同的颜色。 ? 若使用4种颜色进行涂色均不能满足要求, 2)若使用4种颜色进行涂色均不能满足要求, 则回溯一步,更改前一区域的颜色。 则回溯一步,更改前一区域的颜色。 ? 转步骤1继续涂色, 3)转步骤1继续涂色,直到全部区域全部涂 色为止,输出结果。 色为止,输出结果。 ? 已经有研究证明, 已经有研究证明,对任意的平面图至少存在一 种四色涂色法。 种四色涂色法。

?3、数据采用的存储结构:邻接矩阵存储 邻接矩阵存储
– – – – – – – 0 1 0 0 1 0 1 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 1 0 1 1 1 0

1 0 1 1 1 0 0

?4、算法如下: ?int data[7][7],n,color[7],total; int ?main( ) main( ?{ int i,j; { ? for(i=1;i<=n;i++) ? for(j=1;j<=n;j++) ? input(data[i][j]); ? for(j=1;j<=n;j++) ? color[j]=0; ? total=0; ? try(1); ? print('换行符,Total=',total); print('换行符 换行符,Total=',total); ?} }

? try(int s) { int i,; if (s>7) ? output( ); else for(i=1;i<=4;i++) { color[s]=i; colorsame(s)=0 =0) if (colorsame(s)=0) ? try(s+1); } ? }

? output( ) { int i,; print(换行符 换行符, number: print(换行符,serial number:',total); for i:=1 to n do ? print(color[i]); total=total+1; ? }

?colorsame(int s) colorsame(int 判断相邻点是否同色/ /判断相邻点是否同色/ { int i,flag; flag=0; for(i=1;i<=sfor(i=1;i<=s-1;i++) if (data[i][s]=1 and color[i]=color[s]) ? flag=1; ? return(flag) }

?【例3】关结点的判断及消除 【 】 ? ? 1.网络安全相关的概念 ? 在一个无向连通图G 在一个无向连通图G中,当且仅当删 中的顶点v及所有依附于v的所有边后, 去G中的顶点v及所有依附于v的所有边后,可 将图分割成两个以上的连通分量,则称v 将图分割成两个以上的连通分量,则称v为图 关结点,关结点亦称为割点 割点。 G的关结点,关结点亦称为割点。

图5-6 连通图 含有关结点2 (含有关结点2、3、5)

图5-7 连通图 (不含关结点 不含关结点) (不含关结点)

图5-8 删去关结点2 图5-6删去关结点2的结果

? ? 一个表示通信网络的图的连通度越高, 一个表示通信网络的图的连通度越高, 其系统越可靠。 其系统越可靠。 ? 网络安全比较低级的要求就是重连通图。 网络安全比较低级的要求就是重连通图。 在重连通图上, 在重连通图上,任何一对顶点之间至少存在 有两条路径, 有两条路径,在删除某个顶点及与该顶点相 关联的边时,也不破坏图的连通性。 关联的边时,也不破坏图的连通性。即“如 果无向连通图G根本不包含关结点,则称G 果无向连通图G根本不包含关结点,则称G为 重连通图” 重连通图”。 ? 不是所有的无向连通图都是重连通图。 不是所有的无向连通图都是重连通图。

?2.连通图G的关结点的判别 2 连通图G ? 算法设计:连通图中关结点的判别方法如下: 连通图中关结点的判别方法如下: 连通图中关结点的判别方法如下
– 1)从图的某一个顶点开始深度优先遍历图 从图的某一个顶点开始深度优先遍历图, 1)从图的某一个顶点开始深度优先遍历图,得到深度 优先生成树

? 2)用开始遍历的顶点作为生成树地根 用开始遍历的顶点作为生成树地根, 2)用开始遍历的顶点作为生成树地根,一、根 ? 顶点是图的关结点的充要条件是,根至少有两个 顶点是图的关结点的充要条件是, 子 ? 女。二、其余顶点u是图的关结点的充要条件是, 其余顶点u是图的关结点的充要条件是, ? 该顶点u至少有一个子女w,从该子女出发不可能 该顶点u至少有一个子女w 通 ? 过该子女顶点w和该子女w的子孙顶点,以及一条 过该子女顶点w和该子女w的子孙顶点, 回 ? 边所组成的路径到达u的祖先,不具有可行性。 所组成的路径到达u的祖先,不具有可行性。 ? 三、特别的,叶结点不是关结点。 特别的,叶结点不是关结点。

?例:图中,每个结点的外面都有一个数,它 例 图中,每个结点的外面都有一个数, 表示按深度优先检索算法访问这个结点的次 这个数叫做该结点的深度优先数 DFN) 深度优先数( 序,这个数叫做该结点的深度优先数(DFN)。 ?例如:DFN(1)=1,DFN(4)=2,DFN(8)=10等 例如: 例如 DFN(1)=1,DFN(4)=2,DFN(8)=10等 等。

图5-9

图5-6所示的深度优先生成树

? ? 图5-9 (b)中的实线边构成这个深度优先 (b)中的实线边构成这个深度优先 生成树,这些边是递归遍历顶点的路径,叫 生成树,这些边是递归遍历顶点的路径, 树边,虚线边为回边 回边。 做树边,虚线边为回边。

?定义: 定义: 定义 ? w是 L(u)=Min DFN[u],low[w],DFN[k] w是u DFS生成树上的孩子结点 k是 生成树上的孩子结点; DFS生成 在DFS生成树上的孩子结点; k是u在DFS生成 树上由回边联结的祖先节点;(u,w)∈实 树上由回边联结的祖先节点;(u,w)∈实 ;(u,k)∈虚边 显然,L(u)是 虚边, 边;(u,k)∈虚边,显然,L(u)是u通过一条子 孙路径且至多后随一条逆边所可能到达的最 低深度优先数。如果u不是根, 低深度优先数。如果u不是根,那么当且仅当 有一个使得L(w)=DFN(u)的儿子w L(w)=DFN(u)的儿子 u有一个使得L(w)=DFN(u)的儿子w时,u是一 个关结点。 个关结点。

? ? 对于图5 所示的生成树, 对于图5-8(b)所示的生成树,各结点 的最低深度优先数是: 的最低深度优先数是: L(1:10)=(1,1,1,1,6,8,6,6,5,4)。 L(1:10)=(1,1,1,1,6,8,6,6,5,4)。 ? 由此,结点3是关结点, 由此,结点3是关结点,因为它的儿子 结点10 L(10)=4>DFN(3)=3。同理,结点2 10有 结点10有L(10)=4>DFN(3)=3。同理,结点2、 也是关结点。 5也是关结点。

? ? 按后根次序访问深度优先生成树的结点, 按后根次序访问深度优先生成树的结点, 可以很容易地算出L )。于是 于是, 可以很容易地算出L(U)。于是,为了确定 的关结点,必须既完成对G的深度优先检索, 图G的关结点,必须既完成对G的深度优先检索, 产生G的深度优先生成树T 产生G的深度优先生成树T,又要按后根次序 访问树T的结点。 访问树T的结点。

?算法ART——计算DFN和L的算法如下: ? DFN[n],L[n],num, int DFN[n],L[n],num,n ? ART( //u是深度优先检索的开 ART(u,v) //u是深度优先检索的开 始结点。在深度优先生成树中, 始结点。在深度优先生成树中, ? 若有父亲,那末v就是它的父亲。 u若有父亲,那末v就是它的父亲。假设 数组DFN是全程量,并将其初始化为0 num是 DFN是全程量 数组DFN是全程量,并将其初始化为0。num是 全程变量, 全程变量,被初始化为 1。n是 G的结点数

算法如下: 算法如下: int DFN[n],L[n],num=1,n; , , , ; TRY(u,v) ( , ) {DFN[u]=num;L[u]=num;num=num+1; ; ; + ; while (每个邻接于 的结点 w ) 每个邻接于u的结点 if (DFN(w)=0) ( ) ) {TRY(w,u); ( , ); if(L(u)>L(w)L(u)=L(w); );} ( ) ( ) ( ) ( ); else if (w<>v) ) if (L(u)>DFN(w)) ( ) ( ) L(u)= DFN(w); ( ) ( ); }

?算法说明: ? 算法ART实现了对图G的深度优先检索; ART实现了对图 算法ART实现了对图G的深度优先检索; 在检索期间, 在检索期间,对每个新访问的结点赋予深度 优先数;同时对这棵树中每个结点的L 优先数;同时对这棵树中每个结点的L(i) 值也进行计算。 值也进行计算。 ? 如果连通图G 个结点e条边, 如果连通图G有n个结点e条边,且G由邻 接表表示,那末ART的计算时间为O ART的计算时间为 接表表示,那末ART的计算时间为O(n+e)。 识别关结点的总时间不超过O 识别关结点的总时间不超过O(n+e)。

?3.非重连通图的加边策略 3
– 的最大重连通子图, G‘=( V , E )是G的最大重连通子图,指的 =( V’, E‘ 中再没有这样的重连通子图G =( V’‘, E’‘ 是G中再没有这样的重连通子图G’‘=( V , E )存 使得V V 且 E 。 在,使得V’V‘’且E‘E’‘。 – 最大重连通子图称为重连通分图

图5-10

图5-6所示的重连通分图

两个重连通分图至多有一个公共结点,且这个结点就是割点。 两个重连通分图至多有一个公共结点,且这个结点就是割点。 因而可以推出任何一条边不可能同时出现在两个不同的重连通 分图中(因为这需要两个公共结点)。 )。选取两个重连通分图中 分图中(因为这需要两个公共结点)。选取两个重连通分图中 不同的结点连结为边,则生成的新图为重连通的。 不同的结点连结为边,则生成的新图为重连通的。多个重连通 分图的情况依此类推。 分图的情况依此类推。

? 使用这个方法将图5 变成重连通图, 使用这个方法将图5-6变成重连通图, 需要对应于关结点3增加边( 10) 10, 需要对应于关结点3增加边(4,10)和(10, );对应关结点 增加边( 对应关结点2 );对应关 9);对应关结点2增加边(1,5);对应关 结点5增加( ),结果如图 11。 结果如图5 结点5增加(6,7),结果如图5-11。 ?

图5-11 (图5-6改进为重连通图)

5.4 回 溯 法
回溯算法实际是一个类似枚举的搜索尝试方法, 回溯算法实际是一个类似枚举的搜索尝试方法 , 它的主题思想是在搜索尝试中找问题的解, 它的主题思想是在搜索尝试中找问题的解,当不满 足求解条件就”回溯”返回,尝试别的路径。 足求解条件就”回溯”返回,尝试别的路径。回溯 算法是尝试搜索算法中最为基本的一种算法,其采 算法是尝试搜索算法中最为基本的一种算法, 用了一种“走不通就掉头”的思想, 用了一种“走不通就掉头”的思想,作为其控制结 构。

5.4.1 认识回溯法
【例1】八皇后问题模型建立 要在8*8的国际象棋棋盘中放八个皇后, 8*8的国际象棋棋盘中放八个皇后 要在8*8的国际象棋棋盘中放八个皇后, 使任意两个皇后都不能互相吃掉。规则: 使任意两个皇后都不能互相吃掉。规则:皇 后能吃掉同一行、同一列、 后能吃掉同一行、同一列、同一对角线的任 意棋子。如图5 12为一种方案 求所有的解。 为一种方案, 意棋子。如图5-12为一种方案,求所有的解。

? 模型建立 不妨设八个皇后为xi,她们分别在第i行 不妨设八个皇后为xi,她们分别在第i xi i=1, (i=1,2,3,4……,8),这样问题的解空 , ),这样问题的解空 就是一个八个皇后所在列的序号, 间,就是一个八个皇后所在列的序号,为n元 一维向量(x1,x2,x3,x4,x5,x6,x7,x8) 一维向量(x1,x2,x3,x4,x5,x6,x7,x8),搜 索空间是1≤xi≤8 i=1, 1≤xi≤8( 索空间是1≤xi≤8(i=1,2,3,4……,8), , 个状态。约束条件是八个(1,x1) 共88个状态。约束条件是八个(1,x1),(2,x 2) ,(3,x3),(4,x4) ,(5,x5), (6,x6) , (7, (8,x8)不在同一行 不在同一行、 x7), (8,x8)不在同一行、同一列和同一对角 线上。 线上。

虽然问题共有8 个状态, 虽然问题共有88个状态,但算法不会真正地搜 索这么多的状态,因为前面已经说明, 索这么多的状态,因为前面已经说明,回溯法采用 的是“走不通就掉头”的策略, 的是“走不通就掉头”的策略,而形如 (1,1,x3,x4, x5,x6,x7,x8)的状态共有86个,由 x5,x6,x7,x8)的状态共有8 于1,2号皇后 在同一列不满足约束条件,回溯后这8 在同一列不满足约束条件,回溯后这86个状态是不 会搜索的。 会搜索的。

? 算法设计1:加约束条件的枚举算法 加约束条件的枚举算法
– – 最简单的算法就是通过八重循环模拟搜索空 间中的8 个状态,按深度优先思想, 间中的88个状态,按深度优先思想,从第一个皇后 从第一列开始搜索, 从第一列开始搜索,每前进一步检查是否满足约束 条件,不满足时, continue语句回溯 语句回溯, 条件,不满足时,用continue语句回溯,满足满足 约束条件,开始下一层循环,直到找出问题的解。 约束条件,开始下一层循环,直到找出问题的解。

– – 约束条件不在同一列的表达式为x 约束条件不在同一列的表达式为xi xj;而 在同一主对角线上时xi-i=xj-j, 在同一负对角线 在同一主对角线上时x 上时x +j,因此, 上时xi+i=xj+j,因此,不在同一对角线上的约束 条件表示为abs(x xj)≠abs(i j)(abs() abs(i()取绝对 条件表示为abs(xi-xj) abs(i-j)(abs()取绝对 值)。

?算法1:
queen1( ) ( {int a[9]; for (a[1]=1;a[1]<=8;a[1]++) for (a[2]=1;a[2]<=8;a[2]++) {if ( check(a,2)=0 ) continue; for (a[3]=1;a[3]<=8;a[3]++) {if(check(a,3)=0) continue; ( ) for (a[4]=1;a[4]<=8;a[4]++) {if (check(a,4)=0) continue; ) for (a[5]=1;a[5]<=8;a[5]++) {if (check(a,5)=0) continue; ) for (a[6]=1;a[6]<=8;a[6]++) {if (check(a,6)=0) continue; )

for(a[7]=1;a[7]<=8;a[7]++) {if (check(a,7)=0) continue; ) for(a[8]=1;a[8]<=8;a[8]++) {if (check(a,8)=0) ) continue; else for(i=1;i<=8;i++) print(a[i]); } }}}}}}}

check(int a[ ],int n) {int i; for(i=1;i<=nfor(i=1;i<=n-1;i++) (abs(a[i]-a[n])=abs(iif (abs(a[i]-a[n])=abs(i-n)) or (a[i]=a[n]) return(0); ?return(1); return(1); }

算法分析1: 若将算法中循环嵌套间的检查是否满足 约束条件的: 约束条件的: “if (check(a[],i)=0)continue; check(a[],i)=0) if i=2,3,4,5,6,7“ i=2,3,4,5,6,7 语句都去掉,只保留最后一个检查语句: 语句都去掉,只保留最后一个检查语句: check(a[],8)=0)continue;” “if (check(a[],8)=0)continue;

相应地check()函数修改成: 相应地check()函数修改成: check()函数修改成 check*(a[],n) {int i,j; for(i=2;i<=n;i++) for(j=1;j<=ifor(j=1;j<=i-1;j++) if(abs(a[i]-a[j])=abs(iif(abs(a[i]-a[j])=abs(i-j))or(a[i]=a[j]) return(0); return(1); } 则算法退化成完全的盲目搜索,复杂性就是8 则算法退化成完全的盲目搜索,复杂性就是88了

算法设计2:非递归回溯算法 以上的枚举算法可读性很好, 以上的枚举算法可读性很好,但它只能 解决八皇后问题,而不能解决任意的n 解决八皇后问题,而不能解决任意的n皇后问 题。下面的非递归算法可以说是典型的回溯 算法模型。 算法模型。

算法2 算法2: int a[20],n; queen2( queen2( ) { input(n); bckdate( bckdate(n); }

backdate (int n) { int k; a[1]=0; k=1; while( k>0 ) {a[k]=a[k]+1; check(k)=0)) /搜索第 个皇后位置/ 搜索第k (check(k) while ((a[k]<=n) and (check(k)=0)) /搜索第k个皇后位置/ a[k]=a[k]+1; if( a[k]<=n) if( a[k]<=n) if(k=n ) output(n); / 找到一组解/ 找到一组解/ 继续为第k+1个皇后找到位置/ k+1个皇后找到位置 else {k=k+1; 继续为第k+1个皇后找到位置/ a[k]=0;}/注意下一个皇后一定要从头开始搜索 注意下一个皇后一定要从头开始搜索/ a[k]=0;}/注意下一个皇后一定要从头开始搜索/ k=k/回溯 回溯/ else k=k-1; /回溯/ } }

check(int k) { int i; for(i=1;i<=kfor(i=1;i<=k-1;i++) (abs(a[i]-a[k])=abs(iif (abs(a[i]-a[k])=abs(i-k)) or return(0); return(1); } output( ) { int i; for(i=1;i<=n;i++) print(a[i]); }

(a[i]=a[k])

? 算法设计3:递归算法 ?
– 这种方式也可以解决任意的n皇后问题。 这种方式也可以解决任意的n皇后问题。 – 这里我们用第三章3 这里我们用第三章3.2.3 “利用数组记录 利用数组记录 c,b,d分别记录棋 状态信息”的技巧,用三个数组c,b,d 状态信息”的技巧,用三个数组c,b,d分别记录棋 盘上的n个列、 个主对角线和n 盘上的n个列、n个主对角线和n个负对角线的占用 情况。 情况。

以四阶棋盘为例,如图5 13,共有2n以四阶棋盘为例,如图5-13,共有2n2n 1=7个主对角线 对应地也有7个负对角线。 个主对角线, 1=7个主对角线,对应地也有7个负对角线。
?

图5-13 四皇后棋盘示意图

用i,j分别表示皇后所在的行列,同一主对角 分别表示皇后所在的行列, 线上的行列下标的差一样,若用表达式i 编号, 线上的行列下标的差一样,若用表达式i-j编号,则 范围为-n+1 所以我们用表达式i j+n对主 范围为-n+1——n-1,所以我们用表达式i-j+n对主 n 对角线编号,范围就是1——2n-1。同样地,负对角 2n同样地, 对角线编号,范围就是1 2n 线上行列下标的和一样,用表达式i+j编号, 线上行列下标的和一样,用表达式i+j编号,则范围 i+j编号 2n。 为2——2n。 2n

算法3 算法3:
int a[20],b[20],c[40],d[40]; n,t, /t记录解的个数 记录解的个数/ int n,t,i,j,k; /t记录解的个数/ queen3( ) queen3( { int i, input(n); for(i=1;i<=n;i++) { b[i]=0; c[i]=0; c[n+i]=0; d[i]=0; d[n+i]=0; } try( try(1); }

try(i:integer) {int j; for(j=1;j<=n;j++) /第i个皇后有n种可能位置/ /第 个皇后有n种可能位置/ (d[iif (b[j]=0) and (c[i+j]=0) and (d[i-j+n]=0) /摆放皇后 摆放皇后/ {a[i]=j; /摆放皇后/ /占领第 占领第j b[j]=1; /占领第j列/ c[i+j]=1; d[i-j+n]=1; d[i/占领两个对角线/ /占领两个对角线/ 占领两个对角线 if (i<8) /n个皇后没有摆完 递归摆放下一皇后/ 个皇后没有摆完, try(i+1); /n个皇后没有摆完,递归摆放下一皇后/ else output( ); b[j]=0; c[i+j]=0; } } /完成任务,打印结果/ 完成任务,打印结果/ d[i/回溯 回溯/ d[i-j+n]=0; /回溯/

output( ) { t=t+1; print(t,' '); for( k=1;k<=n;k++) print(a[k],' '); print(“ 换行符”); print( 换行符” }

递归算法的回溯是由函数调用结束自动 完成的,也不需要指出回溯点, 完成的,也不需要指出回溯点,但也需要 清理现场” 将当前点占用的位置释放, “清理现场”——将当前点占用的位置释放, 将当前点占用的位置释放 也就是算法try()中的后三个赋值语句 try()中的后三个赋值语句。 也就是算法try()中的后三个赋值语句。

5.4.2 算法简介算法框架

1.回溯法基本思想 2.算法设计过程 3.算法框架

?1.回溯法基本思想 1 ? 回溯法是在包含问题的所有解的解空间树中。 回溯法是在包含问题的所有解的解空间树中。 按照深度优先的策略,从根结点出发搜索解空间树, 按照深度优先的策略,从根结点出发搜索解空间树, 算法搜索至解空间树的任一结点时, 算法搜索至解空间树的任一结点时,总是先判断该 结点是否满足问题的约束条件。 结点是否满足问题的约束条件。如果满足进入该子 树,继续按深度优先的策略进行搜索。否则,不去 继续按深度优先的策略进行搜索。否则, 搜索以该结点为根的子树, 搜索以该结点为根的子树,而是逐层向其祖先结点 回溯。 回溯。 ? 回溯法就是对隐式图的深度优先搜索算法。 回溯法就是对隐式图的深度优先搜索算法。

? 如图5-14是四皇后问题的搜索过程 如图5 14是四皇后问题的搜索过程

图5-14四皇后问题的解空间树

2.算法设计过程

1)确定问题的解空间 问题的解空间应只至少包含问题的一个解。 问题的解空间应只至少包含问题的一个解。 2)确定结点的扩展规则 如每个皇后在一行中的不同位置移动, 如每个皇后在一行中的不同位置移动,而 象棋中的马只能走“ 象棋中的马只能走“日”字等。 字等。

3) 搜索解空间 回溯算法从开始结点出发, 回溯算法从开始结点出发,以深度优先的方式 搜索整个解空间。这个开始结点就成为一个活结点, 搜索整个解空间。这个开始结点就成为一个活结点, 活结点 同时也成为当前的扩展结点。在当前的扩展结点处, 同时也成为当前的扩展结点。在当前的扩展结点处, 搜索向纵深方向移至一个新结点。 搜索向纵深方向移至一个新结点。这个新结点就成 为一个新的活结点,并成为当前扩展结点。 为一个新的活结点,并成为当前扩展结点。如果在 当前的扩展结点处不能再向纵深方向移动, 当前的扩展结点处不能再向纵深方向移动,则当前 扩展结点就成为死结点。此时,应往回移动至最近 扩展结点就成为死结点。此时, 死结点 的一个活结点处, 的一个活结点处,并使这个活结点成为当前的扩展 结点。 结点。回溯法即以这种工作方式递归地在解空间中 搜索, 搜索,直至找到所要求的解或解空间中已没有活结 点时为止。 点时为止。

3.算法框架 1)问题框架 设问题的解是一个n 设问题的解是一个n维向量 (a1,a2,……,an),约束条件是ai(i=1,2, (a1,a2, ,an),约束条件是ai(i=1, ,an) ai 3……n)之间满足某种条件,记为f(ai) n 之间满足某种条件,记为f(ai)

2)非递归回溯框架
a[n], int a[n],i; 初始化数组a[ ]; 初始化数组a[ ]; i=1; (i>0(有路可走 有路可走)) ([未达到目标 未达到目标]) /还未回溯到头 还未回溯到头/ While (i>0(有路可走)) and ([未达到目标]) /还未回溯到头/ {if (i>n) /正在处理第i个元素/ /正在处理第i个元素/ 正在处理第 搜索到一个解,输出; 搜索到一个解,输出; else {a[i]第一个可能的值 第一个可能的值; {a[i]第一个可能的值; (a[i]在不满足约束条件 在在搜索空间内) while (a[i]在不满足约束条件 且 在在搜索空间内) a[i]下一个可能的值 下一个可能的值; a[i]下一个可能的值; (a[i]在搜索空间内 在搜索空间内) if (a[i]在搜索空间内) 标识占用的资源; /扩展下一个结点 扩展下一个结点/ {标识占用的资源; i=i+1;} /扩展下一个结点/ {清理所占的状态空间 清理所占的状态空间; i=i-1;}/回溯 回溯/ else {清理所占的状态空间; i=i-1;}/回溯/ }}

3)递归算法框架 一般情况下用递归函数来实现回溯法比较简单,其中i 一般情况下用递归函数来实现回溯法比较简单,其中i为搜 索深度。 索深度。 int a[n]; try(int i) {if (i>n) 输出结果; i>n) 输出结果; else for( j=下界 j<=上界 j++) 枚举i所有可能的路径/ 上界; for( j=下界 ; j<=上界; j++) /枚举i所有可能的路径/ 满足限界函数和约束条件/ { if ( f(j) ) /满足限界函数和约束条件/ { a[i]=j; …… 其它操作/ /其它操作/ try(i+ 1);} } 回溯前的清理工作(如a[i]置空值等); 回溯前的清理工作( a[i]置空值等) 置空值等 } }

应用1 5.4.3 应用1 ——基本的回溯搜索 基本的回溯搜索
【例2】马的遍历问题 在n*m的棋盘中,马只能走日字。马从位置 的棋盘中,马只能走日字。 (x,y)处出发 把棋盘的每一格都走一次, 处出发, (x,y)处出发,把棋盘的每一格都走一次,且只走一 次。找出所有路径。 找出所有路径。

1、问题分析 马是在棋盘的点上行走的, 马是在棋盘的点上行走的,所以这里的棋 盘是指行有N条边、列有M条边。 盘是指行有N条边、列有M条边。而一个马在 不出边界的情况下有八个方向可以行走, 不出边界的情况下有八个方向可以行走,如当 前坐标为(x,y)则行走后的坐标可以为: 前坐标为(x,y)则行走后的坐标可以为: y(x+1,y+2) ,( x+1, y-2),( x+2, y+1), y-1),(x( x+2, y-1),(x-1, y -2),(x -1, y+2), ( x -2, y -1),( x -2, y+1)

2、算法设计 搜索空间是整个n 搜索空间是整个n*m个棋盘上的点。约束条件是 个棋盘上的点。 不出边界且每个点只经过一次。结点的扩展规则如问 不出边界且每个点只经过一次。 题分析中所述。 题分析中所述。 搜索过程是从任一点(x,y)出发, 搜索过程是从任一点(x,y)出发,按深度优先的 原则,从八个方向中尝试一个可以走的点, 原则,从八个方向中尝试一个可以走的点,直到走过 棋盘上所有n*m个点。用递归算法易实现此过程。 棋盘上所有n 个点。用递归算法易实现此过程。 注意问题要求找出全部可能的解, 注意问题要求找出全部可能的解,就要注意回溯 过程的清理现场工作,也就是置当前位置为未经过。 过程的清理现场工作,也就是置当前位置为未经过。

3、数据结构设计 1)用一个变量dep记录递归深度,也就是走过的 用一个变量dep记录递归深度, dep记录递归深度 点数, dep=n* 找到一组解。 点数,当dep=n*m时,找到一组解。 2)用n*m的二维数组记录马行走的过程,初始 的二维数组记录马行走的过程, 值为0表示未经过。搜索完毕后,起点存储的是“ , 值为0表示未经过。搜索完毕后,起点存储的是“1”, 终点存储的是 “n*m”。 。

4、算法 int n=5 , m=4, dep , i, x , y , count; int fx[8]={1,2,2,1,-1,-2,-2,-1} , fx[8]={1,2,2,1,-1,-2,-2,fy[8]={2,1,-1,-2,-2,fy[8]={2,1,-1,-2,-2,-1,1,2} , a[n][m]; main( ) {count=0; dep=1; print('input x,y'); input(x,y); if (y>n or x>m or x<1 or y<1) { print('x,y error!'); return;} for(i=1;i<=;i++) for(j=1;j<=;j++) a[i][j]=0; a[x][y]=1; find(x,y,2); print(“No answer!”); if (count=0 ) print( No answer! ); print(“count=! count=!”,count); else print( count=! ,count); }

find(int y,int x,int dep) {int i , xx , yy ; /加上方向增量 形成新的坐标/ 加上方向增量, for i=1 to 8 do /加上方向增量,形成新的坐标/ {xx=x+fx[i]; yy=y+fy[i]; /判断新坐标是否出界 是否已走过?/ 判断新坐标是否出界, if (check(xx,yy)=1) /判断新坐标是否出界,是否已走过?/ /走向新的坐标 走向新的坐标/ {a[xx,yy]=dep; /走向新的坐标/ if (dep=n*m) output( ); else find(xx,yy,dep+1); } } a[xx,yy]=0; } /回溯,恢复未走标志/ /回溯,恢复未走标志/ 回溯 /从新坐标出发,递归下一层/ /从新坐标出发,递归下一层/ 从新坐标出发

output( output( ) { count=count+1; print(“换行符”); print( 换行符” 换行符 print('count=',count); for y=1 to n do {print(“换行符 换行符” {print( 换行符”); for x=1 to m do print(a[y,x]:3); } }

【例3】素数环问题 把从1 20这20个数摆成一个环, 把从1到20这20个数摆成一个环,要求相 个数摆成一个环 邻的两个数的和是一个素数。 邻的两个数的和是一个素数。

1、算法设计

尝试搜索从1开始,每个空位有2 尝试搜索从1开始,每个空位有2——20 20 共19种可能,约束条件就是填进去的数满足: 19种可能,约束条件就是填进去的数满足: 种可能 与前面的数不相同; 与前面的数不相同;与前面相邻数据的和是 一个素数。 20个数还要判断和第 个数还要判断和第1 一个素数。第20个数还要判断和第1个数的和 是否素数。 是否素数。

?2、算法 main() main() { int a[20],k; for (k=1;k<=20;k++) a[k]=0; a[1]=1; try(2); }

try(int i) { int k for (k=2;k<=20;k++) (check1(k,i)=1 if (check1(k,i)=1 and check3(k,i)=1 ) { a[i]=k; i=20) if (i=20) output( ); else {try(i+1); a[i]=0;} } }

check1(int j,int i) { int k; (k=1;k<=ifor (k=1;k<=i-1;k++) if (a[k]=j ) return(0); return(1); } check2(int x) { int k,n; n= sqrt(x); for (k=2;k<=n;k++) if (x mod k=0 ) return(1); } return(0);

check3(int j,int i) return(check2(j+a[i 1])); check2(j+a[i{ if (i<20) return(check2(j+a[i-1])); else return(check2(j+a[ireturn(check2(j+a[i-1]) and check2(j+a[1])); } output( ) { int k; for (k=1;k<=20;k++) print(a[k]); print(“换行符” print( 换行符”); 换行符 }

3、算法说明 这个算法中也要注意在回溯前要“ 这个算法中也要注意在回溯前要 “ 清理 现场” 也就是置a[i] a[i]为 现场”,也就是置a[i]为0。

【例4】找n个数中r个数的组合。 个数中r个数的组合。 1、算法设计 先分析数据的特点,以n=5,r=3为例 先分析数据的特点, n=5,r=3为例 在数组a 在数组a中: a[1] a[2] a[3] 5 4 3 5 4 2 5 4 1 5 3 2 5 3 1 5 2 1 4 3 2 4 3 1 4 2 1 3 2 1

分析数据的特点, 搜索时依次对数组(一维向量 元素a[1]、 一维向量)元素 分析数据的特点 , 搜索时依次对数组 一维向量 元素 、 a[2]、a[3]进行尝试, 进行尝试, 、 进行尝试 a[ri] i1——i2 a[1]尝试范围 尝试范围5——3 尝试范围 a[2]尝试范围 尝试范围4——2 尝试范围 a[3]尝试范围 尝试范围3——1 尝试范围 且有这样的规律:“后一个元素至少比前一个数小1”, ri+i2均为 。 均为4。 均为 归纳为一般情况: 归纳为一般情况: a[1]尝试范围 尝试范围n——r, a[2]尝试范围 尝试范围n-1——r-1, ……,a[r]尝 尝试范围 , 尝试范围 , 尝 试范围r——1. 试范围 由此,搜索过程中的约束条件为 由此,搜索过程中的约束条件为ri+a[ri]>=r+1,若 , ri+a[ri]<r就要回溯到元素 就要回溯到元素a[ri-1]搜索,特别地 搜索, 就要回溯到元素 搜索 特别地a[r]=1时, 时 回溯到元素a[r-1]搜索。 搜索。 回溯到元素 搜索

2、算法 main( ); { int n,r,a[20] ; print(“n,r= n,r=”); print( n,r= ); input(n,r); r>n) if (r>n) print(“Input error!”); print( Input n,r error! ); else {a[0]=r; /调用递归过程 调用递归过程/ comb(n,r);} /调用递归过程/ }

comb2(int n,int r,int a[]) {int i,ri; ri=1; a[1]=n; while(a[1]<>rwhile(a[1]<>r-1) ri<>r) 没有搜索到底/ if (ri<>r) /没有搜索到底/ ri+a[ri]>r) {a[ri+1]=a[ri]if (ri+a[ri]>r) {a[ri+1]=a[ri]-1; ri=ri+1;} {ri=ria[ri]=a[ri]/回溯 回溯/ else {ri=ri-1; a[ri]=a[ri]-1;} /回溯/ else {for (j=1;j<=r;j++) print(a[j]); print(“换行符 换行符” /输出组合数 输出组合数/ print( 换行符”); /输出组合数/ a[r]=1) {ri=ri-1;a[ri]=a[ri]/回溯 回溯/ if (a[r]=1) {ri=ri-1;a[ri]=a[ri]-1;} /回溯/ a[ri]=a[ri]/搜索到下一个数 搜索到下一个数/ else a[ri]=a[ri]-1; /搜索到下一个数/ } }

应用2 5.4.4 应用2 ——排列及排列树的回溯搜索 排列及排列树的回溯搜索

【例5】输出自然数1到n所有不重复的排 输出自然数1 列,即n的全排列

1、算法设计 n的全排列是一组n元一维向量:(x1,x2, 的全排列是一组n元一维向量: x1,x2, x3, ),搜索空间是 x3,……,xn),搜索空间是:1≤xi≤n ,xn),搜索空间是: i=1, n,约束条件很简单 i=1,2,3,……n,约束条件很简单,xi互不 n,约束条件很简单,xi互不 相同。 相同。 这里我们采用第三章“ 这里我们采用第三章“3.2.3 利用数 组记录状态信息”的技巧,设置n 组记录状态信息”的技巧,设置n个元素的数 组d,其中的n个元素用来记录数据1——n的 其中的n个元素用来记录数据1 n 使用情况,已使用置1,未使用置0。 使用情况,已使用置1 未使用置0

2、算法 main( main( ) { int j,n, print(‘Input n=’ ‘); print( Input n= ); input(n); for(j=1;j<=r;j++) d[j]=0; try(1); }

try(int k) { int j; for(j=1;j<=n;j++) {if (d[j]=0) {a[k]=j; d[j]=1;} else continue; if (k<n) try(k+1); else output(k);} {p=p+1; output(k);} } d[a[k]]=0; }

output( ) { int j; print(p,”: ) print(p, :”) for(j=1;j<=n;j++) print(a[j]); print(“换行符”); print( 换行符” 换行符 } 变量p 3、算法说明:变量p记录排列的组数,k为当前 变量 记录排列的组数, 处理的第k 处理的第k个元素

4、算法分析 全排列问题的复杂度为O nn) 全排列问题的复杂度为O(nn),不是一 个好的算法。 个好的算法 。 因此不可能用它的结果去搜索 排列树。 排列树。

【例6】全排列算法另一解法——搜索排列树 全排列算法另一解法 搜索排列树 的算法框架 1、算法设计 根据全排列的概念, 定义数组初始值为 根据全排列的概念 , (1,2,3,4,……,n),这是全排列中的 , 一种, 然后通过数据间的交换, 一种 , 然后通过数据间的交换 , 则可产生所 有的不同排列。 有的不同排列。

2、算法 int a[100],n,s=0; main( ) { int i,; input(n); for(i=1;i<=n;i++) a[i]=i; try(1); print(“换行符” print( 换行符”,“s=”,s); 换行符 s= ,s); }

try(int t) { int j; if (t>n) );} {output( );} else for(j=t;j<=n;j++) {swap(t,j); try(t+1); 回溯时,恢复原来的排列/ swap(t,j); /回溯时,恢复原来的排列/ } }

output( ) { int j; printf("\ printf("\n"); for( j=1;j<=n;j++) s=s+1; } swap(int t1,int t2) { int t; t=a[t1]; a[t1]= a[t2]; a[t2]=t; }

printf(" mod d",a[j]);

3、算法说明 函数中, 1)有的读者可能会想try( )函数中,不 有的读者可能会想try( )函数中 应该出现自身之间的交换,for循环是否应该 应该出现自身之间的交换,for循环是否应该 改为for(j=t+1;j<=n;j++) 回答是否定的。 for(j=t+1;j<=n;j++)? 改为for(j=t+1;j<=n;j++)?回答是否定的。 n=3时 算法的输出是:123,132,213, 当n=3时,算法的输出是:123,132,213,2 31,321,312。123的输出说明第一次到达叶 31,321,312。123的输出说明第一次到达叶 结点是不经过数据交换的, 132的排列也是 结点是不经过数据交换的,而132的排列也是 不进行交换的结果。 1不进行交换的结果。

for循环体中的第二个 循环体中的第二个swap( 调用, 2)for循环体中的第二个swap( )调用, 是用来恢复原顺序的。 是用来恢复原顺序的 。 为什么要有如此操作 还是通过实例进行说明, 排列“ 213”是 呢 ? 还是通过实例进行说明 , 排列 “ 213 是 123”进行 进行1 由 “ 123 进行 1 , 2 交换等到的所以在回溯时 要将“132” 恢复为“123”。 要将“132 恢复为“123 。 4、算法分析 全排列算法的复杂度为O n!) 全排列算法的复杂度为O(n!), 其结果 可以为搜索排列树所用。 可以为搜索排列树所用。

【例7】按排列树回溯搜索解决八皇后问题 1、算法设计 利用例6 枚举 所有1 的排列, 枚举” 利用例6“枚举”所有1-n的排列,从中选 出满足约束条件的解来。 出满足约束条件的解来 。 这时的约束条件只 有不在同一对角线, 有不在同一对角线 , 而不需要不同列的约束 和例1 的算法3 一样,我们用数组c 了 。 和例 1 的算法 3 一样 , 我们用数组 c , d 记 录每个对角线的占用情况。 录每个对角线的占用情况。

2、算法
int a[100],n,s=0,c[20],d[20]; main( ) { int i; input(n); for(i=1;i<=n;i++) a[i]=i; for (i=1;i<=n;i++) { c[i]=0; c[n+i]=0; d[i]=0; d[n+i]=0;} try(1); print("s=",s); }

try(int t) { int j; if (t>n) {output( );} else for(j=t;j<=n;j++) { swap(t,j); if (c[t+a[t]]=0 and { c[t+a[t]]=1; try(t+1); c[t+a[t]]=0; swap(t,j); } }

d[t-a[t]+n]=0) d[td[td[t-a[t]+n]=1; d[td[t-a[t]+n]=0;}

output( ) { int j; print("换行符 换行符"); print("换行符"); for( j=1;j<=n;j++) s=s+1; } swap(int t1,int t2) { int t; t=a[t1]; a[t1]= a[t2]; a[t2]=t; }

print(a[j]);

应用3 5.4.5 应用3 ——最优化问题的回溯搜索 最优化问题的回溯搜索
【例8】一个有趣的高精度数据 构造一个尽可能大的数,使其从高到低 构造一个尽可能大的数, 前一位能被1整除, 位能被2整除, 前一位能被1整除,前2位能被2整除,……, , 位能被n整除。 前n位能被n整除。

1、数学模型 记高精度数据为a1 a2……an,题目很明 an, 记高精度数据为a1 a2 an 确有两个要求: 确有两个要求: 1)a1整除1且 1)a1整除1 整除 (a1*10+a2)整除 整除2 (a1*10+a2)整除2且…… (a1*10n-1+a210n-2+……+an) 整除n; (a1*10n-1+a210n-2+ +an) 整除n 求最大的这样的数。 2)求最大的这样的数。

2、算法设计 此数只能用从高位到低位逐位尝试失败 回溯的算法策略求解, 回溯的算法策略求解,生成的高精度数据用 数组的从高位到低位存储, 数组的从高位到低位存储,1号元素开始存储 最高位。 最高位。此数的大小无法估计不妨为数组开 100个空间 个空间。 辟100个空间。 算法中数组A 算法中数组A为当前求解的高精度数据的 暂存处,数组B为当前最大的满足条件的数。 暂存处,数组B为当前最大的满足条件的数。

算法的首位A[1]从 开始枚举。 算法的首位A[1]从1开始枚举。以后各位 A[1] 开始枚举。 从0开始枚举。所以求解出的满足条件的数据 之间只需要比较位数就能确定大小。 之间只需要比较位数就能确定大小。n 为当 前满足条件的最大数据的位数,当i>=n就认 前满足条件的最大数据的位数, i>=n就认 为找到了更大的解,i>n不必解释位数多数据 为找到了更大的解,i>n不必解释位数多数据 一定大;i=n时 由于尝试是由小到大进行的, 一定大;i=n时,由于尝试是由小到大进行的, 位数相等时后来满足条件的?菀欢ū 位数相等时后来满足条件的?菀欢ū惹懊娴 拇蟆

3、算法
main( ) i,j,k,n,r; { int A[101],B[101]; int i,j,k,n,r; A[1]=1; /置初值 首位为1 其余为0/ 置初值: for(i=2;i<=100;i++) /置初值:首位为1 其余为0/ A[i]=0; n=1; i=1; while(A[1]<=9) /发现有更大的满足条件的高精度数据 发现有更大的满足条件的高精度数据/ {if (i>=n) /发现有更大的满足条件的高精度数据/ /转存到数组 转存到数组B {n=i; /转存到数组B中/ for (k=1;k<=n;k++) B[k]=A[k]; }

i=i+1;r=0; /检查第 位是否满足条件/ 检查第i for(j=1;j<=i;j++) /检查第i位是否满足条件/ {r=r*10+A[j]; r=r mod i;} /若不满足条件 若不满足条件/ if(r<>0) /若不满足条件/ {A[i]=A[i]+i/第 位可能的解/ {A[i]=A[i]+i-r ; /第i位可能的解/ /搜索完第 位的解, 搜索完第i while (A[i]>9 and i>1) /搜索完第i位的解,回 溯到前一位/ 溯到前一位/ i=i{A[i]=0; i=i-1; A[i]=A[i]+i;} } } }

4、算法说明 1)从A[1]=1开始,每增加一位A[i](初 A[1]=1开始,每增加一位A[i]( 开始 A[i] 值为0 先计算r=(A[1]*10i 1+A[2]*10ir=(A[1]*10i值为0)先计算r=(A[1]*10i-1+A[2]*10i-2+ ……+A[i]),再测试r=r mod i是否为0。 +A[i]), i是否为 是否为0 +A[i]) 再测试r=r r=0表示增加第 位后,满足条件, 表示增加第i 2)r=0表示增加第i位后,满足条件,与 原有满足条件的数(存在数组B 比较, 原有满足条件的数(存在数组B中)比较,若 前者大,则更新后者(数组B),继续增加下 前者大,则更新后者(数组B),继续增加下 一位。 一位。

3)r≠0表示增加i位后不满足整除条件, r≠0表示增加i位后不满足整除条件, 表示增加 接下来算法中并不是继续尝试A[i]= A[i]+1, 接下来算法中并不是继续尝试A[i]= A[i]+1, 而是继续尝试A[i]= A[i]+i- 因为若A[i]= 而是继续尝试A[i]= A[i]+i-r,因为若A[i]= A[i]+i-r<=9时 A[1]*10i-1+A[2]*10iA[i]+i-r<=9时,(A[1]*10i-1+A[2]*10i-2+ ……+A[i]杛+i) mod i肯定为0,这样可减 +A[i]杛 i肯定为 肯定为0 +A[i] +i) 少尝试次数。 17除 15-2+5肯定能 少尝试次数。如:17除5余2,15-2+5肯定能 整除。 被5整除。

+i>9时 4)同理,当A[i] -r +i>9时,要进位也 同理, 不能算满足条件。这时, 不能算满足条件。这时,只能将此位恢复初 且回退到前一位(i=i- 尝试A[i]= 值0且回退到前一位(i=i-1)尝试A[i]= A[i] +i……。这正是最后一个while循环所做的工 while循环所做的工 +i 。这正是最后一个while 作。 当回溯到i=1 i=1时 A[1]加 5)当回溯到i=1时,A[1]加1开始尝试首 位为2的情况,最后直到将A[1]=9 A[1]=9的情况尝试 位为2的情况,最后直到将A[1]=9的情况尝试 完毕,算法结束。 完毕,算法结束。

【例9】流水作业车间调度 个作业要在由2 台机器M n 个作业要在由 2 台机器 M1 和 M2 组成的流水线上 完成加工。每个作业加工的顺序都是先在M 上加工, 完成加工。每个作业加工的顺序都是先在M1上加工, 然后在M 上加工。 加工作业i 然后在 M2 上加工 。 M1 和 M2 加工作业 i 所需的时间分别 ai和 bi。 流水作业调度问题要求确定这n 为 ai 和 bi 。 流水作业调度问题要求确定这 n 个作业的 最优加工顺序,使得从第一个作业在机器M 最优加工顺序,使得从第一个作业在机器M1上开始加 到最后一个作业在机器M 工,到最后一个作业在机器M2上加工完成所需的时间 最少。作业在机器M 的加工顺序相同。 最少。作业在机器M1、M2的加工顺序相同。

1、算法设计 问题的解空间是一棵排列树, 1)问题的解空间是一棵排列树,简单的解 决方法就是在搜索排列树的同时, 决方法就是在搜索排列树的同时 , 不断更新最 优解,最后找到问题的解。算法框架和例6 优解,最后找到问题的解。算法框架和例6完全 相同,用数组x 初值为1 相同,用数组x(初值为1,2,3,……,n)模 , 拟不同的排列, 拟不同的排列 , 在不同排列下计算各种排列下 的加工耗时情况。 的加工耗时情况。

2)机器M1进行顺序加工,其加工f1时间是固定的,f1[ 机器M1进行顺序加工,其加工f1时间是固定的, M1进行顺序加工 f1时间是固定的 f1[i-1]+a[x[i]]。机器M2则有空闲( M2则有空闲 19( ))或 i]= f1[i-1]+a[x[i]]。机器M2则有空闲(图5-19(1))或 积压( 19( ))的情况 总加工时间f2 当机器M2 的情况, f2, M2空 积压(图5-19(2))的情况,总加工时间f2,当机器M2空 闲时, b[x[i]];当机器M2有积压情况出现时, M2有积压情况出现时 闲时,f2[i]=f1+ b[x[i]];当机器M2有积压情况出现时,f f2[ib[x[i]]。总加工时间就是f2[n] f2[n]。 2[i]= f2[i-1]+ b[x[i]]。总加工时间就是f2[n]。

图5-19(1)有空闲 19(

图5-19(2)有积压 19(

一个最优调度应使机器M 没有空闲时间, 3)一个最优调度应使机器M1没有空闲时间,且 机器M 的空闲时间最少。在一般情况下, 机器 M2 的空闲时间最少 。 在一般情况下 , 当作业按 在机器M 上由小到大排列后,机器M 在机器 M1 上由小到大排列后 , 机器 M2 的空闲时间较 少 , 当然最少情况一定还与 M2 上的加工时间有关, 当然最少情况一定还与M 上的加工时间有关, 所以还需要对解空间进行搜索。 所以还需要对解空间进行搜索 。 排序后可以尽快地 找到接近最优的解, 找到接近最优的解 , 再加入下一步限界操作就能加 速搜索速度。 速搜索速度。

经过以上排序后, 4)经过以上排序后,在自然数列的排列 就是一个接近最优的解。 因此, 下 , 就是一个接近最优的解 。 因此 , 在以后 的搜索过程中, 的搜索过程中 , 一当某一排列的前面几步的 加工时间已经大于当前的最小值, 加工时间已经大于当前的最小值 , 就无需进 行进一步的搜索计算, 行进一步的搜索计算 , 从而可以提高算法效 率。

2、数据结构设计

1)用二维数组job[100][2]存储作业在M1、M2 用二维数组job[100][2]存储作业在M1、 job[100][2]存储作业在M1 上的加工时间。 上的加工时间。 2)由于f1在计算中,只需要当前值,所以用变 由于f1在计算中,只需要当前值, f1在计算中 量存储即可; f2在计算中, 量存储即可;而f2在计算中,还依赖前一个作业的 在计算中 数据,所以有必要用数组存储。 数据,所以有必要用数组存储。 3)考虑到回溯过程的需要,用变量f存储当前 考虑到回溯过程的需要,用变量f 加工所需要的全部时间。 加工所需要的全部时间。

3、算法 job[100][2],x[100],n, int job[100][2],x[100],n,f1=0,f=0,f2[100]=0; main( ) { int j; input(n); for(i=1;i<=2;i++) for(j=1;j<=n;j++) input(job[j][i]); try( ); }

try(int i) { int j; if (i=n+1) {for(j=1;j<=n;j++) bestx[j]=x[j]; bestf=f; } else

for(j=1;j<=n;j++) { f1= f1+ job[x[j]][1]; (f2[iif (f2[i-1]>f1) else f=f+f2[i]; if (f<bestf) { swap(x[i],x[j]); swap(x[i],x[j]);} f1f1= f1-job[x[j]][1]; f=ff=f-f2[i]; } } try(i+1); f2[if2[i]= f2[i-1]+job[x[j]][2]; f2[i]= f1+job[x[j]][2];

解空间为排列树的最优化类问题, 解空间为排列树的最优化类问题,都可 以依此算法解决。 以依此算法解决。而对于解空间为子集树的 最优化类问题,类似本节例题1 最优化类问题,类似本节例题1、2、3枚举元 素的选取或不选取两种情况进行搜索就能找 出最优解,同时也可以加入相应的限界策略。 出最优解,同时也可以加入相应的限界策略。


更多相关文档:

算法设计与分析第五章重点

算法设计与分析第五章重点_工学_高等教育_教育专区。回溯法:具有限界凼数的深度...1、针对所给问题,定义问题的解空间;2、确定易于搜索的解空间结构;3、以深度优...

算法设计与分析答案参考

新闻网页贴吧知道音乐图片视频地图百科文库 搜 试试 7 帮助 全部 DOC PPT TXT...算法设计与分析答案参考_计算机硬件及网络_IT/计算机_专业资料。1、用 Floyd 算法...

5.《算法设计与分析》试题库

算法分析与设计》试题库() 、 选择题 1....动态规划算法 2.Hanoi 塔问题如下图所示。现要求将...分) 3、试用分治法对一个有序表实现二分搜索算法...

算法设计与分析复习题目及答案

算法设计与分析复习题目及答案_工学_高等教育_教育专区。山东科技大学 一。选择题 1、二分搜索算法是利用( A、分治策略 B、动态规划法 A )实现的算法。 C、...

算法设计与分析 实验指导 (1)

算法设计与分析 实验指导 (1)_物理_自然科学_专业资料。中南大学 算法设计与分析...Sample Input 36 62 49 343 0 0 Sample Output 62 49 实验三:搜索算法实验...

算法设计与分析作业1

新闻 网页 贴吧 知道 音乐 图片 视频 地图 百科文库 搜试试 3 帮助 全部 ...算法设计与分析作业1_理学_高等教育_教育专区。《算法设计与分析》作业 1 1. ...

算法设计与分析复习题目及答案

算法设计与分析复习题目及答案_工学_高等教育_教育...分治法 1、二分搜索算法是利用( 分治策略)实现的...图的 m 着色问题可用 回溯 mn 法求解,其解空间树...

算法设计与分析习题

登录注册新闻网页贴吧知道音乐图片视频地图百科文库 搜...《算法设计与分析》习题 第一章算法引论 1、 算法...答:相同点:都属于搜索算法; 都需要在问题的解空间...

算法设计与分析试卷及答案

新闻 网页 贴吧 知道 音乐 图片 视频 地图 百科文库 搜试试 7 帮助 全部 ...五、算法设计(共计 15 分) 1. 7 分 为了尽可能地逼近目标,选取的贪心策略...

算法设计与分析考试重点归纳

算法设计与分析考试重点归纳_计算机软件及应用_IT/计算机_专业资料。算法设计考试...图 G = <V, E, W>, 顶点集合 V 划分成 k 个不相交的子集 vi, 1 ?...
更多相关标签:
算法设计与分析 | 计算机算法设计与分析 | 算法设计与分析基础 | 算法设计与分析考试题 | 算法设计与分析第二版 | 算法设计技巧与分析 | 算法设计与分析第三版 | 算法设计与分析 pdf |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com