最短路径问题一—结论 C1 D1 B1 -c2 A D2 E 3B2 C38 D3 c43 从以上过程可以看出,每个阶段中,都求出本阶段的各个 初始状态到过程终点E的最短路径,当逆序倒退到过程 起点A时,便得到了全过程的最短路径
最短路径问题——结论 从以上过程可以看出，每个阶段中，都求出本阶段的各个 初始状态到过程终点E的最短路径，当逆序倒退到过程 起点A时，便得到了全过程的最短路径。 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E 5 3 1 6 3 8 4 5 5 6 8 3 3 4 3
最短路径问题一一DP条件 ◎最优子结构性质:任何最短路径的子路径都是相对于子路径的始点和终点 的最短路径 从A>B2→>C4→>D3-→>E是A到E的最短路,则A→>B2→>c4→>D3 是A到D3的最短路,A>B2->c4-是A到c4的最短路 子问题重叠性质:任何中间结点到终点的距离都被前面的结点多次使用 C1 B1K6C2 D1 A D2 E 3B2 C3 D3 3 C43
最短路径问题——DP条件 最优子结构性质：任何最短路径的子路径都是相对于子路径的始点和终点 的最短路径 子问题重叠性质：任何中间结点到终点的距离都被前面的结点多次使用 从A->B2->C4->D3->E是A到E的最短路，则A->B2->C4->D3 是A到D3的最短路，A->B2->C4-是A到C4的最短路…… A B1 B2 C1 C2 C3 C4 D1 D2 D3 E 5 3 1 6 3 8 4 5 5 6 8 3 3 4 3
动态规划的条件 当前状态为D3的时候,到D3的最短路与 以前所经过的结点无关,如到D3经过的点 为A→>B2>C3→>D3或A>B2->C4->D3都对 o无后效性 以后的求解无关 过去的步骤只能通过当前状态影响未来的发展,当前的状 态是历史的总结。 C1 D1 B1 C2 6 D2 E B2 C3 D3 c43
动态规划的条件 无后效性 过去的步骤只能通过当前状态影响未来的发展，当前的状 态是历史的总结。 当前状态为D3的时候，到D3的最短路与 以前所经过的结点无关，如到D3经过的点 为A->B2->C3->D3或A->B2->C4->D3都对 以后的求解无关。 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E 5 3 1 6 3 8 4 5 5 6 8 3 3 4 3