多项式分治背包问题单元最短路径克鲁斯卡尔多段图.docx

多项式分治背包问题单元最短路径克鲁斯卡尔多段图.docx

《多项式分治背包问题单元最短路径克鲁斯卡尔多段图.docx》由会员分享，可在线阅读，更多相关《多项式分治背包问题单元最短路径克鲁斯卡尔多段图.docx（13页珍藏版）》请在冰点文库上搜索。

多项式分治背包问题单元最短路径克鲁斯卡尔多段图

算法设计与分析大作业

班级：

物联网1401

学号：

姓名：

zk

江南大学物联网工程学院

一、多项式分治

1.1算法简介

分治字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题„„直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

因为多项式的表示是Pn（x）= anxn ＋an-1xn-1＋…＋a1x＋a0 

任意大整数都可以看作是一多项式（其中X=10，an是第n+1位上的数字，个位用a0表示）。

如：

9876=6+7*101+8*102+9*103  

所以大整数相乘可以用多项式乘积的分治算法实现，实际上大整数相乘就是多项式乘积的一个特例。

 把一个多项式分为两个 

P （x）= P0（x）+ P1（x）xn/2    q（x）=q0（x）+q1（x）xn/2   

P（x）*q（x）=P0（x）*q0（x）+P1（x）*P1（x）*xn+（（P0（x）+ P1（x））*（ q0（x）+q1（x））- P0 * q0 – P1* q1）* xn/2 

令：

R0= P0（x）*q0（x）    R1= P1（x）*q1（x）  R2= P0（x）+ P1（x））*（ q0（x）+q1（x））- P0 * q0 – P1* q1 

于是上式可化简为P（x）*q（x）= R0 +（R2- R0- R1）* xn/2+ R1*xn 

由于多项式乘法时间远多于加法时间，所以多项式乘积分治算法对比较大的n将有很大的改进。

1.2调试过程

①在调试过程中poly_product（）函数出错，单步调试发现

图1poly_product（）错误部分

第16,17行出错，多项式阶数相同系数相加，所以讲r2+k改为r2或17,18行r3改为r3+k即可。

②多项式的输入只能是2的倍数。

1.3运行结果

图2多项式分治算法运行结果

二、背包问题

2.1算法简介

背包是基于这样的问题，即有N件物品和一个容量为V的背包，第i件物品的重量是w[i]，价值是v[i]。

求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

问题的约束方程为：

根据约束方程，最好是选择即使目标函数的值增加最快，又使背包载重消耗较慢的物体装入背包，即优先选择价值重量比最大的物体装入背包中。

2.2算法复杂度

时间和空间复杂度均为O（N*V），其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O（V）。

2.3调试过程

①在背包问题中首先用到merge_sort（）合并排序算法对物体的价值重量比进项排序，实际运行中发现出错。

单步调试发现在swap（）交换函数中并没有完成交换，由于物体属性为结构体所有采用较麻烦的方法交换。

voidswap（OBJECT&x,OBJECT&y）

{

OBJECTtemp;

temp.p=x.p;

x.p=y.p;

y.p=temp.p;

temp.w=x.w;

x.w=y.w;

y.w=temp.w;

temp.v=x.v;

x.v=y.v;

y.v=temp.v;

}

2.4运行结果

图3背包问题程序运行结果

三、单源最短路径

3.1算法简介

Dijkstra算法思想为：

设G=（V,E）是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径,就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。

在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。

此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

其实Dijkstra算法是一个数学问题，算法是一个贪心算法，未被确定的最短路径处在一个不断更新的过程中，已经确定的最短路径不需更新，每次都是在已经确定的最短路径的基础上获取新的最短路径。

并且最先找到的最短路径越短，最后找到的最短路径越长，也就是说，确定的最短路径是一个递增的趋势。

这里需要明确的一个很重要的问题就是：

下一条最短路径只能有两种情况：

1.集合A=由已经产生的最短路径的终点再扩充一条边得到；

2.B=由源点直接到达目的节点。

3.2调试过程

①又相图邻接表的建立，程序中利用循环嵌套的方式建立每个节点与相邻节点的邻接链表。

思路是：

图4邻接表建立思路

在此之前尝试另一种建立邻接链表的方法：

typedefstructVertexNode{

intdata;

NODE*firstedge;//边表头指针

}VertexNode,AdjList[9];

typedefstructGraphAdjList{

AdjListadjList;

intnumVertexes,numEdges;//图中当前的结点数以及边数

}GraphAdjList;

intCreateDG（GraphAdjList&G）/*邻接表建立有向图*/

