算法设计与分析

算法设计与分析王歧目录动态规划贪心算法状态空间搜索法分治法随机算法模拟算法递归算法数论算法回溯算法

对于有些最优解问题，没有任何的理论也无法采用精确的数学公式来帮助我们找到最优解，我们只能用穷举算法。在这里我们介绍一种系统化的穷举搜索技术，称为回溯技术。

所谓回溯技术就是向人走迷宫一样，先选择一个前进方向尝试，一步步试探，在遇到死胡同不能再往前的时候就会退

到上一个分支点，另选一个方向尝试，

而在前进和回撤的路上都设置一些标记，以便能够正确返回，直到达到目标或者

所有的可行方案都已经尝试完为止。回溯算法

在通常的情况下，我们使用递归方式来实现回溯技术，也就是在每一个分叉点进行递归尝试。在回溯是通常采用栈来记录回溯过程，使用栈可使穷举过程能回溯到所要的位置，并继续在指定层次上往下穷举所有可能的解。回溯算法用伪代码描述如下：Proc

search(当前状态)；BeginIf当前状态等于目标状态then

exit；for对所有可能的新状态search(新状态);End;回溯算法的经典问题八皇后问题。骑士周游问题地图着色问题八皇后问题问题描述在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相“冲突”（在每一横列竖列斜列只有一个皇后）。算法流程１、数据初始化。２、从n列开始摆放第n个皇后，先测试当前位置(n,m)是否等于０如果是，摆放第n个皇后，并宣布占领，接着进行递归；否则，测试下一个位置(n,m+1)，但是如果当n<=8,m=8时，却发现此

时已经无法摆放时，便要进行回溯。

３、当n>8时，便一一打印出结果。问题分析

这道题可以用递归来做，分别一一测试每一种摆法，直到得出正确的答案。主要解决以下几个问题：1、冲突。包括行、列、两条对角线2、数据结构1、冲突，包括行、列、两条对角线：

（1）列：规定每一列放一个皇后，不会造成列上的冲突；行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；对角线：对角线有两个方向。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占

领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。2、数据结构

（1）解数组A。A[I]表示第I个皇后放置的列；

I=1,…,8；行冲突标记数组B。B[I]=0表示第I行空闲；

B[I]=1表示第I行被占领；I=1,…,8；对角线冲突标记数组C、D。C[I-J]=0表示第（I-J）条对角线空闲；C[I-J]=1表示第（I-J）条对角线被占领；范围：-7..7D[I+J]=0表示第（I+J）条对角线空闲；

D[I+J]=1表示第（I+J）条对角线被占领；范围：

2..16优点：逐一测试标准答案，不会有漏网之鱼。八皇后问题程序#include

<stdio.h>#include

<stdlib.h>#include

<time.h>int

main

