算法课程设计

1

cout« I i st [0] [num-1 ]; return 0;

1

本课设中list[0] [n-1]代表所用租金最少，n为游艇出租站的个数。 List[i][j]表示从笫i个游艇出租站到第j个游艇出租站的费用(其中i〈j)。 当 list[i] [j]+list[j] [mark] [i] [mark]时，list [i] [mark]= list [i] [j] +list[j] [mark]。则递归方程为

list[0][n-l]=min{list[0][k]+list[k][n~l], list[0][n~l]}

1.4算法实现与结果

程序代码：

#inelude #include using namespace std; int main()

cin»num;

int mark二i+k; vector< vector >list; vectorline; for(i=0;i {

list.push_back(li ne); for(j=0;j<=i;j++)

〃在容器前面添加些0,从而使list[i][j]表示从第

i个出租站到第j个出租站所需的金额

{

接赋值为0,从而使后面的计算更方便

list[i].push_back(O);

〃同时也去除无效的表示，比如list[0][0]直

}

for(j=i+l;j {

cin> >tmp;

list[i].push_back(tmp); 〃从i+1个出租站到第j+1个岀租站所需 金额

} }

for(k=2;k〃从两个出租站开始，逐步计算每儿个出租站之间的

最优解，最终计算num-1个出租站合并的最优解

for(i=0;i for(j=i+l;jif(list[i][j]+list[j][mark]list[O][l]+list[1][2]//例如

{

} } } }

cout«list[0][num-l]; return 0; }

1.5结果描述

运行结果如图1・1所示。

list[i][mark]=list[i][j]+list[j][mark];

图1.1租用游艇问题运行结果

如图1所示，含有3个游艇出租站，从出租站1到出租站2, 3分别需要租 金为5,

15,从出租站2到出租站3需要租金为7,则运用动态规划法求解出从 出租站1到出租站3所需最少租金为12o

二、回溯法解决部落卫队问题

2. 1问题重述

原始部落byteland中的居民们为了争夺有限的资源，经常发生冲突。儿乎 每个居民都是他的仇敌。部落酋长为了组织一支保卫部落的队伍，希望从部落的 居民中选出最多的居民入伍，并保证队伍中任何2个人都不是仇敌。

2.2问题分析

本问题为组织一支队伍保卫部落，并且卫队中任意2人不能有仇敌关系，因 而，实际可考虑在居民中选择一个最大团体问题。

构建一个树状图G,居民为树状图G的顶点，居民间的关系为树状图的边界线。 “1”表示两个居民间没有仇敌关系，“0”表示两个居民间有仇敌关系。这样最 大团问题就成了图G顶点集的子集的选取问题，可用子集树表示问题的解空 间。设当前考察结点位于解空间树的第i层。先考虑顶点到要选入团中的所 有结点都要相连（即无仇敌关系）且任意两个结点都仇敌关系，然后进入左子树 进行深度优先遍历，在进入右子树。

2. 3算法原理及设计

2. 3. 1算法原理

具有限界函数的深度优先的方式系统第搜索问题的解的算法称为回溯法。它 可以系统地搜索某一个问题的所有解或任一解。回溯法是一个既带有系统性乂带 有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策 略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判 断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的 子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先 的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所 有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问 题的一个解就可以结束。它适用于解一些组合数较大的问题。

回溯法搜索解空间树时，通常采用两种策略避免无效搜索，提高回溯法的搜 索效率。其一是用约束函数在扩展结点处剪去不满足约束的子树；其二是用限界 函数剪去得不到最优解的子树。这两类函数统称为剪枝函数。

问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题 的解空间应到少包含问题的一个（最优）解。

运用回溯法解题通常包含以下3个步骤：

（1） 针对所给问题，定义问题的解空间；

（2） 确定易于搜索的解空间结构；

（3）以深度优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜

索。

对于本题来说，回溯法操作步骤如下:

(1) 针对所给问题，定义问题的解空间；确定易于搜索的解空间结构；以深 度

优先方式搜索解空间，并在搜索过程中利用剪枝函数剪去无效的搜索。

(2) 无向图G的最大团问题可以看作是图G的顶点集V的子集选取问题。因 此

可以用子集树表示问题的解空间。设当前扩展节点Z位于解空间树的笫i层。 在进入左子树前，必须确认从顶点i到已入选的顶点集中每一个顶点都有边相连。 在进入右子树之前，必须确认还有足够多的可选择顶点使得算法有可能在右子树 中找到更大的团。

⑶用邻接矩阵表示图G, n为G的居民数，cn存储当前卫队数，bestn存储 最大卫队人数。cn+n-i为进入右子树的上界函数，| cn+n-i2. 3. 2算法设计

M，

void Backtrackfint ijnt a[20][20]) { if(i>n) {

for(int j=l;j<=n;j++) bestx[j]=x[j]; best n=cn; return; } int ok=l; for(i nt j=l;jok=0; break; } if(ok) {

x[i]=l； cn++;

Backtrack(i+l,a); x[i]=O; cn_; }

if(cn+n-i>best n) { x[i]=O;

Backtrack(i+l,a);} } }

