算法分析与设计
查找迷宫的最短路径(广度算法)
计算机科学与技术12级
16班
2012/12/16
【摘要】本论文提出了求解迷宫最短路径问题的经典广度优先搜索。通过合理的变换, 将原问题转化为迷宫路径深度图的生成问题。最后对算法进行了严谨的分析和实例测试。迷宫求解是一个古老的游戏，要在迷宫中找到出口，需要经过一连串的错误尝试才能找到正确的路径，有的时候甚至找不到路径。类似于给定一个m*n的矩形网格，设其左上角为起点S。一辆汽车从起点出发驶向右下角终点T。在若干网格处设置了障碍，表示该网格不可到达。设计一个算法，求汽车从起点S出发到达终点T的一条路线。用计算机求解这个问题时，我们通常采用的是回溯方法，即从入口出发，顺某方向向前探索，若能走通，则继续往前走；否则沿原路退回。换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事。当然还有其他的方法来解决，例如顺序表，深度优先遍历，广度优先遍历等。
【关键词】:最短路径; 时间复杂度;广度优先搜索
【Summary】Maze solving is an ancient game , you want to find the exit in the maze , need to go through a series of trial and error to find the right path , and sometimes not even find the path .
A m * n rectangular grid , similar to a given set its upper-left corner as the starting point S . A car from the starting point towards the bottom right corner of the end of T . Set up barriers at certain grid , indicates that the grid is unreachable . Design an algorithm , find the car starting to reach the end point T, route from the starting point S . Use the computer to solve this problem , we usually use the backtracking method , that is, starting from the entrance , Shun forward to explore a direction , if we go through , and continue to move forward ; otherwise return along the same route . Continue to explore another direction , until all possible paths to explore to far . In order to ensure that in any position along the same route back , it is clear that the need to use a LIFO structure to save the path from the entrance to the current position . Therefore , in seeking labyrinth path algorithm application "stack" is the natural thing to do . Of course , there are other ways to solve , for example, the sequence table , depth-first traversal , breadth -first traversal .
【Key phrase】Shortest path ; time complexity ; breadth-first search
目录
摘要 (1)
关键字 (1)
一、问题描述 (3)
二、算法 (3)
1深度优先搜索 (3)
2广度优先搜索 (3)
三、参考代码 (4)
四、编程调试方面 (5)
五、小结 (5)
六、参考文献 (5)
一、问题描述
迷宫最短路径( the shortest path of maze) 问题是一个典型的搜索、遍历问题, 其程序设计想在人工智能设计、机器人设计等事务中均有应用。
如图所示, 一个N×M的大方块迷宫, 带斜线的单元格表示墙壁( 障碍) , 空白的单元格表示通道。迷宫问题可以表述为:
寻找从某一个给定的起始单元格( 迷宫入口) 出发, 经由行相邻或列相邻的通道单元格, 最终可以到达目标单元格( 迷宫出口) , 所走过的单元格序列。行进中, 只能沿上下左右四个方向前进。
而迷宫最短路径问题就是找出从迷宫入口到出口所经过单元格个数最少的路径。
二、算法
求解迷宫问题, 经典算法有深度优先搜索和广度优先搜索两种。
深度优先搜索(DFS) :
从入口出发, 顺着某一方向向前探索, 若能走通, 则继续往前走; 否则沿原路退回( 回溯) , 换一个方向再继续探索, 直至所有可能的通路都探索到为止。如果恰好某一步探索到出口, 则就找到了从入口到出口的路径。为了保证在任何位置上都能沿原路退回, 防止死循环, 需要使用堆栈来保存大量记录。而要求解迷宫最短路径, 则必须用深度优先搜索出所有到达出口的路径, 通过比较得到最短距离的路径, 这样也必然要求增加数据空间来保存搜索过程中当前最短路径, 增加了空间复杂度。
广度优先搜索(BFS) :
从入口出发, 离开入口后依次访问与当前位置邻接的单元格( 上下左右方向) , 然后分别从这些相邻单元格出发依次访问它们的邻接格, 并使“先被访问的单元格的邻接格‘先于’后被访问的单元格的邻接格”被访问, 直至访问到迷宫出口, 则找到了迷宫问题的最优解, 即迷宫最短路径。该算法的显著特点是“层层推进”, 探索点会随着探索的深入急剧增加, 相应地, 需要大量的空间用来保存探索过程的记录, 空间复杂度大。
三、参考代码：
uses crt;
const
migong:array [1..5,1..5] of integer=((0,0,-1,0,0), (0,-1,0,0,-1),
(0,0,0,0,0), (0,-1,0,0,0), (-1,0,0,-1,0));
{迷宫数组}
fangxiang:array [1..4,1..2] of -1..1=((1,0),(0,1),(-1,0),(0,-1));
{方向增量数组}
type node=record
lastx:integer; {上一位置坐标}
lasty:integer;
nowx:integer; {当前位置坐标}
nowy:integer;
pre:byte; {本结点由哪一步扩展而来}
dep:byte; {本结点是走到第几步产生的}
end;
var
lujing:array[1..25] of node; {记录走法数组}
closed,open,x,y,r:integer;
procedure output;
var i,j:integer;
begin
for i:=1 to 5 do begin
for j:=1 to 5 do
write(migong[i,j]:4); writeln;end;
i:=open;
repeat
with lujing[i] do
write(nowy:2,',',nowx:2,' <--');
i:=lujing[i].pre;
until lujing[i].pre=0;
with lujing[i] do
write(nowy:2,',',nowx:2);
end;
begin
clrscr;
with lujing[1] do begin {初始化第一步}
lastx:=0; lasty:=0; nowx:=1;nowy:=1;pre:=0;dep:=1;end;
closed:=0;open:=1;migong[1,1]:=1;
repeat
inc(closed); {队列首指针加1,取下一结点}
for r:=1 to 4 do begin {以4个方向扩展当前结点}
x:=lujing[closed].nowx+fangxiang[r,1]; {扩展形成新的坐标值}
y:=lujing[closed].nowy+fangxiang[r,2];
if not ((x>5)or(y>5) or (x<1) or (y<1) or (migong[y,x]<>0)) then begin
{未出界,未走过则可视为新的结点} inc(open); {队列尾指针加1}
with lujing[open] do begin {记录新的结点数据}
nowx:=x; nowy:=y;
lastx:=lujing[closed].nowx;{新结点由哪个坐标扩展而来}
lasty:=lujing[closed].nowy;
dep:=lujing[closed].dep+1; {新结点走到第几步}
pre:=closed; {新结点由哪个结点扩展而来} end;
migong[y,x]:=lujing[closed].dep+1; {当前结点的覆盖范围}
if (x=5) and (y=5) then begin {输出找到的第一种方案}
writeln('ok,thats all
right');output;halt;end;
end;
end;
until closed>=open; {直到首指针大于等于尾指针,即所有结点已扩展完} end.
四、编程调试方面：
用广度优先算法进行编成时, 由于牵涉到回溯、递归等较复杂的算法, 非常容易出错。尤其牵涉到复杂数据结构队列的操作，调试跟踪比较麻烦。
五、小结
本论文主要讨论一种解决迷宫最短路径问题的经典算法,从广度优先方面方面证明了该算法的正确性, 分析了算法的时间空间复度, 迷宫问题是一个古老的问题，要在迷宫中找到出口，需要经过一连串的的错误尝试才能找到正确的路径，有时甚至找不到路径。而且这里有很多方法可以完成迷宫问题，例如顺序表，深度优先遍历，广度优先遍历等，但是我写不出程序。于是参考了《数据结构》书和我以前的一些设计，所以我们这里用的是栈。在这个问题中主要运用了栈的各种基本操作，例如构造空栈，判断栈是否为空，入栈操作，出栈操作等等。
通过这次的作业，我又学会了一种解决迷宫问题的方法，我很高兴。当让在完成设计过程中，我也遇到了很多难题，比如用什么办法解决问题，怎样创建调用栈等等，但在再次复习了当时所学的《C++》,《数据结构》等课程后，发现这些问题还是可以解决的，而且解决
的方法不止一种。在这里我参考的最多的是《数据结构》中“栈的应用”那一节的知识，它给我了很大帮助。
六、参考文献:
[1] 严蔚敏, 吴伟民.数据结构[M].北京: 清华大学出版社, 2002.
[2] 陈媛.算法与数据结构[M].北京: 清华大学出版社, 2005.
[3] 苏德富.计算机算法设计与分析[M].北京: 电子工业出版社, 2005.
算法设计与分析实验报告 学院信息科学与技术学院 专业班级软件工程3班 学号 20122668 姓名王建君 指导教师尹治本 2014年10月
实验四 矩阵相乘次序 一、问题提出 用动态规划算法解矩阵连乘问题。给定n 个矩阵{A 1,A 2,…,A n }，其中A i 与A i+1是可乘的，i=1,2,…,n-1。要算出这n 个矩阵的连乘积A 1A 2…A n 。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A 是完全加括号的，则A 可表示为2个完全加括号的矩阵连乘积B 和C 的乘积并加括号，即A=(BC)。 例如，矩阵连乘积A 1A 2A 3A 4有5种不同的完全加括号的方式：（A 1（A 2（A 3A 4））），（A 1（（A 2A 3）A 4）），（（A 1A 2）（A 3A 4）），（（A 1（A 2A 3））A 4），（（（A 1A 2）A 3）A 4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A 是一个p ×q 矩阵，B 是一个q ×r 矩阵，则计算其乘积C=AB 的标准算法中，需要进行pqr 次数乘。 （3）为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵{A 1,A 2,A 3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A 1A 2）A 3），（A 1（A 2A 3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n 个矩阵{A 1,A 2,…,A n }（其中矩阵Ai 的维数为p i-1×p i ，i ＝1,2,…,n ），如何确定计算矩阵连乘积A 1A 2…A n 的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。 二、求解思路 本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。本实验的算法思路是： 1)计算最优值算法MatrixChain()：建立两张表（即程序中的**m 和**s ，利用二维指针存放），一张表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵…、直到n 个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n 个矩阵相乘的最小运算量；另一张表存储最优断开位置。 2)输出矩阵结合方式算法Traceback()：矩阵结合即是给矩阵加括号，打印出矩阵结合方式，由递归过程Traceback()完成。分三种情况： （1）只有一个矩阵，则只需打印出A1； （2）有两个矩阵，则需打印出（A1A2）； （3）对于矩阵数目大于2，则应该调用递归过程Traceback()两次，构造出最优加括号方式。 三、算法复杂度 该算法时间复杂度最高为）（n 3 O 。 四、实验源代码
《算法分析与设计》作业( 一) 本课程作业由两部分组成。第一部分为”客观题部分”, 由 15个选择题组成, 每题1分, 共15分。第二部分为”主观题部分”, 由简答题和论述题组成, 共15分。作业总分30分, 将作为平时成 绩记入课程总成绩。 客观题部分: 一、选择题( 每题1分, 共15题) 1、递归算法: ( C ) A、直接调用自身 B、间接调用自身 C、直接或间接 调用自身 D、不调用自身 2、分治法的基本思想是将一个规模为n的问题分解为k个规模 较小的字问题, 这些子问题: ( D ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 3、备忘录方法的递归方式是: ( C ) A、自顶向下 B、自底向上 C、和动态规划算法相同 D、非递归的 4、回溯法的求解目标是找出解空间中满足约束条件的: ( A )
A、所有解 B、一些解 C、极大解 D、极小解 5、贪心算法和动态规划算法共有特点是: ( A ) A、最优子结构 B、重叠子问题 C、贪心选择 D、 形函数 6、哈夫曼编码是: ( B) A、定长编码 B、变长编码 C、随机编码 D、定 长或变长编码 7、多机调度的贪心策略是: ( A) A、最长处理时间作业优先 B、最短处理时间作业优 先 C、随机调度 D、最优调度 8、程序能够不满足如下性质: ( D ) A、零个或多个外部输入 B、至少一个输出 C、指令的确定性 D、指令的有限性 9、用分治法设计出的程序一般是: ( A ) A、递归算法 B、动态规划算法
C、贪心算法 D、回溯法 10、采用动态规划算法分解得到的子问题: ( C ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 11、回溯法搜索解空间的方法是: ( A ) A、深度优先 B、广度优先 C、最小耗费优先 D、随机搜索 12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策 有可能导致算法: ( C ) A、所需时间变化 B、一定找到解 C、找不到所需的解 D、性能变差 13、贪心算法能得到: ( C ) A、全局最优解 B、 0-1背包问题的解 C、背包问题的 解 D、无解 14、能求解单源最短路径问题的算法是: ( A ) A、分支限界法 B、动态规划 C、线形规划 D、蒙特卡罗算法 15、快速排序算法和线性时间选择算法的随机化版本是:
《数值分析》计算实习题目 第一题： 1. 算法设计方案 （1）1λ，501λ和s λ的值。 1)首先通过幂法求出按模最大的特征值λt1，然后根据λt1进行原点平移求出另一特征值λt2，比较两值大小，数值小的为所求最小特征值λ1，数值大的为是所求最大特征值λ501。 2)使用反幂法求λs ，其中需要解线性方程组。因为A 为带状线性方程组，此处采用LU 分解法解带状方程组。 （2）与140k λλμλ-5011=+k 最接近的特征值λik 。 通过带有原点平移的反幂法求出与数k μ最接近的特征值 λik 。 （3）2cond(A)和det A 。 1）1=n λλ2cond(A)，其中1λ和n λ分别是按模最大和最小特征值。 2）利用步骤（1）中分解矩阵A 得出的LU 矩阵，L 为单位下三角阵,U 为上三角阵，其中U 矩阵的主对角线元素之积即为det A 。 由于A 的元素零元素较多，为节省储存量，将A 的元素存为6×501的数组中，程序中采用get_an_element()函数来从小数组中取出A 中的元素。 2.全部源程序 #include
《算法分析与设计》作业（一） 本课程作业由两部分组成。第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。第二部分为“主观题部分”，由简答题和论述题组成，共15分。作业总分30分，将作为平时成绩记入课程总成绩。 客观题部分： 一、选择题（每题1分，共15题） 1、递归算法：（C ） A、直接调用自身 B、间接调用自身 C、直接或间接调用自身 D、不调用自身 2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题，这些子问题：（D ） A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 3、备忘录方法的递归方式是：（C ） A、自顶向下 B、自底向上 C、和动态规划算法相同 D、非递归的 4、回溯法的求解目标是找出解空间中满足约束条件的：（A ） A、所有解 B、一些解 C、极大解 D、极小解 5、贪心算法和动态规划算法共有特点是：（ A ） A、最优子结构 B、重叠子问题 C、贪心选择 D、形函数 6、哈夫曼编码是：（B） A、定长编码 B、变长编码 C、随机编码 D、定长或变长编码 7、多机调度的贪心策略是：（A） A、最长处理时间作业优先 B、最短处理时间作业优先 C、随机调度 D、最优调度 8、程序可以不满足如下性质：（D ） A、零个或多个外部输入 B、至少一个输出 C、指令的确定性 D、指令的有限性 9、用分治法设计出的程序一般是：（A ） A、递归算法 B、动态规划算法
C、贪心算法 D、回溯法 10、采用动态规划算法分解得到的子问题：（ C ） A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 11、回溯法搜索解空间的方法是：（A ） A、深度优先 B、广度优先 C、最小耗费优先 D、随机搜索 12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法：（ C ） A、所需时间变化 B、一定找到解 C、找不到所需的解 D、性能变差 13、贪心算法能得到：（C ） A、全局最优解 B、0-1背包问题的解 C、背包问题的解 D、无解 14、能求解单源最短路径问题的算法是：（A ） A、分支限界法 B、动态规划 C、线形规划 D、蒙特卡罗算法 15、快速排序算法和线性时间选择算法的随机化版本是：（ A ） A、舍伍德算法 B、蒙特卡罗算法 C、拉斯维加斯算法 D、数值随机化算法 主观题部分： 二、写出下列程序的答案（每题2.5分，共2题） 1、请写出批处理作业调度的回溯算法。 #include
《软件系统分析与设计》 期末大作业 选题名称：游戏平台管理系统设计人：徐文豪刘青海 赖超宇甘智宏 班级：软工143班 南昌大学软件学院 2016.6.1
目录 一、整体描述 (2) 二、需求分析 (3) 三、系统功能概况 (4) 四、类的属性与方法 (5) 五、系统界面界限 (11) 六、设计模型 (13) 七、设计原则 (17) 八、设计模式······················
一、整体描述 随着移动通讯的发展，手机应用也越来越多，其中，游戏应用占据了很大的比重，游戏平台管理系统是整合了大量游戏应用，以及玩家线上交流的平台。 主要受众群：拥有移动端或电脑端的人群。 应用前景：移动互联的发展为游戏平台的发展提供了很大的生存空间，应用前景十分广阔 盈利方式：向平台中游戏的开发商收取一定的费用，游戏玩家向游戏中注入资金时，收取一定比例的游戏收入。 面临的困难：游戏平台前期的推广，提高游戏平台本身对开发商和游戏玩家的吸引力，游戏平台能否适应大部分游戏玩家的要求。 玩家首先要注册账号，然后就可以在上面下载游戏应用，上传自己的游戏资源。同时，根据玩家的活跃程度获取相应积分，用积分可以兑换游戏礼包，也会根据玩家等级在游戏装备上给与相应的优惠和等级奖励。玩家在每一款游戏的评论区都可以交流游戏经验，提出意见和建议，以便游戏及时更新，弥补相应不足。玩家也可以建立游戏工会，不同游戏的玩家都可以加入，分享自己的游戏心得或者转赠游戏装备或积分。
二、需求分析 时间when：游戏厂商：随时；注册用户：随时；管理人员：正常工作时间。 地点Where：游戏厂商，管理人员：工作地点；注册用户：随地 人员who：游戏厂商，管理人员，注册用户， What：游戏厂商：推广游戏，管理人员：扩大服务，盈利；注册人员：玩游戏。 Why：游戏厂商：推广力度不大，效果不好，管理人员：方便管理，注册用户：良好的游戏环境。 性能Performance：系统提供服务的效率，响应时间快，由于是手机端的APP吞吐量不需要太大。 成本Cost：实现系统需要付出的代价，耗费****元 时间Time：2016年6月3日 可靠性Reliability: 需要系统长时间正确运行的能力 安全性Security: 由于该平台会涉及资金的流动，所以需要对信息安全的保护能力。 合规性Compliance: 需要符合各种行业的标准，法律法规，规范。技术性Technology:要求基于安卓平台开发。 兼容性Compatibility:需要与一些支付平台进行兼容能力。还有对游戏的兼容性。
一需求分析 此系统是一个类似于淘宝网的在线衣服销售系统，相当于淘宝网上的一个专门买衣服的网店，它具有用户注册，用户登录，修改密码，显示系统功能，查看订购历史以及订货。 1.1需求列表： （1）用户管理：用户管理的需求包括用户注册，用户登录以及修改密码。 用户注册是添加一个我们网上衣店的新用户；用户登录是用户想要进 入系统时必须采取验证身份的步骤；修改密码是为了用户的安全性考 虑，当密码存在不安全的因素时，适时修改密码。 （2）商品衣服的管理：商品管理包括订购衣服和查看订购衣服的历史。订购衣服是当我们衣店的库存数量不足时必须采取的；查看订购衣服的 历史有助于我们更好地了解衣服的订购情况。 （3）显示系统功能：此功能是用来让用户能很清楚地了解此系统所实现的各种功能。 1.2系统用例图：
1.3用例分析及场景描述： 用户注册用例： 这部分主要是新用户进行注册的过程，首先用户进入到注册页面，填写注册信息并提交，如果无误的话系统会给予注册成功的提示，如果注册失败会提示注册失败信息。 用户登录用例： 此功能模块针对的对象是本网站的会员既已经注册的会员，会员首先填写用户名和密码，然后点击登录按钮，如果网站数据库中存在此会员并且密码正确则提示登录成功提示，如果网站不存在此用户或密码不正确，系统会提示用户登录失败。 修改密码用例： 此用例针对注册会员进行操作。用户登录成功会可以进入网站主页面，如果用户想修改密码的话可以单击修改密码按钮，进行密码修改，用户输入新密码单击修改按钮即可完成密码修改。
显示系统功能用例： 此功能针对注册会员，会员首先登录到网站，进入主页，主页会有相关操作的按钮，显示系统所提供给会员操作的功能，用户可以针对自己的需要选择系统提供的功能。 订货衣服用例： 此功能针对注册登录会员，网站提供两种订购方案：单件订购和定制套装。用户可以根据自己的需求来选择。 单件订购方案：用户选择是上衣还是裤子，并填写订购的数量，确认无误后单击订购按钮即可，如果订购成功，系统会提示订购成功，失败则会提示订购失败。 定制套装方案：用户选择定制套装的档次（高、中、低），并填写订购的数量，确认无误后单击订购按钮即可，如果订购成功，系统会提示订购成功，失败则会提示订购失败。 显示订购历史用例： 此功能针对注册会员，用户登录到系统后，主页显示系统功能中包括历史查看选项，用户可以单击进入历史交易记录页面，页面将显示用户所有的交易记录。 二设计模式 2.1单件模式 2.1.1单件模式的定义
《算法分析与设计》作业参考答案 作业一 一、名词解释： 1.递归算法：直接或间接地调用自身的算法称为递归算法。 2.程序：程序是算法用某种程序设计语言的具体实现。 二、简答题： 1.算法需要满足哪些性质？简述之。 答：算法是若干指令的有穷序列，满足性质： （1）输入：有零个或多个外部量作为算法的输入。（2）输出：算法产生至少一个量作为输出。 （3）确定性：组成算法的每条指令清晰、无歧义。 （4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 2.简要分析分治法能解决的问题具有的特征。 答：分析分治法能解决的问题主要具有如下特征： （1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 3.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 答：将递归算法转化为非递归算法的方法主要有： （1）采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归， 只不过人工做了本来由编译器做的事情，优化效果不明显。（2）用递推来实现递归函数。 （3）通过Cooper 变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，但其适用范围有限。 三、算法编写及算法应用分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 do for j ←1 to n-i do if a[j] 算法分析大作业 动态规划方法解 乘法表问题和汽车加油行驶问题目录 1.动态规划解乘法表问题 1.1问题描述------ 1.2算法设计思想------ 1.3设计方法------ 1.4源代码------ 1.5最终结果------ 2.动态规划解汽车加油行驶问题 2.1问题描述------ 2.2算法设计思想------ 2.3设计方法------ 2.4源代码------ 2.5最终结果------ 3.总结 1.动态规划解决乘法表问题 1.1问题描述 定义于字母表∑{a,b,c)上的乘法表如表所示： 依此乘法表,对任一定义于∑上的字符串,适当加括号表达式后得到一个表达式。 例如,对于字符串x=bbbba,它的一个加括号表达式为(b(bb))(ba)。依乘法表,该表达式的值为a。 试设计一个动态规划算法,对任一定义于∑上的字符串x=x1x2…xn，计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a。 1.2算法设计思想 设常量a,b,c 分别为 1, 2 ,3 。n 为字符串的长度。 设字符串的第 i 到第 j 位乘积为 a 的加括号法有result[i][j][a] 种， 字符串的第 i 到第 j 位乘积为 b 的加括号法有result[i][j][b] 种, 字符串的第 i 到第 j 位乘积为 c 的加括号法有 result[i][j][c] 种。 则原问题的解是：result[i][n][a] 。 设 k 为 i 到 j 中的某一个字符，则对于 k 从 i 到 j ：result[i][j][a] += result[i][k][a] * result[k + 1][j][c] + result[i][k][b] * result[k + 1][j][c] + result[i][k][c] * result[k + 1][j][a]; result[i][j][b] += result[i][k][a] * result[k + 1][j][a] + result[i][k][a] * result[k + 1][j][b] + result[i][k][b] * result[k + 1][j][b]; result[i][j][c] += result[i][k][b] * result[k + 1][j][a] + result[i][k][c] * result[k + 1][j][b] + result[i][k][c] * result[k + 1][j][c]; 《算法分析与设计》 学习中心： 专业： 学号： 姓名： 作业练习二 一、名词解释 1、MST性质 2、子问题的重叠性质 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题的重叠性质。 二、简答题 1、简述动态规划算法求解的基本要素。 答：动态规划算法求解的基本要素包括： 1)最优子结构是问题能用动态规划算法求解的前提； 2)动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果，即重叠子问题。 2、备忘录方法和动态规划算法相比有何异同简述之。 答：备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此问题时，只要简单地查看该子问题的解答，而不必重新计算。备忘录方法与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同的子问题的重复求解，而直接递归方法没有此功能。 3、贪心算法求解的问题主要具有哪些性质简述之。 答：贪心算法求解的问题一般具有二个重要的性质： 一是贪心选择性质，这是贪心算法可行的第一个基本要素； 另一个是最优子结构性质，问题的最优子结构性质是该问题可用贪心算法求解的关键特征。 三、算法编写及算法应用分析题 1、设计求解如下最大子段和问题的动态规划算法。只需给出其递推计算公式即可。 最大子段和问题：给定由n 个整数（可能为负整数）组成的序列a1a2 … an，求该序列形如Σi≤k≤j ak的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义，所求的最优值为max{0, max1≤i≤j≤n Σi≤k≤j ak }。 深圳大学研究生课程论文 题目大作业：变位词实验成绩 专业计算机与软件学院软件工程 课程名称、代码 年级2015 姓名文成 学号2150230509 时间2015 年12 月任课教师杨烜 一、大作业要求与内容 大作业内容： 在下列问题中挑选一个问题，选用适当的算法进行实现，在课堂上，针对该问题完成一个10分钟的论文演讲与演示，并提交演讲PPT。（30分） 在一个类似英语词典的大文件中找出变位词的所有集合，例如，tea和eat是变位词，同属一个集合，找出所有这种集合。 大作业要求：（70分） （1）要求演示算法解决问题的完整过程，如果我对解这个问题一无所知，看了你的解决过程，就要能理解算法是如何解决问题的； （2）要求交互界面活泼生动，演示速度可控； （3）尽可能提供丰富的功能让我理解你是如何解决这个问题的； （4）提交源程序、大作业报告（介绍详细的算法设计说明和使用说明）； （5）以论文、报告等形式考核专用答题纸写大作业，大作业报告中要分析算法效率，并给出实测效率和理论效率图表； （6）大作业用5号字体，总页数不得少于8页，否则视为无效。 二、大作业步骤 Introduction: 给定一本英语单词词典，找出所有的变位词集。所谓的变位词是指，组成各个单词的字母完全相同，只是字母排列的顺序不同。例如，tea和eat是变位词，同属一个集合，找出所有这种集合。 Motivating idea: 1.如何判断两个单词是否为变位词。 思路一： 如果两个单词是变位词，那么它们具有相同的长度，且每个英语字母的个数是一样的。我们只需要挨个对各个单词进行比较即可。这个思路容易想，但时间效率太低，还可以继续改进一下，且看下面的思路二。 思路二： 将两个字符串按照字母表顺序排序，看排序后的字符串是否相等，如果相等则是兄弟字符串（变位词）。这种方法的时间效率根据你使用的排序算法不同而不同。这里我采取思路二，我使用的是快速排序。但是依旧有个问题，单词与单词一个一个比较的话效率还是太低了，我们可以再做改进。 2.如何从字典中找出所有变位词的集合。 思路一： 对于这个问题，最快想到的最直接的方法就是针对每一个单词跟字典中的其他单词进行比较。然而，假设一次比较至少花费1微秒的时间，则拥有二十万单词的字典将花费：200000 算法设计与分析期末成绩考核标准 要求：算法设计与分析考试方式为小论文形式。下面给出了小论文的参考模型和参考题目，供大家选择。 1.小作业题目（仅供参考） （题目的难易：●简单10道题★中等11道题▲复杂10道题） ●最佳浏览路线问题 问题描述：某旅游区的街道呈网格状，其中东西向的街道都是旅游街，南向的街道都是林荫道。由于游客众多，旅游街被规定为单行道。游客在旅游街上只能从西向东走，在林荫道上既可以由南向北走，也可以从北向南走。 阿隆想到这个旅游区游玩，他的好友阿福给了他一些建议，用分值表示所有旅游街相邻两个路口之间的道路浏览的必要程度，分值从-100到100的整数，所有林荫道不打分，所有分值不可能全是负值。阿隆可以从任一路口开始浏览，在任一路口结束浏览，请写出一个算法，帮助阿隆寻找一条最佳的浏览路线，使得这条路线的所有分值总和最大。（算法设计与分析第二版P190—11题） ●问题描述：某工业生产部门根据国家计划的安排，拟将某种高效率的5台机器，分配给所属的，A，B，C个工厂，各工厂在获得这种机器后，可以为国家盈利如图表所示，问：这5台机器如何分配给各工厂，才能使得国家盈利最大？（P190-14题） ●问题描述：编写算法对输入的一个整数，判断他能否被4，7，9整除，并输出一下信息之一， 能同时被4，7，9整除; 能被其中两个数（要指出那两个）整除 能被其中一个数（要指出哪一个）整除 不能被4，7，9任一个整除。（P118-16） ●问题描述：某一印刷厂有6项加工任务，对印刷车间和装订车间所需的时间表如下图：完成每项任务都要先去印刷车间印刷，再到装订车间装订。问咋样安排这6项加工任务的加工工序，使得加工工时最少？（P191-17） ●问题描述：编写用动态规划法求组合数m C的算法(P191-19). n ●问题描述：仿照分治算法中两个大数相乘的算法策略，完成求解两个n*n阶矩阵A和矩阵B的乘积的算法。假设n=2k,要求算法的复杂性要小于O（n3）.(P190-12) ●问题描述：在一个n*m的方格中，m为奇数，放置有n*m个数，方格中间的下方有一人，此人可按照5个方向前进但不能跃出方格，如图所示，人每走过一个方格必须取此方格中的数。要求找到一条路径从低到顶的路径，使其数相加之和为最大，输出最大和的值。（P190-14）●问题描述：N 块银币中有一块不合格，已知不合格的银币比正常的银币重，先用一天平，请利用它找不合格的银币，并且用天平的次数最少。（P-19116） ●问题描述：旅行售货员问题：某售货员要到若干城市去推销商品，已知个城市之间的路线。她要选择一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或总旅行费）最小（P246-6） ●问题描述：54张扑克牌，两个人轮流拿牌，每人每次最少取一张，最多取四张，谁那最后一张谁输。编写模拟计算机先拿牌取且必胜的算法。（P189-3） ★题目一选课方案设计（P290） ★题目二表达式相等判断（P291） 《算法分析与设计》实验指导. 实验一锦标赛问题 [实验目的] 1.基本掌握分治算法的原理. 2.能用程序设计语言求解锦标赛等问题的算法; [预习要求] 1.认真阅读数据结构教材和算法设计教材,了解分治算法原理; 2.设计用分治算法求解背包问题的数据结构与程序代码. [实验题] 【问题描述】设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表： （1）每个选手必须与其他n-1个选手各赛一次； （2）每个选手一天只能参赛一次； （3）循环赛在n-1天内结束。 请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中1≤i≤n，1≤j≤n-1。 [实验提示] 我们可以按分治策略将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。 1 2 3 4 5 6 7 1 （1）（2）（3） 图1 2个、4个和8个选手的比赛日程表 图1所列出的正方形表（3）是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这 样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。 [实验步骤] 1.设计并实现算法并准备测试用例,修改并调试程序,直至正确为止; 2.应用设计的算法和程序求锦标赛问题; 3.去掉测试程序,将你的程序整理成功能模块存盘备用. [实验报告要求] 1.阐述实验目的和实验内容; 2.阐述分治算法原理; 3.提交实验程序的功能模块; 4.记录最终测试数据和测试结果。 [思考与练习] 【金块问题】老板有一袋金块(共n块，n是2的幂（n>=2）），将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器，请用最少的比较次数找出最重和最轻的金块。 《算法分析与设计》作业（三） 本课程作业由两部分组成。第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。第二部分为“主观题部分”，由简答题和论述题组成，共15分。作业总分30分，将作为平时成绩记入课程总成绩。 客观题部分： 一、选择题（每题1分，共15题） 1、贪心算法解各个子问题的方法是：（） A、自底向上 B、自顶向下 C、随机选择 D、自底向上或自顶向下 2、用回溯法解旅行售货员问题时生成的树是：（） A、子集树 B、排列树 C、二叉树 D、多叉树 3、在n后问题中任意两个皇后能放在：（） A、同一行 B、同一列 C、同一斜线 D、以上都不行 4、用回溯法解0-1背包问题时生成的解空间树是：（） A、子集树 B、排列树 C、二叉树 D、多叉树 5、用贪心算法解单源最短路径问题时采用的算法是：（） A、Dijkstra算法 B、Prime算法 C、Kruskal算法 D、蒙特卡罗算法 6、在用动态规划解流水作业调度时的最优调度法则是：（） A、最优子结构 B、重叠子问题 C、Johnson法则 D、最长处理时间作业优先 7、算法与程序的区别在于：（） A、输入 B、输出 C、指令的确定性 D、指令的有限性 8、从分治法的一般设计模式可以看出，用它设计的程序一般是：（） A、顺序 B、选择 C、循环 D、递归 9、回溯法的解空间是在搜索过程中：（） A、动态产生 B、静态产生 C、无解空间 D、动态或者静态产生 10、在用贪心法解多机调度时的贪心选择策略是：（） A、最优子结构 B、重叠子问题 C、Johnson法则 D、最长处理时间作业优先 11、合并排序和快速排序采用的共同策略是：（） A、分治法 B、蒙特卡罗法 C、拉斯维加斯法 D、单纯形法 12、用回溯法解最大团问题时生成的解空间树是：（） 题目作业调度问题及算法分析 学院名称：计算机与信息工程学院 专业名称：计算机科学与技术 目录 《算法设计与分析》课程大作业 (1) 一．动态规划算法解决流水作业调度 (3) 1、问题描述 (3) 2、算法分析 (3) 3. 算法的描述 (4) 4、部分算法实现 (5) 5. 运行结果 (6) 6、时空效率分析 (6) 二．贪心算法解多机调度问题 (6) 1、问题描述 (6) 2、算法分析 (7) 3.部分算法实现 (7) 4.计算复杂性分析 (8) 5. 运行结果 (9) 三．回溯法解决批作业调度问题 (9) 1.问题描述 (9) 2.算法思想 (10) 3. 部分算法实现 (11) 4.运行结果 (12) 5.时间复杂性分析 (12) 四．作业调度算法比较 (12) 五．课程学习总结 (13) 摘要： 在现代企业中，作业调度已成为提高资源利用率、从而提高企业运行效益的关键环节之一。把各个作业分配到车间现有的设备上，并确定它们的先后次序，这是一项复杂的工作本文就作业调度排序问题进行了研究，通过对几个经典作业调度算法的分析讨论，总结了各个算法对作业调度的求解过程，并给出了每个算法的复杂度及性能分析。 关键词：作业调度；动态规划；贪心算法；回溯法； 一．动态规划算法解决流水作业调度 1、问题描述 给定n 个作业，每个作业有两道工序，分别在两台机器上处理。一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。一个作业只有在机器1上的处理完成以后才能由机器2处理。假设已知作业i 在机器j 上需要的处理时间为t[i,j]。流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n 个作业。 2、算法分析 直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。 在一般情况下，机器M1开始加工S 中作业时，机器M2还在加工其他作业，要等时间t 后才可利用。将这种情况下完成S 中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。 由流水作业调度问题的最优子结构性质可知， )}},{({min )0,(1i i n i b i N T a N T -+=≤≤（1） (单选题)1: 图中有关路径的定义是（）。 A: 由顶点和相邻顶点序偶构成的边所形成的序列 B: 由不同顶点所形成的序列 C: 由不同边所形成的序列 D: 上述定义都不是 正确答案: (单选题)2: ()是一个基本完整的开发工具集，它包括了整个软件生命周期中所需要的大部分工具，如UML工具、代码管控工具、集成开发环境等等。 A: VS B: VM C: Dev-C++ D: IDE 正确答案: (单选题)3: 下列数据结构中，属于非线性结构的是（）。 A: 循环队列 B: 带链队列 C: 二叉树 D: 带链栈 正确答案: (单选题)4: 下列叙述中正确的是（）。 A: 顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的 B: 顺序存储结构只针对线性结构，链式存储结构只针对非线性结构 C: 顺序存储结构能存储有序表，链式存储结构不能存储有序表 D: 链式存储结构比顺序存储结构节省存储空间 正确答案: (单选题)5: 十六进制中最大的数码是（）。 A: 16 B: 15 C: F D: E 正确答案: (单选题)6: 二进制，就表示某一位置上的数运算时是逢（）进一位。 A: 2 B: 8 C: 9 D: 10 正确答案: (单选题)7: 在程序代码编辑框外（一般都是程序代码的最左侧）双击，就成功设置了一个断 点，设置成功后会在该行的最前面显示一个圆点，这样的过程称作()。 A: 设置断点 B: 单步调试 C: 程序编译 D: 程序调试 正确答案: (单选题)8: 递归结束条件，又称为()。 A: 递归判定 B: 递归策略 C: 递归出口 D: 递归返回 正确答案: (单选题)9: 下列叙述中正确的是（）。 A: 一个逻辑数据结构只能有一种存储结构 B: 数据的逻辑结构属于线性结构，存储结构属于非线性结构 C: 一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D: 一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率 正确答案: (单选题)10: 下列说法正确的是()。 A: 关键字是数据元素（或记录）中某个数据项的值，可以标识一个记录，称为主关键字。B: 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。 C: 对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为log2n。 D: 折半查找的先决条件：表中结点按关键字有序，且顺序（一维数组）存储。 正确答案: (单选题)11: 下列排序方法中，哪一个是稳定的排序方法？() A: 直接选择排序 B: 二分法插入排序 C: 希尔排序 D: 快速排序 正确答案: (单选题)12: isalnum（）函数用来（）。 A: 判断字符串 B: 判断大写 C: 判断数字或字母 D: 判断小写 正确答案: (单选题)13: 深度优先搜索的搜索策略是()。 A: 尽可能“深”地搜索图 算法分析与设计作业答案 第一章绪论 一填空 算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算 2..算法具备五个重要特性：确定性、可实现性、数据输入、数据输出、有穷性 3. 要制定一个算法，一般要经过设计、确认、分析、编码、调试等阶段。 4. 算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。 5．一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上。时间和空间资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。 7.算法的时间复杂性函数用T(n)表示，它是问题的大小n 的函数。 8. n在不同的问题中有不同的表现形式。指出下列问题中n的计量。 1) 在数组中找值为c的分量，n表示数组中分量的个数 2) 两个矩阵相乘, n表示矩阵的阶 3) 一个数表的排序，n表示数组中元数的个数 4) 遍历一棵二叉树，n表示树中的结点数 9.最坏情况下的时间复杂性定义：W(n) = max{ T(n，I) } , I∈Dn 10. 平均情况下的时间复杂性定义：A(n)＝∑P( I )T(n，I) I∈Dn 11.最具有可操作性和实际价值的是最坏情况下的时间复杂性定义复杂性。教材中没有特殊说明时，T(n)一般指的就是最坏情况下的时间复杂性定义。 12．f(n)=O(g(n))表示 当且仅当存在正的常数C和N0，使得对于所有的n >=N0，有f(n) <=cg(n) 。 13. 写出下列f(n)的渐进性态： 1) f(n)=C0，为常数：f(n)= O( 1 )。 2) f(n)= 3n+2：f(n)= O( n )。 3) f(n)= 6×2n +n ：f(n)= O( 2n )。 4) f(n)= nlog n ：f(n)= O( nlog n )。 二 分析算法复杂性 1. 已知不重复且已经按从小到大排好的m 个整数的数组A[L ．m](为简单起见，设m ＝2k ，k 是一个确定的非负整数)。对于给定的整数c ，要求寻找一个下标i ，使得A[i]=c,若找不到，则返回一个0。算法如下： procedure search( c) /*c 是整型数 */ { i ←0; j ←l; while A[j] 2014级计算机科学与技术专业“算法设计与分析”大作业题 2015学年~2016学年第2学期 2016年4月18日 总体要求 本次综合大作业（上机实现题目）是为了配合“算法设计与分析”课程的讲授而设置的，目的在于培养学生理论联系实际的问题求解能力。综合大作业题目共两道，两题均要求采用动态规划算法求解。每题50分。以小组为单位检查，自由组合（可跨越班级），每组人数一般不少于3人、但不超过5人。每组提交1份课程报告，检查时每组至少须有1人做成果展示演讲（答辩），在课堂上就题目的设计思想、实现方法的正确性等进行说明，全组成员一起参与答辩，回答教授及同学的提问与质疑。 对于“动态规划”问题，报告中必须对最优值函数和标记函数的含义进行详细说明，列出子问题计算中所使用的有关最优值函数和标记函数的递推关系（一般采用递归式加以描述）和初值（边界条件）。给出所设计算法的时间复杂度分析。 每组自备2、3个相关问题的实例，报告中以实例中的数据描述算法的执行步骤。 一、广义背包问题 广义背包问题的描述如下：给定载重量为M的背包和n种物品，每种物品有一定的重量和价值，现在需要设计算法，在不超过背包载重量的前提下，巧妙选择物品，使得装入背包的物品的总价值最大化。规则是，每种物品均可装入背包多次或不装入（但不能仅装入物品的一部分）。请用数学语言对上述背包问题加以抽象，在此基础上给出动态规划求解该问题的递归公式。要求对所给公式中的符号意义加以详细说明，并简述算法的求解步骤。用一种你熟悉的程序设计语言加以实现。 二、在下面A 、B两道题中选取一道感兴趣的题目完成 A、加工顺序问题 “加工顺序问题”又被称为“批处理作业调度问题”。 设有n个工件需要在机器M1和M2上加工，每个工件的加工顺序都是先在M1上加工，然后在M2上加工。t1j，t2j分别表示工件j在M1，M2上所需的加工时间（j=1，2，···，n）。问应如何在两机器上安排生产，使得第一个工件从在M1上加工开始到最后一个工件在M2上加工完所需的总加工时间最短？关于此（类）问题的回溯法求解被作为经典案例在很多教材或参考文献中出现，现要求设计求解此问题的动态规划算法。 请用数学语言对“加工顺序问题”加以抽象，在此基础上给出动态规划求解该问题的递归公式。要求对所给公式中的符号意义加以详细说明，并简述算法求解步骤。用一种你熟悉的程序设计语言加以实现。 提示（分析最优解的性质，刻画最优解的结构—最优子结构性质）算法分析大作业动态规划方法解乘法表问题和汽车加油行驶问题#精选.
算法分析与设计(线下作业二)
算法分析大作业 寻找变位词
算法分析 期末大作业内容
《算法设计与分析》实验指导
算法分析与设计作业(三)
算法设计与分析课程大作业
东师《算法分析与设计》19春在线作业2
算法分析与设计之作业习题答案
2016春季14级本科“算法设计与分析”大作业题目要求
相关主题
文本预览