{

inti,s,d,l;

NODE*p;

printf（"输入结点数目和边数"）;

scanf_s（"%d%d",&G.numVertexes,&G.numEdges）;//输入结点数目和边数

getchar（）;

for（i=1;i<=G.numVertexes;i++）//输入顶点

{

printf（"输入顶点"）;

scanf_s（"%d",&G.adjList[i].data）;//输入顶点

getchar（）;

G.adjList[i].firstedge=NULL;//首先初始化为NULL

}

for（i=1;i<=G.numEdges;i++）

{

printf（"输入一条边依附的起点序号和终点序号及权值"）;

scanf_s（"%d%d%d",&s,&d,&l）;//输入一条边依附的起点序号和终点序号

getchar（）;

p=（structNODE*）malloc（sizeof（structNODE））;

p->v_num=d;

p->len=l;//这两句代码相当于单链表的插入操作

p->next=G.adjList[s].firstedge;//保存顶点所对应的终点位置

G.adjList[s].firstedge=p;

}

return1;

}

运行即停止工作。

图5运行出错图

单步调试也无法进行，后来就放弃这种方法。

图6调试出错

3.3运行结果

图7有向图

图8单源最短路径程序运行结果

四、克鲁斯卡尔算法

4.1算法简介

（1）构造一个只含n个顶点，边集为空的子图。

若将图中各个顶点看成一棵树的根节点，则它是一个含有n棵树的森林。

（2）从网的边集E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图。

也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之（3）依次类推，直至森林中只有一棵树，也即子图中含有n-1条边为止。

简而言之就是

（1）将图中的所有边都去掉。

（2）将边按权值从小到大的顺序添加到图中，保证添加的过程中不会形成环（3）重复上一步直到连接所有顶点，此时就生成了最小生成树。

这是一种贪心策略。

假设有无向图如下图所示：

图9无向图

边集数组按权值顺序排列如下图：

图10权值顺序排列

按照权值由小到大的顺序连接：

图11连接顺序示意图

4.2算法复杂度

时间复杂度：

O（mlogm），m是边数，空间复杂度：

O

（1）

4.3调试过程

图12程序调试无向图

4.4运行结果

图13克鲁斯卡尔程序运行结果

五、多段图最短路径问题

5.1算法简介

这里先讨论用动态规划法的解法。

考虑多段图的最短路径问题的填表形式。

用一个数组cost[n]作为存储子问题解的表格，cost[i]表示从顶点i到终点n-1的最短路径，数组path[n]存储状态，path[i]表示从顶点i到终点n-1的路径上顶点i的下一个顶点。

则：

cost[i]=min{cij+cost[j]}     （i≤j≤n且顶点j是顶点i的邻接点）         

 path[i]=j                （使cij+cost[j]最小的j）                   

 对多段图的边（u, v），用cuv表示边上的权值，将从源点s到终点t的最短路径记为d（s, t），则从源点0到终点9的最短路径d（0, 9）由下式确定：

d（0, 9）=min{c01+d（1, 9）, c02+d（2, 9）, c03+d（3, 9）}，这是最后一个阶段的决策，它依赖于d（1, 9）、d（2, 9）和d（3, 9）的计算结果，而由此模式推知，

d（1, 9）=min{c14+d（4, 9）, c15+d（5, 9）}，

d（2, 9）=min{c24+d（4, 9）, c25+d（5, 9），

c26+d（6, 9）}，d（3, 9）=min{c35+d（5, 9），

c36+d（6, 9）}，

每一个d（i，n-1）都是通过min{cik+d（k,n-1）}得到的k>i&&k

5.2调试过程

在多段图程序中问题仍然是邻接表的建立，采用了另外一种邻接矩阵存储的方法，建立邻接表连边比较方便。

多段图如下所示：

图14多段图

for（i=0;i

for（j=0;j

cost[i][j]=MAX;

cost[0][1]=9;cost[0][2]=7;cost[0][3]=3;cost[0][4]=2;cost[1][5]=4;cost[1][6]=2;cost[1][7]=1;cost[2][5]=2;cost[2][6]=7;cost[3][7]=11;cost[4][6]=11;cost[4][7]=8;cost[5][8]=6;cost[5][9]=5;cost[6][8]=4;cost[6][9]=3;cost[7][9]=5;cost[7][10]=6;cost[8][11]=4;cost[9][11]=2;cost[10][11]=5;

/*生成邻接表*/

for（i=0;i

L[i]=（structnode*）malloc（sizeof（node））;

for（i=0;i

{

q=L[i];

for（j=0;j

if（cost[i][j]>0&&cost[i][j]

{

p=（structnode*）malloc（sizeof（node））;

p->v=j;

p->w=cost[i][j];

q->next=p;

q=p;

}

q->next=NULL;}

5.3运行结果

图15多段图最短路径程序运行结果

六、总结

通过本次学习，更加深入的了解了递归分子以及贪婪法和动态规划的思想，即如果一个问题的最优解可以分解为找子问题的最优解，那么即可使用动态规划。

并且区别了分治法和动态规划思想的异同，最大的不同点就是动态规划问题中的子问题不是相互独立的，而分治法的子问题是相互独立的。

学会了对背包问题的分析求解。

就多段图问题而言，学会了从“向前”和“向后两方面”理解问题，采用递推的方式依次求得问题的最优解。

将选择最短路径的实际问题同算法内容相结合，使得知识应用于实践。

同时在算法的设计中学会了单步调试，增强了程序改错的能力，在过程中巩固了邻接表的存储方式，收获颇丰。