数据结构课程设计最小生成树

1、成绩评定表学生姓名班级学号专 业信息与计算科学课程设计题目1.分支限界解决布线问题2.船只停泊港口管理动态规划解决最长公共子序列问题评语组长签字：成绩日期20 年 月 日课程设计任务书学 院理学院专 业信息与计算科学学生姓名班级学号课程设计题目1.分支限界解决布线问题2.动态规划解决最长公共子序列问题实践教学要求与任务:1、巩固和加深对计算机算法分析与设计基本知识的理解。2、初步掌握简单软件的分析方法和设计方法。3、了解与课程有关的工程技术规范，能正确解释和分析设计结果。4、具体任务（1）分支限界解决布线问题（2）动态规划解决最长公共子序列问题。工作计划与进度安排:第一天 查阅资相关料； 第二

2、、三天 程序设计；第四天 程序调试； 第五天 答辩指导教师： 201 年 月 日专业负责人：201 年 月 日学院教学副院长：201 年 月 日摘要“计算机算法设计与分析”着重介绍了计算机算法设计领域的基本原则和根本原理。深入分析了一些计算机模型上的算法，介绍了一些和设计有效算法有关的数据结构和编程技术，为读者提供了有关递归方法、分治方法和动态规划方面的详细实例和实际应用，并致力于更有效算法的设计和开发。同时，对NP完全等问题能否有效求解进行了分析，并探索了应用启发式算法解决问题的途径。本文第一问，随着信息技术的发展和嵌入式设备的广泛使用电路布线问题越来越受到人们的重视要使电子电路获得最佳性能

3、不仅元器件的布置占有着重要的地位而且导线的布设也是非常重要的特别是在涉及到线路成本的布线方案中一个好的布线算法就显得尤为重要 本文首先对一类电路板低成本布线问题进行了分析进而给出了解决这一问题的分支限界解法并对所提出算法的时间复杂度进行了分析和讨论。本文第二问，掌握动态规划法的原理，并能够按其原理编程实现求两个序列数据的最长公共子系列，以加深对其的理解。关键字：分支限界；布线问题；动态规划目录1 分支限界解决布线问题11.1问题重述11.2问题分析11.3算法分析与设计11.4算法的实现与结果22 动态规划解决最长公共子序列问题92.1问题重述92.2问题分析92.3算法分析与设计92.4算法

4、实现与结果10参考文献141 分支限界解决布线问题1.1问题重述布线问题：如图1所示，印刷电路板将布线区域划分成n*m个方格。精确的电路布线问题要求确定连接方格a的中点到b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，如图1所示。为了避免线路相交，已经布线的方格做了封锁标记（如图1中阴影部分），其他线路不允许穿过被封锁的方格。1.2问题分析题目的要求是找到最短的布线方案，从图1的情况看，可以用贪婪算法解决问题，也就是从a开始朝着b的方向垂直布线即可。实际上，再看一下图2，就知道贪婪算法策略是行不通的。因为已布线的放个没有规律的所以直观上说只能用搜索方法去找问题的解。根据布线方法的要

5、求，除边界或已布线处，每个E-结点分支扩充的方向有4个：上、下、左、右，也就是说，一个E-结点扩充后最多产生4个活结点。以图2的情况为例，图的搜索过程如图3所示。搜索以a为第一个E-结点，以后不断扩充新的活结点，直到b结束（当然反之也可以）。反过来从b到a，按序号8-7-6-5-4-3-2-1就可以找到最短的布线方案。从图3中也可以发现最短的布线方案是不唯一的。且由此可以看出，此问题适合用分支限界搜索。1.3 算法分析与设计算法分析：分支限界搜索法是一种在问题解空间上进行搜索尝试的算法。所谓“分支”是采用广度优先的策略，依次搜索E-结点的所有分支，也就是所有的相邻结点。和回溯法一样，在生成的结

