程序算法设计论文

浅谈递归与几种搜索在程

序设计中的应用

暨程序设计专题训练结业论文

南京航空航天大学10级计算机软件培优班

041040124马晓林 指导教师：刘邵翰

摘要

本文主要按照我的认知顺序，并结合实际应用案例分别就深度优先遍历、广度优先遍历、记忆化搜索的概念、优缺点、实现方法等简单的谈了自己的理解，并将几种算法进行了比较。

关键词

递归 图论 搜索 效率 算法优化 深度优先遍历 广度优先遍历 重复字问题 记忆化搜索 动态规划

浅谈递归与搜索在程序设计中的应用

暨程序设计专题训练结业论文

本学期的程序设计算法专题训练主要集中在递归递推算法的使用，并以此为基础对深度搜索、广度搜索、动态规划以及记忆化搜索进行了一定的研究。下面我将按照我对这一系列算法的认知先后顺序谈谈我对它们的理解。

在这门课最开始，我们首先更加深入的理解了递归算法运行背后的原理和关于图论的基本知识。我认为这两部分知识是之后学习的基础，意义十分重大。首先，如深度、广度搜索等算法是完全基于递归而完成的，所以只有掌握好递归才能真正学好这门课。而对于谈到图论，由于这是一门深奥广博的学科，而我们仅仅学到了皮毛的皮毛，我在这里也就不再累述，我仅仅在这里重申，在今后解决问题的过程中，我们大多需要将问题转化成图，然后再通过各种算法加以解决。

下面我将通过实际应用案例（你在哪、N皇后问题、迷宫问题、最长子序列问题）分别就深度优先遍历、广度优先遍历、记忆化搜索简单的谈一下自己的理解。其中，由于老师在上课时已经比较详细、清晰的讲解过深度优先遍历与广度优先遍历，所以在此仅简单介绍。而对于上课未曾系统提及的记忆化搜索，我将进行较为详细的阐述。

1深度优先遍历 ○

