第3章篇 动态规划.ppt

* 多段图 令|V1| =|Vk|=1,称s ∈V1为源点，t∈Vk为汇点。 s t * 首先，根据定义，将图划分成若干个段； 随后，从左向右逐段为顶点编号 （源点编号为0，汇点编号为n-1） * 多段图最短路径问题：求从源点s到达汇点t的最小花费的通路。 s t * （1）分析最优子结构 假设从顶点i到汇点t的最短通路为： （i,j,……,t） 则（j,……,t）一定是从顶点j到汇点t的最短通路。 证明：反证法。 * （2）递归关系 首先，确定k-1段的所有顶点到达汇点t的花费最小的通路。 cost[i]：存放顶点i到汇点t的最小花费 path[i]：存放最小花费通路上，i顶点的直接后继顶点编号 随后，利用 k-1段的计算结果，计算k-2段的所有顶点到达汇点t的花费最小的通路。以此类推，直到确定源点s到汇点t的花费最小的通路。 * 递归关系 cost[i] = min { cij + cost[j] } ijn 0 i = n-1 i j j j …... …... …... t * （3）计算最优值 创建数组path，并在数组path中存放目前确定的花费最小通路的情况。path[i]存放从i顶点到达汇点t花费最小通路上顶点i的直接后继顶点编号。 * 最小花费通路：0-2-3-5-8-9 0 1 2 3 4 5 6 7 8 2 5 3 5 8 8 8 9 9 path * 算法为语言描述： （1）初始化cost[i] = 最大值，cost[n-1] = 0; path[i]=-1 （2）for ( i=n-2; i=0; i--) 计算cost[i],path[i] （3）根据path计算花费最小的通路， 并存放在数组route中 令i=0; route[0]=0; 重复计算下列公式，直到route[i]=n-1 i++; route[i] = path[route[i-1]]; * 0 1 2 3 4 5 6 7 8 9 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 0 1 2 3 4 5 6 7 8 9 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 cost path 初始化 * 0 1 2 3 4 5 6 7 8 9 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 3 0 0 1 2 3 4 5 6 7 8 9 -1 -1 -1 -1 -1 -1 -1 -1 9 -1 cost path i= 8: * 0 1 2 3 4 5 6 7 8 9 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 7 3 0 0 1 2 3 4 5 6 7 8 9 -1 -1 -1 -1 -1 -1 -1 9 9 -1 cost path i= 7: * 0 1 2 3 4 5 6 7 8 9 ∞ ∞ ∞ ∞ ∞ ∞ 8 7 3 0 0 1 2 3 4 5 6 7 8 9 -1 -1 -1 -1 -1 -1 8 9 9 -1 cost path i= 6: * 0 1 2 3 4 5 6 7 8 9 ∞ ∞ ∞ ∞ ∞ 9 8 7 3 0 0 1 2 3 4 5 6 7 8 9 -1 -1 -1 -1 -1 8 8 9 9 -1 cost path i= 5: * 0 1 2 3 4 5 6 7 8 9 ∞ ∞ ∞ ∞ 9 9 8 7 3 0 0 1 2 3 4 5 6 7 8 9 -1 -1 -1 -1 8 8 8 9 9 -1 cost path i= 4: * 0 1 2 3 4 5 6 7 8 9 ∞ ∞ ∞ 13 9 9 8 7 3 0 0 1 2 3 4 5 6 7 8 9 -1 -1 -1 5 8 8 8 9 9 -1 cost path i= 3: * 0 1 2 3 4 5 6 7 8 9 ∞ ∞ 14 13 9 9 8 7 3 0 0 1 2 3 4 5 6 7 8 9 -1 -1 3 5 8 8 8 9 9 -1 cost path i= 2: * 0 1 2 3 4 5 6 7 8 9 ∞ 15 14 13 9 9 8 7 3 0 0 1 2 3 4 5 6 7 8 9 -1 5 3 5 8 8 8 9 9 -1 cost path i= 1: * 0 1 2 3 4 5 6 7 8 9 15 15 14 13 9 9 8 7 3 0 0 1 2 3 4 5 6 7 8 9 2 5 3 5 8 8 8 9 9 -1 cost path i= 0: * 有向连通带权图采用邻接矩阵表示 #define VEX_NUM ? #define