6、点中，抛弃那些不满足约束条件（或者说不可能到处最优可行解）的结点，其余结点加入活结点表。然后从表中选择一个节点作为下一个E-结点，继续搜索。选择下一个E-结点的方式不同，会出现几种不同的分值搜索方式。FIFO搜索先进先出（FIFO）搜索算法要依赖“队”做基本的数据结构。一开始，根节点是唯一的活结点，根节点入队。从活结点队中取出根节点后，作为当前扩展结点。对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子加入或节点队列中。再从活结点表中取出队首结点（对中最先进来的结点）为当前结点，直到找到一个解或活结点队列为空为止。LIFO搜索后进先出（LIFO）搜索算法要依

7、赖“栈”做基本的数据结构。一开始，根结点入栈，从栈中弹出一个结点为当前扩展结点。对当前扩展结点，从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子入栈，再从栈中弹出一个结点（栈中最后进来的结点）为当前扩展结点，直到找到一个解或栈为空为止。优先队列式搜索为了加速搜索的进程，应采用有效的方式选择E-结点进行扩展。优先队列搜索，对每一个活结点计算一个优先级（某些信息的函数值），并根据这些优先级，从当前结点表中优先选择一个优先级最高（最有利）的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。算法设计：开辟m*n的二维数组模拟布线区域，初始值均为0，

8、表示没有被使用。已使用的位置，通过键盘输入其下标，将对应值置为-1.输入方格a、b的下标，存储在变量中。一开始，唯一的活结点是a。从活结点表中取出后为当前扩展结点。对当前扩展结点，按上、下、左、右的顺序，找出可布线的位置，加入活结点队列中，再从活结点队列中取出后为当前扩展结点。依此类推，直到搜索到达b结点，然后按序号8-7-6-5-4-3-2-1输出最短布线方案，算法结束。或活结点队列已为空，表示无解，算法结束。1.4算法的实现与结果 通过算法的分析与设计，计算如图所示4所示的布线问题代码：#include <stdio.h>#include <stdlib.h>typ

9、edef struct Positionint row;int col;Position;typedef struct teamint x;int y;struct team *next;team,*TEAM;Position start,end,path100;TEAM team_l=NULL;int a100100;int m,n,path_len;void output()int i,j;printf("n|-布线区域图-|n");for(i=0;i<m+2;i+)for(j=0;j<n+2;j+)printf("%5d",aij);p

