浮动算法： dp思想。
动态规划算法的基本步骤：
划分阶段：根据问题的时间或空间特征，将问题划分为几个阶段。 这几个阶段是没有后向性的，也就是说，当前状态包含此阶段之前的所有历史信息，下一阶段的状态仅与当前状态相关。 选择状态：用不同的状态表示问题发展到各个阶段时的各种客观情况。 决策和状态转移方程的建立：决策是指从当前阶段执行到下一个阶段的操作，通常根据两个相邻状态之间的关系来做出决策。 编写规划方程(基本方程) :只要阶段、状态、决策确定，基本方程比较简单。 请注意，这里给出基本方程的边界条件。 OK，你觉得动态计划的步骤难懂吗？ 以floyed算法为例，看看动态编程是什么。
首先，分阶段吧。 我们的map中总共包含了n个顶点，根据初始条件，任意两个顶点dis[i][j]的距离要么是邻接距离要么是。 假设每次通过点时，dis[i][j]的距离都会更新。 遍历所有点时，dis[i][j]将更新n次。 然后，我们可以把那个分成n个状态。 接下来，需要确认状态。 我想大多数人一眼就能看出这一点，每次添加点时，dis[i][j]都是现阶段的状态。 Then，确定决策和状态转移方程。 我们的目的是什么？ 当然，是尽量降低任意两个顶点之间的距离。 于是，可以得到状态转移方程式：
dis[I][j]=min(dis[I][j]，dis[i][k] dis[k][j] )，其中我们的基本方程是状态转移方程。 标准动态规划的基本框架：
代码ing :
//console application _ floyed.CPP :此文件包含“主”函数。 程序的执行在此开始并结束。 //# include iostream # include vector # include algorithm # define inf0x3ffffusingnamespacestd； int main () {int N，m，c1，c2； cin N M c1 c2； vectorvectorintvec(n )、path(N ) ) n； int i，j，k； for(I=0； i N； I ) vec[I].resize(n )； path[I].resize(n； //dis[I].resize(n； fill(vec[I].Begin )、vec[i].end )、inf )； vec[i][i]=0； (}int a、b、c； for(I=0； i M； I ) {cin a b c； vec[a][b]=vec[b][a]=c； (for ) I=0； i N； I ) for(j=0； j N； j () if ) vec[I][j]！=inf () {path[i][j]=j； }else{path[i][j]=-1； }}for(k=0； k N； k ) for(I=0； i N； I ) for(j=0； j N； j () if ) vec [ I ] [ j ] vec [ I ] [ k ] vec [ I ] [ j ] ) { vec [ I ]=vec [ I ] [ k ] vec [ k ] [ j ]； path[i][j]=k； }}}}cout vec[c1][c2]； i=c1，j=c2； cout endl； cout c1； wile(path[I][j]！=j ) {cout path[i][j]； i=path[i][j]； }cout path[i][j]； 返回0； }测试样品：5 6 0 20 1 10 2 20 3 11 2 12 4 13 4 1
版权声明：该文观点仅代表作者本人。处理文章：请发送邮件至 三1五14八八95#扣扣.com 举报，一经查实，本站将立刻删除。
