建立动态规划模型: 设S表示从1到v中间所可能经过的城市集 合,S实际上是包含除v1和v两个点之外的其余点 的集合,但S中的点的个数要随阶段数改变。 阶段:S中的点的个数
设S表示从v1到vi中间所可能经过的城市集 合，S实际上是包含除v1和vi两个点之外的其余点 的集合，但S中的点的个数要随阶段数改变。 阶段： S中的点的个数 建立动态规划模型：
建立动态规划模型: 状态变量(i,S)表示:从v1点出发,经过S集合中所 有点一次最后到达vi 最优指标函数fk(i,S)为从v1出发,经过S集合中所 有点一次最后到达v。 决策变量Pk(i,S)表示:从v1经k个中间城镇的S集合 到vi城镇的最短路线上邻接v的前一个城镇,则动态规 划的顺序递推关系为:
状态变量（i，S）表示：从v1点出发，经过S集合中所 有点一次最后到达vi。 最优指标函数fk（i，S）为从v1出发，经过S集合中所 有点一次最后到达vi。 决策变量Pk（i，S）表示：从v1经k个中间城镇的S集合 到vi城镇的最短路线上邻接vi的前一个城镇，则动态规 划的顺序递推关系为： 建立动态规划模型：
w动通 fk(i, s)=mint fk1 (j,S jj+djj j属于S fo(i,空集)=dn(k=1,2, ■■■ n i=2,3,n)
fk（i，S）= min{ fk-1（j，S、{ j }+dji} j属于S f0（i，空集）=d1i （k=1，2，…,n-1, i=2,3,…n)
例12已知4个城市间距离如下表,求从v1出 发,经其余城市一次且仅一次最后返回v1的最短 路径和距离。 距离 234 0856 26085 3790 49780 5
例12 已知4个城市间距离如下表，求从v1出 发，经其余城市一次且仅一次最后返回v1的最短 路径和距离。 Vj 距离 Vi 1 2 3 4 1 0 6 7 9 2 8 0 9 7 3 5 8 0 8 4 6 5 5 0
解:K=0 由边界条件(721b)知 f0(2,空集)=d12=6 f0(3,空集)=d13=7 f0(4,空集)=d14=9
解：K=0 由边界条件（7.21b)知: f0(2,空集)=d12=6 f0(3,空集)=d13=7 f0(4,空集)=d14=9