10、rintf("n");printf("|-|n");return;void input_data()char yes;int x,y;printf("创建布线区域.nn");printf("请输入区域大小(行列的个数): ");scanf("%d,%d",&m,&n);printf("请输入开始点坐标(x,y): ");scanf("%d,%d",&start.row,&start.col);printf("请输入

11、结束点坐标(x,y): ");scanf("%d,%d",&end.row,&end.col);printf("区域内是否有被占用点? (y/n) ");fflush(stdin);scanf("%c",&yes);fflush(stdin);while(yes='y')printf("请输入占用点的坐标(x,y): ");scanf("%d,%d",&x,&y);fflush(stdin);if(x<0 | x>m+

12、1 | y<0 | y>n+1 | (x=start.row && y=start.col) | (x=end.row && y=end.col)printf("输入错误,请重新输入!n");continue;elseaxy=-1;printf("是否还有被占用点? (y/n) ");scanf("%c",&yes);fflush(stdin);for(x=0;x<m+2;x+)a0x=-1;am+1x=-1;for(x=0;x<n+2;x+)ax0=-1;axn+1=-

13、1;return;void inq(Position p)TEAM t,q;q=team_l;t=(TEAM)malloc(sizeof(TEAM);t->x=p.row;t->y=p.col;t->next=NULL;if(team_l=NULL)team_l=t;return ;while(q->next!=NULL)q=q->next;q->next=t;return;Position outq()Position out;out.row=team_l->x;out.col=team_l->y;team_l=team_l->next;

14、return out;void find_path()Position offset4;Position here=start.row,start.col;Position nbr=0,0;int num_of_nbrs=4;int i,j;offset0.row=0;offset0.col=1; /右offset1.row=1;offset1.col=0; /下offset2.row=0;offset2.col=-1;/左offset3.row=-1;offset3.col=0;/上printf("n开始搜索路径.n");if(start.row = end.row)&a

15、mp;&(start.col = end.col)path_len = 0;return;while(1)for(i=0;i<num_of_nbrs;i+)nbr.row=here.row+offseti.row;nbr.col=here.col+offseti.col;if(anbr.rownbr.col=0)anbr.rownbr.col=ahere.rowhere.col + 1;if(nbr.row = end.row) && (nbr.col = end.col)break;inq(nbr); /nbr入队/是否到达目标位置finishif(nbr.ro

16、w = end.row) && (nbr.col = end.col)break;/或节点队列是否为空if(team_l=NULL) printf("n没有结果!n");return ;here=outq();path_len=aend.rowend.col;here=end;for(j=path_len-1;j>=0;j-)pathj = here;for(i = 0;i < num_of_nbrs;i+)nbr.row = here.row + offseti.row;nbr.col = here.col + offseti.col;if(a

17、nbr.rownbr.col = j) /+ 2)break;here=nbr;return;void out_path()int i;printf("n路径为:n");printf("(%d,%d) ",start.row,start.col);for(i=0;i<path_len;i+)printf("(%d,%d) ",pathi.row,pathi.col);printf("n");return;void main()input_data();output();find_path();out_path

18、();output();运行结果与分析：根据运行的结果我们看到，首先要给布线区域加一道“围墙”，从开始点进行标记。直达到达结束点。并且可以看到a到b的路径不是唯一的，及最优解不是唯一的。2 动态规划解决最长公共子序列问题2.1 问题重述若给定序列=,，则另一序列=,，是的子序列是指存在一个严格递增下标序列,使得对于所有j=1,2,k有：=。例如，序列=B，C，D，B是序列=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。请使用C语言编程，设计一个有效的算法解决下述问题：给定2个

19、序列X=,，和Y=,，找出X和Y的最长公共子序列。2.2问题分析设序列X=, ,和Y=, ,的最长公共子序列为=,，则(1)若，则，且是和的最长公共子序列。(2)若且，则Z是和Y的最长公共子序列。(3)若且，则Z是X和的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。2.3算法分析与设计算法分析：动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分

20、治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中，这就是动态规划法的基本思路。算法设计：由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中，=, ,=, ,。当i=0或j=0时，空序列是和的最长公共子序列。故此时

21、Cij=0。程序的设计思路是：调用函数void Initialize（），输入两个字符串，对两个串的存储数组b，c进行动态分配。调用函数void LCSLength（int m,int n,string x,string y,int*c,int*b），将长度较小的字符串作为第一参数，将长度较大的字符串作为第二个参数。调用函数void LCS（inti，int j,string x,int*b）构造最长公共子序列调用函数。调用函数ReadCommand进行系统操作屏幕指示，然后利用函数void Interpret（char&cmd）对函数进行总体操作，最后得出最长公共子序列。2.4算法实

22、现与结果代码如下：#include<iostream>#include<string>using namespace std;string x,y;/x,y用来存放字符序列int *c,*b,m,n;/*m，n分别存储字符串x,y的长度,数组cij存储Xi和Yj得最长公共子序列的长度，bij记录cij的值是有哪一个子问题的解得到的*/void LCSLength(int m,int n,string x,string y,int *c,int*b);void LCS(int i,int j,string x,int *b);void Initialize();/对数组b

23、,c动态分配空间以及对其进行初始化void ReadCommand(char &cmd);void Interpret(char &cmd);void Realese();/释放指针void Display();int main()char cmd;doReadCommand(cmd);Interpret(cmd);while(cmd!='q'&&cmd!='Q');return 0;void ReadCommand(char &cmd)system("cls"); /清屏cout<<&qu

24、ot;n-n"cout<<"ntttt操作提示"cout<<"n-n"cout<<"tquit-q/Q tt continue-c/Cn"docout<<"nnt请选择操作："cin>>cmd;cout<<"n-n"while(cmd!='c'&&cmd!='C'&&cmd!='q'&&cmd!='Q');void Initialize()cout<<"分别输入两个字符串（每个字符串以回车结束）n"cin>>x;cin>>y;m=x.length();n=y.length();c=new int*m+1;b=new int*m+1;for(int i=0;i<=m;i+)ci=new intn+1;bi=new intn+1;void Realese()/释放指针boardfor(int i=0;i