深度优先遍历顾名思义就是优先向深处延伸的一种搜索算法，其核心是将每一个分支情况一直走到尽头而后在考虑其他分支，最终比较求得满足问题要求的解。以迷宫问题为例，本题在思路上就是自出发点开始，向不同方向的满足条件的下一个点前进，直到到达目的地为止。深搜dfs函数如下： void dfs(int i,int j,int k) {

int v;

if (i==m && j==n)

printf(“可以到达指定地点\n”); {

else for (v=0; v

if ( [i+dx[v],j+dy[v] 该点点可以到达,并且在迷宫内 } }

注：dx和dy为代表四个行进方向的方向向量横纵坐标

2广度优先遍历 ○

dfs(i+dx[v],j+dy[v],k+1);

顾名思义，广度优先遍历就是优先向同级的广度方向延伸的一种搜索算法，其核心是每次优先走同一级的分支，在同一级分支走完后在向下一级深入，最终综合的问题要求，求得结果。因为在此算法中大多使用“队列”这一概念和方法，所以该算法在处理和寻找最优解时有着DFS所无法比拟优势。仍然以迷宫问题为例，程序大体如下： head = tail = 0; while(head

综上，我们可以发现，深度优先遍历和广度优先遍历两种算法有着十分明显的优点——易于理解和实现，以上面提到的几个问题为例，只要我们能够理解题目要求并能够清晰地将递归关系以程序语言实现，那么问题基本上可以迎刃而解。但是这两种算法的缺点也是显而易见的，那就是运算量大，耗时极长。以《N皇后问题》为例，当皇后数目在8-10个时，计算机尚可较为快速的完成求解，当其规模达到13个皇后时，计算时间已经达到了近10秒，而当规模进一步扩大时，计算时间更是几何倍数的增长，于是这就对我们的算法提出了进一步

(x,y) = q[head]; for (v=0; v

getnew(xx,yy); if (xx,yy 不重复) } head++;

{ }

if (xx,yy) == 终点 {输出; 结束;} tail++;(xx,yy)入队;

//判断是否存在重复情况

优化要求。在我们进一步研究时容易发现，在这两种算法的执行过程中，由于函数递归的使用，出现了极多的重复子问题，即同一状态对应的运算结果在不同的求解过程中需要重复计算。这方面最典型的例子就是斐波那契额数列的计算过程，在计算a4时，我们需要计算一次a3=a2+a1=1+1=2，在计算a5时我们因为需要a4和a3的值，所以我们又需要再计算两次a3的值，同理当我们计算a6时，我们需要共计3次计算a3的值，计算a7时，调用结果的次数就达到了5次，在计算第10项、第30和第40项项时，调用a3的次数就分别达到了21次、317811次和39088169次。可见随着下标的不断增大，对a3结果的调用次数将会飞速的增长。于是我们自然想到了将那些需要重复使用的中间计算结果储存下来，以便让计算机在需要调用这些结果时只需直接提取结果而不需要再次计算。这种想法就是记忆化搜索思路的核心。

3记忆化搜索 ○

记忆化搜索是在以上基础算法的基础上大大的进行优化的一种算法，他通过一定的方法对已经运行过的结果进行“记忆”，避免了大量的重复计算，从而数以亿计倍的极大程度的减小了程序的计算规模，缩短了运行时间，应用价值十分重大。

如上文所述，该算法核心是将需要多次使用的中间计算结果储存在一个专门的数组中， 以《N皇后问题》为例，在解题过程中，当计算13皇后问题时，在线评判系统会判定先举一个简单的例子来说明记忆化方法对提高递归函数运算效率的巨大作用。仍然是计算斐波那契额数列，其求解函数fun如下：

int f[1000]={0}; int fun(int n) {

int x; if (f[x]!=0)

return f[x]; if(n==1||n==2)

}

显然，以上函数对于数列中具有相同下标的项仅仅进行了一次求解，这就极大的提高了运算效率。实践证明，在求解a240时该方法的运算时间仅仅是普通递归的百亿分之一数量级。

刚刚的斐波那契额数列求解仅仅是使用了记忆化方法，并没有体现其再搜索中的应用，所以并不能算作是记忆化搜索。那么下面请看一个较为复杂的真正的记忆化搜索案例：求解最长公共子序列问题。其主要递归函数calc如下：

int a[1000][1000]

else

x=fun(n-1)+fun(n-2); f[n]=x; return x; x=1;

//用于存放已经求出的结果

在每次计算时先在该数组中对该结果进行搜索，若能够找到则直接调用储存的结果。

其计算超时。但是当我们使用动态规划对改程序进行一定改进时，问题就迎刃而解了。

优化要求。在我们进一步研究时容易发现，在这两种算法的执行过程中，由于函数递归的使用，出现了极多的重复子问题，即同一状态对应的运算结果在不同的求解过程中需要重复计算。这方面最典型的例子就是斐波那契额数列的计算过程，在计算a4时，我们需要计算一次a3=a2+a1=1+1=2，在计算a5时我们因为需要a4和a3的值，所以我们又需要再计算两次a3的值，同理当我们计算a6时，我们需要共计3次计算a3的值，计算a7时，调用结果的次数就达到了5次，在计算第10项、第30和第40项项时，调用a3的次数就分别达到了21次、317811次和39088169次。可见随着下标的不断增大，对a3结果的调用次数将会飞速的增长。于是我们自然想到了将那些需要重复使用的中间计算结果储存下来，以便让计算机在需要调用这些结果时只需直接提取结果而不需要再次计算。这种想法就是记忆化搜索思路的核心。 3记忆化搜索 ○

记忆化搜索是在以上基础算法的基础上大大的进行优化的一种算法，他通过一定的方法对已经运行过的结果进行“记忆”，避免了大量的重复计算，从而数以亿计倍的极大程度的减小了程序的计算规模，缩短了运行时间，应用价值十分重大。

如上文所述，该算法核心是将需要多次使用的中间计算结果储存在一个专门的数组中， 以《N皇后问题》为例，在解题过程中，当计算13皇后问题时，在线评判系统会判定

先举一个简单的例子来说明记忆化方法对提高递归函数运算效率的巨大作用。仍然是计算斐波那契额数列，其求解函数fun如下：

int f[1000]={0};

int fun(int n)

{

int x; if (f[x]!=0)

return f[x];

if(n==1||n==2)

}

显然，以上函数对于数列中具有相同下标的项仅仅进行了一次求解，这就极大的提高了运算效率。实践证明，在求解a240时该方法的运算时间仅仅是普通递归的百亿分之一数量级。

刚刚的斐波那契额数列求解仅仅是使用了记忆化方法，并没有体现其再搜索中的应用，所以并不能算作是记忆化搜索。那么下面请看一个较为复杂的真正的记忆化搜索案例：求解最长公共子序列问题。其主要递归函数calc如下：

int a[1000][1000] else x=fun(n-1)+fun(n-2); f[n]=x; return x; x=1; //用于存放已经求出的结果 在每次计算时先在该数组中对该结果进行搜索，若能够找到则直接调用储存的结果。 其计算超时。但是当我们使用动态规划对改程序进行一定改进时，问题就迎刃而解了。

int calc(int i, int j)

{

}

虽然记忆化搜索在计算时间和计算效率上相对于一般的算法有了巨大飞跃，但是考虑到其执行过程中的递归的不断调用，我们还是能够发现其中比较明显的问题。那就是在递归时需不断的对栈中的数据进行读取和写入，并因此有着极大的开销。所以在我们解决问题的过程当中，在递推的动态规划较为容易实现时，还是应该尽量使用递推以提高程序效率。 最后，感谢刘邵翰老师在本学期对我和我们班同学的悉心教导与辛勤付出! int x = 0; if (a[i][j] != 0) return (a[i][j]); return 0; if (i==0 || j==0) x = max(calc(i - 1, j), x); x = max(calc(i, j - 1), x); if (str1[i-1] == str2[j-1]) x = max(calc(i - 1, j - 1) + 1, x); a[i][j] = x; return x;