(

int

argc,

char

*

argv[]){

int

q[1024];

int

i,

j,

k,

c,

n;

time_t

tm;switch

(

argc

){

case

1:

n

=

8;

break;case

2:

n

=

atoi

(

argv[1]

);if

(

n

<=

0

||

n

>=

1024

)

return

0;

break;default:

return

0;}N皇后问题

发信人:PowerStation

(Warez

Killer),信区:

sources标题:最快的N皇后问题C

Program发信站:饮水思源站(Thu

May

15

01:25:39

1997),转信/*最快的N皇后问题C

Program这个程需仍然采用传统的递归算法，但使用了C的位操作以极大地提高了运行速度。law的程序算

13皇后用了43秒，而我的仅用7秒，快六倍,半个数量级,:))).(比较时删去了火火的输出部分以示公平).同时我的程序可非常容易的转换成

asm,还能更快。本程序去掉了输出各解的功能，一方面是为了尽可能的快，另一方面似乎也没有必要。(真有人看吗?)*/

#include<stdio.h>

#include

<stdlib.h>

#include

<time.h>素数环

问题：把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。

分析：非常明显，这是一道回溯的题目。从1开始，每个空位有20（19）种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。算法流程

1、数据初始化；

2、递归填数：判断第J种可能是否合法；A、如果合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，递归填下一个；B、如果不合法：选择下一种可能；

任何一个正整数都可以用2的幂次方表示.例如:137=2^7+2^3+2^0同时约定次方用括号来表示,即a^b可表示为a(b)由此可知,137可表示为:2(7)+2(3)+2(0)进一步:7=2^2+2+2^0

(2^1用2表示)

3=2+2^0所以最后137可表示为:

2(2(2)+2+2(0))+2(2+2(0))+2(0)又如:1315=2^10+2^8+2^5+2+1所以1315最后可表示为:

2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2()输入:正整数(n<=20000)搜索算法

搜索算法，是一种在状态空间中寻找特定的目标状态及到达目标状态的途径的系统方法。搜索是计算机求解问题的最基本方法，适用面很广，没有向动态规划那样对状态有最优化原理和无后效性的约束。

当然对具体问题，特别是运用了某种智能化的优化手段，也许会带来某些具体的约束。

当所给定的问题用状态网络表示时，则求解过程可归结为对状态空间的遍历。搜索空间是搜索达到的状态空间，它是状态空间的一部分。当问题有解时使用不同的求解策略，找到解的搜索空间范围是有区别的。一般来说，对大空间问题，搜索策略是要解决组合爆炸问题。搜索算法的一般模式

一般说来，搜索算法要求记录完整的搜索空间，即保留所有生成的节点。这样做有两个目的：

状态判重和输出解路径。

为了方便描述选择待扩展的节点和生成新节点的过程，我们同时将节点组织成两张表，称为

CLOSED表和OPEN表。CLOSED表中存放已经扩展过的节点，OPEN表中存放已经生成但尚未扩展的节点。搜索开始之前CLOSED表是空的，而OPEN表中只有初始节点。

搜索过程可描述为：从OPEN表中选择一个结点u，将结点u从OPEN表中删除，加入到CLOSED表，然后扩展结点u得到新结点v1，…，vk，(这些顶点的状态应该于已经生成的节点的状态是不同的)，将这些结点加入到OPEN表中。Procedure

graph_search;BeginCLOSED表初始化为空；OPEN表初始化为空；while

OPEN表非空do取OPEN表中的一个结点u;从OPEN表中删除u;u进入CLOSED表；对扩展结点u得到的每个新结点vi

doif

vi的状态与CLOSED表和OPEN表中的节点的状态都不行同thenvi进入OPEN表；End;End;两种基本的搜索算法

深度优先搜索：优先扩展尚未扩展且具有最大深度的结点； 广度优先搜索：就是在扩展完第k层的结点之后，才扩展第k+1层的结点。如果OPEN表示后进先出的，深度如果OPEN表示先进先出的，广度深度优先与回溯

从本质上说，回溯和深度优先搜索几乎就是一回事了。但两者还是有差别的。

首先，回溯方式不保留完整的树结构，只记住当前工作的一条路经，回溯就是对这条路径进

行修正；而深度优先搜索则记下完整的搜索树，搜索树同时起到记录解路径和状态判重的作用。因此，回溯方式明显的节省空间。（迷宫问题、八皇后问题）

其次，回溯方式要就能够按照一种事先确定好的某种固定排序依次调用规则。即对每一层I事先都确定好一个规则的序列Ri1，Ri2，…，Rin，假设第i层当前规则是Rik

，如果到第i+1层发现所有的规则都不合适，就回溯到第i层，若k<n，则继续尝试规则Rik+1

，否则在回溯到第i-1层，这种对规则有序性要求的原因是，回溯方式不

保留完整的树结构。而深度优先搜索则没有对

规则有序性的要求。

在实际应用中，把两者的优点结合起来，形成一种新的算法模式，以后在提到深度优先搜索就是指这种新算法。搜索算法的优化手段

剪枝：如果能够通过一些信息，说明继续扩展该结点不可能到达目标结点，则可以将搜索树在该结点以下的分支全部剪去，从而达到减少搜索范围、提高搜索速度的目的。对扩展结点u得到的每个新结点vi

doif

vi不满足剪枝条件thenif

vi的状态与CLOSED表和OPEN表中的节点的状态都不行同thenvi进入OPEN表；广度优先搜索算法BFS广度优先搜索(Breadth

First

Search)

对图G=(V，E)进行BFS搜索的步骤可直观的叙述如下。从任意选定的r开始，依次检查所有与r点关联的边(r,a1),(r,a2),…(r,an)，当上面r条边检查完毕后，在依次

检查与a1

,a2

,…,ak相关联的边，依此类推

直到所有的边被检查，所有的顶点均被访问为止。广度优先算法的伪代码表示：取OPEN队头结点u；u出队OPEN;U进入CLOSED表；对扩展节点u得到的每个新节点vi

doBegin计算vi的代价；if

vi的状态=目标状态thenbegin输出节点vi的解路径；exit;end;if

vi的状态与CLOSED表和OPEN队列中的节点的状态都不相同

thenvi如队OPEN；End;八数码问题

在3X3的九宫格棋盘上摆有八个棋子，每个棋子都刻有1-8种的某一个数码，棋盘中留有一个空格，允许周围的某一个棋子向空格移动，这样通过移动棋子可以不断的改变棋盘的格局。给定一种初始棋盘格局和一个目标棋盘格局，求一个移动棋子的序列，实现从初始格局到目标格局的转变，并使移动棋子的步数最少。八数码问题分析实现OPEN队列实现CLOSED表关键在于解决好判重问题骨牌矩阵

多米诺骨牌是一个小正方形方块，每个骨牌都标有一个数字（0~6），现在有28组骨牌，每组两个，各组编号为1~28，每组编号对应的两个骨牌数值如下：•00010203040506•11121314151622•23242526333435•36444546555666

现将这28组骨牌排成一个7X8矩阵，此时只能看到每个骨牌上的数字（0~6），而不能知道每组的组号（如左下图所示）。请编程序将每组骨牌分辨出来（如右下图所示）。•7X8骨牌矩阵骨牌组编号矩阵•6626524128

28

14

7

17

17

11

11•1320103410

10

14

7

2

2

21

23•132466548

4

16

25

25

13

21

23•104321128

4

16

15

15

13

9

9•5136045512

12

22

22

5

5

26

26•5540260327

24

24

3

3

18

1

19•6053420327

6

6

20

20

18

1

19骨牌矩阵问题算法分析

此题的算法比较简单，只需使用标准的回溯算法，而且由于本