用回溯法解决部落卫队问题时，以深度优先方式搜索整个解空间，用完全二 义树表示解空间。剪枝条件为：当前卫队人数+剩余居民人数〈当前最优解；得出 的解用一个n元向量V= (xl, x2,..., xn)来表示。

2. 4算法实现

程序代码：

#include #include

#inelude class clique{

friend maxclique(int a[20][20]Jnt []Jnt); private:

void Backtrack(int i,int a[20][20]); int n,

% //当前解

*bestx, //当前最优解 cn, //当前卫队人数 bestn; //当前最大卫队人数 }；

void clique::Backtrack(int ijnt a[20][20])

for(int j=l;j<=n;j++) bestx[j]=x[j]; bestn=c n; return;

int ok=l;

if(x[j]&&a[i]U]==O)

ok=0; break;

}

讦(ok)

{

x[i]=l； cn++;

Backtrack(i+l,a); x[i]=O; cn_; }

if(cn+n-i>best n) {

x[i]=O； Backtrack(i+l,a); } }

int maxclique(int a[20][20],int v[]Jnt n) {

clique Y; Yx=new int[n+l]; Y.n二n; Y cn=O; Y bestn=O; Y.bestx=v; Y Backtrack(l,a); delete[] Y.x;

return Y.bestn;

int main(void) { int ij,k; int v[2O];

int n,edge; //顶点和边数 int a[2O][2O];

cout<<\"请输入人数:\"； cin»n;

for(i=l;i< 二n ;i++) v[i]=O;

for(i=l;i<=n ;i++) for(j=i;j<=n;j++) a[i]U]=aU][i]=l；

cout<< “请输入这“<<“<<“个人的所有敌对关系”; for(i=l;i<=edge;i++)

cin>> j»k; a[j][k]=a[k]U]=O;

cout«maxclique(a,vr n)vcin> >edge;

cout«v[i]«,

return 0; systemf'pause\"); }

2. 5结果描述

运行结果如图2.1所示。

图2・1部落卫队输岀结果

如图2所示,部落居民人数为7个,存在敌对关系分别为(1,2), (1,4), (2, 3), (2,4), (2,

5), (2,6), (3,5), (3,6),(4,5), (5,6)时，输出最优解空间为 (1,0,1,0,0,0,1),组织卫队人数最大

值为3。

山此可画岀居民人数n=7时的解空间树如图2.2所示。

i=l

=0,best n二0

cn二「best n=0

cn=O,best n=3

i=2

cn二2,best n=0 =l,best n=3 i=4

cn=l,best n=3=1,best n=3=0,best n=3

1 0 1 0 X

+n-i=2,best n=0

=l,best n=3

cn=2,best n=3=l,best n=3

i=5

X 1

0 X 0 +n-icn=l,best n=3 cn=2,best n=3 X

best n=3

=2,best n=0=2

i=6

+n-i1

0 =lzbest n=0

cn+n-i0 =O,best n=3

cn二l,best n=3

i=3

X

1 0

1 0 X =2,best n=0

1 0

X

1 0

i=7

X 1 =3,best n=0

i=8

best n=3

图2. 2解空间树

三、总结

我通过一学期对算法分析与设计的初步学习，了解了一些算法的思想，并运用 到本次算法课程设计中。通过本次课程设讣，使我对动态规划法解决租用游艇问 题和回溯法解决部落卫队问题 的基本过程（设计方法、步骤、思路）有了一定 的了解与认识。在这次课程设计过程中，我认识到只是知道课本上的理论知识是 远远不够的，我们还必须要深入的理解每个算法的思想，再结合实际问题，活用 算法思想，并且能够利用C++语言去编写相关的程序代码，经过不断的修改、调 试，使之能解决相应的问题，最终能解决实际案例。对现阶段的我们来说，动手 能力的培养能力至关重要，而这种动手能力的培养单靠课堂教学是远远不够的, 需要将自己在堂堂上学到的主要中心思想运用于实践中去。而这次的课程设计正 好给了我们一个机会让我们自己动手，在这过程中找出自身能力与实际要求的差 距。在这次课设过程中也开拓了我的视野，学到了书本以外的知识，这种提高不 仅仅是算法与设计这门学科，在软件编程上也有很大收获。改变设计与分析算法 的思维方式，也使我知道随意拼凑算法这种习惯的危险。相信自己在以后的学习 中能够充分的运用学校和社会给我们提供的渠道获得更多知识，完善自己。为以 后求职与正式工作做好充分的知识能力准备，从而缩短与社会的差距。

参考文献

⑴王晓东.计算机算法设计与分析（第4版）..电子工业.2012.2 ⑵王晓云、业纲.计算机算法设计、分析与实现..科学.2012

⑶谭浩强.C语言程序设计（第3版）..清华大学.2012

⑷玉福.算法设计与分析..清华大学.2009 ⑸严蔚敬.数据结构..清华大学.2009