文档介绍：算法实验报告
姓名:邓诗文
班级:CS0906
学号:U200915052
日期:
实验目的
背包问题:研究应用递归思想,背包算法。应用数据结构基础知识进行实际问题求解与分析。
最优二分检索树:通过编程实现最优二分检索树的构造,熟悉二分检索的思想从而掌握算法。
多段图:通过编程实现多段图的最短路径长度,了解多段图的向前处理和向后处理,熟悉算法。
单源点最短路径:运用Dijkstra 算法实现单源点最短路径,熟悉算法。
实验分析
单源点最短路径:若按长度递增的次序生成从源点s到其它顶点的最短路径,则当前正在生成的最短路径上除终点以外,其余顶点的最短路径均已生成(将源点的最短路径看作是已生成的源点到其自身的长度为0的路径)。
多段图:对于向前处理法,汇点的COST=0,求前一段的每一个结点的COST,对于此段的结点,COST为下段各结点中各个结点的COST(下段结点)+W(此结点到下结点权重)的最小值,结果保存在数组中。依次求至源点的COST,即为最优解。向后处理法则是反过来求。
最优二分检索树:构造一棵最优二分检索树不用算法,,大于他的为左子树,小于他的为右子树,依此类推。
背包问题: 令n个物品的重量和价值分别存储于数组w[]和v[]中,(x0,x1,……xn-1)表示物品选择的解,其中xi=0表示第i个物品没有选取,而xi=1则表示第i个物品被选取。只要搜索所有的n元组,就可以得到问题的解。
每个分量取值为0或1的n元组的个数共为2^n个,而每个n元组其实对应了一个长度为n的二进制数,且这些二进制数的取值范围为0~2^n-,如果把0~2^-1分别转化为相应的二进制数,则可以得到所需要的2^n个n元组。
实验源代码及结果
#include <>
#define N 5
#define MAX 100000
#define SWAP(a,b) do{int tmp;tmp=a;a=b;b=tmp;}while(0)
void fun(const int quan[][N],const int shunxu[N],int jieguo[N])//Dijkstra算法主体
{
int i,v,j;
for(i=0;i<N;i++)
{
v=shunxu[i];
for(j=0;j<N;j++)
if(jieguo[v]+quan[v][j]<jieguo[j])
jieguo[j]=jieguo[v]+quan[v][j];
}
}
main()
{
int quan[N][N]={{0,10,3,20,MAX},//邻接矩阵
{10,0,2,5,MAX},
{3,2,0,MAX,15},
{20,5,MAX,0,11},
{MAX,MAX,15,11,0}};
int n,shunxu[N],i,j,jieguo[N];
printf("输入查找点序号:0~N:");
scanf("%d",&n);//起点
for(i=0;i<N;i++)
{
shunxu[i]=i;
jieguo[i]=MAX;
}
jieguo[n]=0;
for(i=1;i<N;i++)
for(j=i;(j>0)&&quan[n][j]<quan[n][shunxu[j-1]];j--)//将各结点插入排序
{
SWAP(shunxu[j],shunxu[j-1]);
}
fun(quan,shunxu,jieguo);//调用
printf("目的地是:");//打印
for(i=0;i<N;i++)
printf("%-3d",i);
printf("\n最短路径:");
for(i=0;i<N;i++)
printf("%-3d",jieguo[i]);
}
实验结果如下:
最优二分检索树
#include <>
#include <>
#include <>
#define N 4
void OBST(int P[], int Q[], int R[][N+1], int n)
{
int W[N+1][N+1], C[N+1][N+1];
for(int i=0; i<=N; i++) // 将初值全部置为0
for(int j=0; j<=N; j++)
W[i][j]=C[i][j]=R[i][j]=0;
for(i=0; i<