算法设计与分析实验报告
目录
实验一 分治法 ………………………………………………………………………… 2
1.1 实验要求 ……………………………………………………………………… 2
1.2 实验内容 ……………………………………………………………………… 2
1.3 核心算法 ……………………………………………………………………… 2
1.4 程序代码 ……………………………………………………………………… 4
1.5 实验结果 ……………………………………………………………………… 8
实验二 贪心法 ……………………………………………………………………… 10
2.1 实验要求 …………………………………………………………………… 10
2.2 实验内容 …………………………………………………………………… 10
2.3 核心算法 …………………………………………………………………… 10
2.4 程序代码 …………………………………………………………………… 12
2.5 实验结果 …………………………………………………………………… 18
实验三 动态规划 ………………………………………………………………… 20
3.1 实验要求 …………………………………………………………………… 20
3.2 实验内容 …………………………………………………………………… 20
3.3 核心算法 …………………………………………………………………… 20
3.4 程序代码 …………………………………………………………………… 21
3.5 实验结果 …………………………………………………………………… 24
实验四 深度优先搜索 …………………………………………………………… 26
4.1 实验要求 …………………………………………………………………… 26
4.2 实验内容 …………………………………………………………………… 26
4.3 核心算法 …………………………………………………………………… 26
4.4 程序代码 …………………………………………………………………… 27
4.5 实验结果 …………………………………………………………………… 28
实验五 回溯法 ……………………………………………………………………… 30
5.1 实验要求 …………………………………………………………………… 30
5.2 实验内容 …………………………………………………………………… 30
5.3 核心算法 …………………………………………………………………… 30
5.4 程序代码 …………………………………………………………………… 31
5.5 实验结果 …………………………………………………………………… 33
实验一 分治法
一.实验要求
1. 了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时，
如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1<k≤n，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那末，对于这类问题分治法是十分有效的。
2. 掌握分治法的一般控制流程。
DanC(p,q)
global n，A[1:n]; integer m,p,q; // 1£p£q£n
if Small(p,q) then return G(p,q);
else m=Divide(p,q); // p£m<q
return Combine(DanC(p,m),DanC(m+1,q));
endif
end DanC
3．实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。
二.实验内容
1. 编程实现归并排序算法和快速排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。
2. 输入10组相同的数据，验证排序结果和完成排序的比较次数。
3. 与复杂性函数所计算的比较次数比较。
4. 用表格列出比较结果。
5. 给出文字分析。
三.程序算法
1. 归并排序算法
procedure MERGESORT(low，high)
//A(low；high)是一个全程数组，它含
有high-low+1≥0个待排序的元素//
integer low，high；
if low<high；
then mid← ， //求这个集合的分割点//
call MERGESORT(low，mid) //将一个子集合排序//
call MERGESORT(mid+1，high) //将另一个子集合排序
call MERGE(low，mid，high) //归并两个已排序的子集合//
endif
end MERGESORT
归并两个已排序的集合
procedure MERGE(low，mid，high)
//A(low：high)是一个全程数组//
//辅助数组B(low；high)//
integer h，i，j，k；
h←low；i←low；j←mid+1；
while h≤mid and j≤high do //当两个集合都没取尽时//
if A(h)≤A(j) then B(i) ←A(h)；h←h+1
else B(i) ←A(j)；j←j+1
endif
i←i+1
repeat
if h>mid then
for k←j to high do //处理剩余的元素//
B(i) ←A(k)；i←i+1
repeat
else for k←h to mid do
B(i) ←A(k)；i←i+1
repeat
endif
将已归并的集合复制到A
end MERGE
2. 快速排序算法
QuickSort(p,q)
//将数组A[1:n]中的元素
A[p], A[p+1], ¼ , A[q]按不降次序排列，
并假定A[n+1]是一个确定的、且大于
A[1:n]中所有的数。//
int p,q; global n, A[1:n];
if p<q then
j=Partition(p, q+1); // 划分后j成为划分元素的位置
QuickSort(p,j-1);
QuickSort(j+1,q);
endif
end QuickSort
procedure PARTITION(m，p)
//退出过程时，p带着划分元素所在的下标位置。//
integer m，p，i；global A(m：p-1)
v←A(m)；i←m //A(m)是划分元素//
loop
loop i←i+1 until A(i)≥v repeat //i由左向右移//
loop p←p-1 until A(p)≤v repeat //p由右向左移//
if i<p
then call INTERCHANGE(A(i)，A(p)) //A(i)和A(p)换位//
else exit
endif
repeat
A(m) ←A(p)；A(p) ←v //划分元素在位置p//
End PARTITION
四.程序代码
1. 归并排序
#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<time.h>
#define M 11
typedef int KeyType;
typedef int ElemType;
struct rec{
KeyType key;
ElemType data;
};
typedef rec sqlist[M];
class guibing{
public:
guibing(sqlist b)
{
for(int i=0;i<M;i++)
r[i]=b[i];
}
void output(sqlist r,int n)
{
for(int i=0;i<n;i++)
cout<<setw(4)<<r[i].key;
cout<<endl;
}
void xuanze(sqlist b,int m,int n)
{
int i,j,k;
for(i=m;i<n-1;i++)
{
k=i;
for(j=i;j<n;j++)
if(b[k].key>b[j].key) k=j;
if(k!=i)
{
rec temp=b[k];
b[k]=b[i];
b[i]=temp;
}
}
}
void merge(int l,int m,int h,sqlist r2)
{
xuanze(r,l,m);
xuanze(r,m,h);
output(r,M);
int i,j,k;
k=i=l;
for(j=m;i<m&&j<h;k++)
{
if(r[i].key<=r[j].key)
{
r2[k]=r[i];
i++;
}
else
{
r2[k]=r[j];
j++;
}
output(r2,M);
}
while(j<h)
{
r2[k]=r[j];
j++;
k++;
}
while(i<=m)
{
r2[k]=r[i];
i++;
k++;
}
output(r2,M);
}
private:
sqlist r;
};
void main()
{
cout<<"guibingfa1运行结果:\n";
sqlist a,b;
int i,j=0,k=M/2,n=M;
srand(time(0));
for(i=0;i<M;i++)
{
a[i].key=rand()%80;b[i].key=0;
}
guibing gx(a);
cout<<"排序前数组:\n";
gx.output(a,M);
cout<<"数组排序过程演示:\n";
gx.merge(j,k,n,b);
cout<<"排序后数组:\n";
gx.output(b,M);
cin.get();
}
2. 快速排序
#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<time.h>
#define MAXI 10
typedef int KeyType;
typedef int ElemType;
struct rec{
KeyType key;
ElemType data;
};
typedef rec sqlist[MAXI];
class kuaisu
{
public:
kuaisu(sqlist a,int m):n(m)
{
for(int i=0;i<n;i++) b[i]=a[i];
}
void quicksort(int s,int t)
{
int i;
if(s<t){
i=part(s,t);
quicksort(s,i-1);
quicksort(i+1,t);
}
else return;
}
int part(int s,int t)
{
int i,j;
rec p;
i=s;j=t;p=b[s];
while(i<j)
{
while(i<j&&b[j].key>=p.key)j--;
b[i]=b[j];
while(i<j&&b[i].key<=p.key)i++;
b[j]=b[i];
}
b[i]=p;
output();
return i;
}
void output()
{
for(int i=0;i<n;i++)
cout<<setw(4)<<b[i].key;
cout<<endl;
}
private:
sqlist b;
int n;
};
void main()
{
cout<<"kuaisu1.cpp运行结果:\n";
sqlist a1;
int i,n=MAXI,low=0,high=9;
srand(time(0));
for(i=0;i<n;i++)
a1[i].key=rand()%80;
kuaisu px(a1,n);
cout<<"数组排序过程演示:\n";
px.quicksort(low,high);
cout<<"排序后数组:\n";
px.output();
cin.get();
}
五.实验结果
1. 归并排序
2. 快速排序
实验二 贪心法
一.实验要求
1. 优化问题
有n个输入，而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组
成，而把满足约束条件的子集称为该问题的可行解。可行解一般来说是不唯一的。那些使目标函数取极值(极大或极小)的可行解，称为最优解。
2. 贪心法求优化问题
算法思想：在贪心算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪心决策的依据称为贪心准则（greedy criterion）。
3. 一般方法
1）根据题意，选取一种量度标准。
2）按这种量度标准对这n个输入排序
3）依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。
procedure GREEDY(A，n) /*贪心法一般控制流程*/
//A(1：n)包含n个输入//
solutions←φ //将解向量solution初始化为空／
for i←1 to n do
x←SELECT(A)
if FEASIBLE(solution，x)
then solutions←UNION(solution，x)
endif
repeat
return(solution)
end GREEDY
4. 实现典型的贪心算法的编程与上机实验，验证算法的时间复杂性函数。
二.实验内容
1. 编程实现背包问题贪心算法和最小生成树prim算法。通过具体算法理解如何通过局部最优实现全局最优，并验证算法的时间复杂性。
2. 输入5个的图的邻接矩阵，程序加入统计prim算法访问图的节点数和边数的语句。
3. 将统计数与复杂性函数所计算的比较次数比较，用表格列出比较结果，给出文字分析。
三.程序算法
1. 背包问题的贪心算法
procedure KNAPSACK(P，W，M，X，n)
//P(1：n)和W(1；n)分别含有按
P(i)/W(i)≥P(i+1)/W(i+1)排序的n件物品的效益值
和重量。M是背包的容量大小，而x(1：n)是解向量
real P(1：n)，W(1：n)，X(1：n)，M，cu；
integer i，n；
X←0 //将解向量初始化为零
cu←M //cu是背包剩余容量
for i←1 to n do
if W(i)>cu then exit endif
X(i) ←1
cu←cu-W(i)
repeat
if i≤n then X(i) ←cu/ W(i)
endif
end GREEDY-KNAPSACK
procedure prim(G,)
status←“unseen” // T为空
status[1]←“tree node” // 将1放入T
for each edge(1,w) do
status[w]←“fringe” // 找到T的邻接点
dad[w] ←1; //w通过1与T建立联系
dist[w] ←weight(1,w) //w到T的距离
repeat
while status[t]≠ “tree node” do
pick a fringe u with min dist[w] // 选取到T最近的节点
status[u]←“tree node”
for each edge(u,w) do
修改w和T的关系
repeat
repeat
2. Prim算法
PrimMST(G，T，r){
//求图G的以r为根的MST，结果放在T=(U，TE)中
InitCandidateSet(…)；//初始化：设置初始的轻边候选集，并置T=({r}，￠)
for(k=0；k<n-1；k++){ //求T的n-1条树边
(u，v)=SelectLiShtEdge(…)；//选取轻边(u，v)；
T←T∪{(u，v)}；//扩充T，即(u，v)涂红加入TE，蓝点v并人红点集U
ModifyCandidateSet(…)； //根据新红点v调整候选轻边集
}
}
四.程序代码
1. 背包问题贪心算法
#include <iostream.h>
struct goodinfo
{
float p; //物品效益
float w; //物品重量
float X; //物品该放的数量
int flag; //物品编号
};//物品信息结构体
void Insertionsort(goodinfo goods[],int n)
{
int j,i;
for(j=2;j<=n;j++)
{
goods[0]=goods[j];
i=j-1;
while (goods[0].p>goods[i].p)
{
goods[i+1]=goods[i];
i--;
}
goods[i+1]=goods[0];
}
}//按物品效益，重量比值做升序排列
void bag(goodinfo goods[],float M,int n)
{
float cu;
int i,j;
for(i=1;i<=n;i++)
goods[i].X=0;
cu=M; //背包剩余容量
for(i=1;i<n;i++)
{
if(goods[i].w>cu)//当该物品重量大与剩余容量跳出
break;
goods[i].X=1;
cu=cu-goods[i].w;//确定背包新的剩余容量
}
if(i<=n)
goods[i].X=cu/goods[i].w;//该物品所要放的量
for(j=2;j<=n;j++)
{
goods[0]=goods[j];
i=j-1;
while (goods[0].flag<goods[i].flag)
{
goods[i+1]=goods[i];
i--;
}
goods[i+1]=goods[0];
}
cout<<"最优解为:"<<endl;
for(i=1;i<=n;i++)
{
cout<<"第"<<i<<"件物品要放:";
cout<<goods[i].X<<endl;
}
}
void main()
{
cout<<"|--------运用贪心法解背包问题---------|"<<endl;
cout<<"|-------------------------------------|"<<endl;
int j;
int n;
float M;
goodinfo *goods;//定义一个指针
while(j)
{
cout<<"请输入物品的总数量：";
cin>>n;
goods=new struct goodinfo [n+1];//
cout<<"请输入背包的最大容量：";
cin>>M;
cout<<endl;
int i;
for(i=1;i<=n;i++)
{ goods[i].flag=i;
cout<<"请输入第"<<i<<"件物品的重量:";
cin>>goods[i].w;
cout<<"请输入第"<<i<<"件物品的效益:";
cin>>goods[i].p;
goods[i].p=goods[i].p/goods[i].w;//得出物品的效益，重量比
cout<<endl;
}
Insertionsort(goods,n);
bag(goods,M,n);
cout<<"press <1> to run agian"<<endl;
cout<<"press <0> to exit"<<endl;
cin>>j;
}
}
2. Prim算法
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
typedef int VRType;
typedef int InfoType;
typedef char VerTexType;
typedef struct ArcCell
{
VRType adj;
InfoType *info;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VerTexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum, arcnum;
}MGraph;
typedef struct
{
VerTexType adjvex;
VRType lowcost;
}closedge[MAX_VERTEX_NUM];
void CreateGraph(MGraph &G);
void MiniSpanTree_PRIM(MGraph G, VerTexType u);
int LocateVex(MGraph G, VerTexType u);
int minimum(closedge close);
void main( void )
{
int i, j;
MGraph G;
CreateGraph(G);
for(i = 0; i < G.vexnum; i++)
{
for(j = 0; j < G.vexnum; j++)
{
cout<<G.arcs[i][j].adj;
cout<<" ";
}
cout<<endl;
}
MiniSpanTree_PRIM(G, 'a');
}
void CreateGraph(MGraph &G)
{
int weigh;
int i, j = 0, k = 0;
char hand, tide;
cout<<"input the number for vexnum and arcnum:";
cin>>G.vexnum>>G.arcnum;
for(i = 0; i < G.vexnum; i++)
{
for(j = 0; j < G.vexnum; j++)
G.arcs[i][j].adj = 88;
}
cout<<endl;
cout<<"input"<<G.vexnum<<"char for vexs:";
for(i=0; i < G.vexnum; i++)
cin>>G.vexs[i];
cout<<endl;
cout<<"input"<<G.arcnum<<"arc(char,char,weigh):"<<endl;
j = 0;
k = 0;
for(i=0; i < G.arcnum; i++)
{
cout<<i<<":";
cin>>hand;
cin>>tide;
cin>>weigh;
while (hand != G.vexs[j])
j++;
while (tide != G.vexs[k])
k++;
G.arcs[j][k].adj = weigh;
G.arcs[k][j].adj = weigh;
j = 0;
k = 0;
cout<<endl;
}
}
void MiniSpanTree_PRIM(MGraph G,VerTexType u)
{
int i, j, k = 0;
closedge close;
k = LocateVex ( G, u );
for ( j = 0; j < G.vexnum; j++ )
{
if (j != k)
{
close[j].adjvex = G.vexs[k];
close[j].lowcost = G.arcs[k][j].adj;
}
}
close[j].lowcost = 88;
close[j].adjvex = '\0';
close[k].lowcost = 0;
close[k].adjvex = u;
for (i = 1; i < G.vexnum; i++)
{
k = minimum(close);
cout<<close[k].adjvex;
cout<<"---->";
cout<<G.vexs[k]<<" ";
cout<<close[k].lowcost<<endl;
close[k].lowcost = 0;
for (j=0; j<G.vexnum; j++)
{
if (G.arcs[k][j].adj < close[j].lowcost)
{
close[j].adjvex = G.vexs[k];
close[j].lowcost = G.arcs[k][j].adj;
}
}
}
}
int LocateVex(MGraph G, VerTexType u)
{
int k = 0;
while(G.vexs[k++] == u)
return k-1;
return 0;
}
int minimum(closedge close)
{
int j1=0, client = 88, j2;
while(close[j1].adjvex != '\0')
{
if (client > close[j1].lowcost && close[j1].lowcost != 0)
{
client = close[j1].lowcost;
j2 = j1;
}
j1++;
}
return j2;
}
五.实验结果
1. 背包问题贪心算法
2. Prim算法
实验三 动态规划
一.实验要求
- 理解最优子结构的问题。
有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状态，与该阶段之前的过程如何达到这种状态的方式无关。这类问题的解决是多阶段的决策过程。在50年代，贝尔曼（Richard Bellman）等人提出了解决这类问题的“最优化原理”，从而创建了最优化问题的一种新的算法设计方法－动态规划。
对于一个多阶段过程问题，是否可以分段实现最优决策，依赖于该问题是否有最优子结构性质，能否采用动态规划的方法，还要看该问题的子问题是否具有重叠性质。
最优子结构性质：原问题的最优解包含了其子问题的最优解。
子问题重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。
- 理解分段决策Bellman方程。
每一点最优都是上一点最优加上这段长度。即当前最优只与上一步有关。
us 初始值，uj第j段的最优值。
- 一般方法
1） 找出最优解的性质，并刻画其结构特征；
2） 递归地定义最优值（写出动态规划方程）；
3） 以自底向上的方式计算出最优值；
4） 根据计算最优值时得到的信息，构造一个最优解。
步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。
二.实验内容
- 编程实现多段图的最短路径问题的动态规划算法。
- 图的数据结构采用邻接表。
- 要求用文件装入5个多段图数据，编写从文件到邻接表的函数。
- 验证算法的时间复杂性。
三.核心算法
多段图算法
procedure FGRAPH(E，k，n，P)
//输入是按段的顺序给结点编号的，有n个结点
的k段图。E是边集，c(i，j)是边<i,j>的成本。
P(1：k)是最小成本路径。//
real COST(n)，integerD(n一1)，P(k)，r，j，k，n
COST(n)← 0
for j←n-1to 1by－1do //计算COST(j)//
设r是一个这样的结点，(j，r)ÎE且使c(j，r)+COST(r)取最小值
COST(j)←c(j，r)+COST(r)
D(j)←r
repeat //向前对j-1进行决策//
P(1)←1；P(k)←n；
for j←2 to k-1 do //找路径上的第j个节点//
P(j)←D ( P(j-1) )
repeat
end FGRAPH
四.程序代码
多段图问题
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define MAX_VERTEX_NUM 50
typedef struct ArcNode
{
int adjvex; //该弧所指向的顶点的位置
int value; //该结点与邻接结点间的代价
struct ArcNode *nextarc; //指向下一条弧的指针
}ArcNode, *node;
typedef struct VNode
{
int data; //顶点信息
ArcNode *firstArc; //指向第一条依附该顶点的弧的指针
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct Graph
{
AdjList vertices;
int vexnum,arcnum; //图的当前顶点数和弧数
}*ALGraph;
int build_adList(ALGraph G,int n,int a)
{ //建立邻接表
int v, m, i, t, h;
node p, q;
if(n < 0) return printf("ERROR");
G->vexnum = n; //图的顶点数
if(a < 0) return printf("ERROR");
G->arcnum = a; //图的弧数
for(m = 0; m < n; m++)
{
G->vertices[m].data = m;
G->vertices[m].firstArc = NULL;
}
for(m = 1; m <= a; m++)
{
i = 1;
printf("输入第%d条弧:", m);
scanf("%d,%d,%d",&t,&h,&v);
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = h;
p->value = v;
p->nextarc = NULL;
while(G->vertices[i].data != t) i++; //转到下一个结点
if(!G->vertices[i].firstArc) //终点
G->vertices[i].firstArc = p;
else
{ //若当前结点有后继节点则后移
for(q = G->vertices[i].firstArc; q->nextarc; q = q->nextarc);
q->nextarc = p; //新开辟结点
}
}
return v;
}
void print_Graph(ALGraph G)
{ //打印邻接表
ArcNode *p=(ArcNode *)malloc(sizeof(ArcNode));
int i;
for(i = 1; i < G->vexnum; i++)
{
p = G->vertices[i].firstArc;
printf("[%d]",i);
while(p)
{
printf("->%d,%d",p->adjvex,p->value);//第i个结点的邻接结点信息
p = p->nextarc;
}
printf("\n");
}
}
void fgraph(ALGraph G ,int k,int n)
{ //多段图ALGraph G，n为结点数，k为图的段数
//输入是按段的顺序给结点编号
int cost[100];
int d[100];
int path[100];
int j, r, i, min, w, value;
node p;
cost[n] = 0;
for(j = n - 1; j >= 1; j--) //向前处理结点
{
p = G->vertices[j].firstArc;
min = p->value+cost[p->adjvex]; //初始化路径最小代价
r = p->adjvex;
value = p->value;
while(p != NULL)
{ //r是一个的这样的结点，权值c(j,r)+cost[r]取最小值
if((p->value + cost[p->adjvex]) < min)
{
min = p->value + cost[p->adjvex]; //p->value=c(j,r)
r = p->adjvex;
value = p->value;
}
p = p->nextarc;
}
cost[j] = value + cost[r]; //当前节点的代价值
d[j] = r; //决策阶段，各结点到终点最小代价路径上前方顶点的编号
}
path[1] = 1; path[k] = n;
for(i = 2; i <= k - 1; i++) //找出最小代价路径上的结点
path[i] = d[path[i - 1]];
printf("最小成本为:%d\n",cost[1]);
printf("最小成本路径为: ");
for(w = 1; w <= k; w++)
printf("%d->", path[w]);
}
void main()
{
ALGraph g;
int n,a,k;
g = (ALGraph)malloc(sizeof(ALGraph));
printf("请输入多段图节点数目:");
scanf("%d", &n);
printf("请输入多段图边的数目:");
scanf("%d", &a);
printf("请输入多段图的段数:");
scanf("%d", &k);
printf("输入多段图的弧的信息（弧头，弧尾，权值）\n");
build_adList(g, n, a);
printf("多段图的邻接表为:\n");
print_Graph(g);
fgraph(g, k, n);
getch();
}
五.实验结果
多段图问题
实验四 深度优先搜索
一.实验要求
1． 理解深度优先搜索策略：
深度优先搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的顶点v，如果边(v,w)是还未探测的边，则沿(v,w)继续搜索下去。当所有的边(v,w)都己被探寻过，搜索将回溯到发现结点v的顶点。这一过程一直进行到回到源点为止。如果还存在未被发现的顶点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。
2． 理解深度优先搜索过程中顶点的三种状态：
还未到达的顶点，当前路径上经过的顶点，深度优先在搜索过程中也为结点着色以表示结点的状态。每个顶点开始均为白色，搜索中被发现时置为灰色，当其邻接表被完全检索之后又被置成黑色。
二.实验内容
1． 编程实现深度优先搜索算法。
2． 修改算法使之可以找出图的所有树。
3． 修改算法使之可以判断图是否为一棵树。
4． 修改算法使之可以判断图是否存在一个环。
三.核心算法
procedure DFS(G);
for 每个顶点u∈G do
color[u]← White;
repeat
for每个顶点u∈G do
if color[u]=White
then DFS_Visit(G,u);
end;
procedure DFS_Visit(u);
color[u]←Gray;
for (u,w)∈E do //探寻边(u,w)
if color[w]=White
then DFS_Visit(w);
repeat
color[u]←Black; //完成后置u为黑色
end;
四.程序代码
#include<iostream.h>
#define MAX 50 //能够处理的最多顶点数
char color[MAX]; //保存每个点的颜色标记
int n,A[MAX][MAX]; //顶点数和矩阵
int loop=0; //标记环并记录其个数
int tree=0; //标记树并记录其个数
void DFS(int i)
{
int k;
color[i]='G'; //已访问顶点记为灰色
for(k=1;k<=n;k++)
{
if(A[i][k]==1)
{
if(color[k]=='G'||color[k]=='B') //当该点的邻接点中有已被访问的点时存在环
loop++;
if(color[k]=='W')
DFS(k); //访问邻接点中一个没有被访问的点
}
}
color[i]='B'; //当点为死结点时记为黑色
}
void main()
{
int i,j,k,m;
cout<<"请输入总顶点数：\n";
cin>>n;
cout<<"请输入总边数：\n";
cin>>m;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
A[i][j]=0; //将矩阵初始化为0
color[i]='W'; //所有顶点颜色初始化为白色
}
}
for(k=1;k<=m;k++)
{
cout<<"请输入其始点:"; cin>>i;
cout<<"请输入指向的点:"; cin>>j;
A[i][j]=1; //有边的赋值为1
}
for(i=1;i<=n;i++)
{
if(color[i]=='W')
DFS(i);
}
for(i=1;i<=n;i++)
for(j=1;j<n;j++)
{
if(!(A[i][j]&&A[j][i]))
tree++;
}
if(loop==0)
{
cout<<"该图中无环!"<<endl;
if(m==n-1)
cout<<"该图为一棵树!"<<endl;
}
else
{
cout<<"该图中共有"<<loop<<"个环!"<<endl;
cout<<"该图不是一棵树!"<<endl;
}
}
五.实验结果
实验五 回溯法
一.实验要求
1. 理解可用回溯法求解的问题
问题P通常要能表达为对已知的、由n元组(x1，…，xn)组成的状态空间E={(x1，…，xn)| xiÎSi,i=1,2,…n}，给定关于n元组中的分量的一个约束集D，求满足D的全部约束条件的所有n元组。 Si 是 xi 的定义域且Si 是有穷集，称E中满足D 的全部约束条件的所有n元组为问题P的一个解。
2. 理解回溯法的基本思想
回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。
算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。
回溯法的形式描述：
procedure BACAKTRACE(n)
k =1 ;
while (k>0) do
if Tk (x1，x2，…， x k-1)的值还未取遍 then
{xk←Tk (x1，x2，…， x k-1)中未取遍过的值；
if Bk (x1，x2，…， x k) then
{(x1，x2，…， x k)被激活；
if k ==n then 输出(x1，x2，…， x n)；
else k =k+1； // 深度扩展搜索
}
}
else k = k -1 // 试探完了所有的x k，回溯
end BACAKTRACE
二.实验内容
1. 编程实现n皇后算法。
2. 用图形输出中间过程。
3. 在程序中添加统计扩展节点数，估计算法的复杂性。
三.核心算法
n皇后算法
procedure NQUEENS(n)
X(1)←0；k←1 //k是当前行；X(k)是当前列//
While k>0 do //对所有的行执行以下语句//
{ X(k)←X(k)+1 //移到下一列//
While X(k)≤n and not PLACE(k) do
X(k)←X(k)十l
if X(k)≤n //找到一个位置//
then if k=n //是一个完整的解吗//
then print(X) //是，打印这个数组//
else {k←k+1；X(k)←0；}
else k←k－1 //回溯//
}
end NQUEENS
四.程序代码
#include <stdio.h>
#include <math.h>
/*检查可不可以放置一个新的皇后*/
bool place(int k, int *X)
{
int i;
i = 1;
while(i < k)
{
if((X[i] == X[k])||(abs(X[i] - X[k]) == abs(i - k))) //两个皇后不在同行/列/对角线
return false;
i++;
}
return true;
}
void Nqueens(int n, int *X)
{//k表示所处理的是第k行的皇后，X[k]表示第k行皇后的列位置
int k;
X[1] = 0;
k = 1;
while(k > 0)
{
X[k] = X[k] + 1; //从当前列加1的位置开始搜索
while((X[k] <= n)&&(!place(k, X))) //当前列位置是否满足条件
X[k] = X[k] + 1; //不满足条件,继续搜索下一列位置
if(X[k] <= n) //存在满足条件的列
{
if(k == n) //是最后一个皇后,完成搜索
{
for(int i = 1;i <= n;i++) //输出各行皇后的列位置
printf("%d ", X[i]);
printf("\n");
}
else
{
k = k + 1; //不是最后一个,则处理下一个皇后
X[k] = 0; //下一列的皇后所在列位置置0
}
}
else
{//已判断完n列，均未能满足条件
X[k] = 0; //当前行复位为0
k = k - 1; //回溯到前一列
}
}
}
void main()
{
int n, i;
int *X;
printf("|--------------THE N QUEENS PROBLEM--------------|\n");
printf("|------ edited by Jill Chih ------|\n");
printf("|------------------------------------------------|\n\n");
while(i)
{
printf("Please input the sum of Queens:\n");
scanf("%d", &n);
X = new int[n];
printf("The solutions are:\n");
Nqueens(n, X);
printf("Press <1> to run again\n");
printf("Press <0> to exit\n");
scanf("%d", &i);
}
}
五.实验结果
