给定一个有向无环图$G=(V,E)$,边权重为实数,给定图中的两个顶点$k,t$,设计动态规划算法,求从k到t的最长简单路径,子问题图是怎样的?算法的效率如何?算法分析:该问题不能够用贪心求解,假设从k出发,每一步取得weight最大的边,按这样的路径,并不能够保证能走到终点t。所以考虑动态规划算法。该问题满足动态规划算法的两个特征:一、最优子结构:从k出发到t的最优路径,一定是$max(best , path , A_1 , to ,, t+weightA_0)$,其中$A0-->A1-->cdots t$和$B0-->B1-->cdots t$等等的诸多方案中的最优方案,构成了最优解。符合“剪贴”性质。二、重叠子结构有上面的公式可知,子问题:$A0-->A1-->cdots t$会被反复求解。状态转移函数:int q=weight[k][t];
for(int i=k+1;i<=t && weight[k][i];i++)
{
q=max(q,weight[k][i]+Find_longest_path(weight,numVertexes,i,t,r));
}
r[k]=q;
return q;算法实现Graphic_longest_path.h#include#includeusing namespace std;
#define INITWEIGHT 0
//
...
继续阅读
(25)