王弘力,古代风俗百图 英道双肩难负重‘乾坤尽在一中 鼓樹头 题 东无须竭力夹 七十六·金货郎担 鼓 塘
货郎担问题
货郎担问题 小组成员: 卢广桃 谢伟娜 郑理
货郎担问题 小组成员： 卢广桃 谢伟娜 郑理
货郎担问题 货郎担问题一般提法为:一个货郎从某 城镇出发,经过若干个城镇一次,且仅经过 一次,最后仍回到原出发的城镇,问应如何 选择行走路线可使总行程最短,这是运筹学 的一个著名的问题。 实际中有很多问题可以归结为这类问题
货郎担问题 货郎担问题一般提法为：一个货郎从某 城镇出发，经过若干个城镇一次，且仅经过 一次，最后仍回到原出发的城镇，问应如何 选择行走路线可使总行程最短，这是运筹学 的一个著名的问题。 实际中有很多问题可以归结为这类问题
哈密尔顿回路: (环球旅行问题) 即从一个结点出发, 经过所有结点回到 出发点(结点不能 重复经过)
哈密尔顿回路： （环球旅行问题） 即从一个结点出发， 经过所有结点回到 出发点（结点不能 重复经过）
问题描述: 设v1,v2, ,vn是已知的n个城镇, 城镇v到城镇v的距离为dj,现求从v1出发, 经各城镇一次且仅一次返回v的最短路程 解决方案: 1穷举法? 2最短路标号法? 3指派问题? 4整数规划? 5动态规划?
设v1，v2，……..，vn是已知的n个城镇， 城镇vi到城镇vj的距离为dij，现求从v1出发， 经各城镇一次且仅一次返回v1的最短路程。 问题描述： 解决方案： 1.穷举法？ 2.最短路标号法？ 3.指派问题？ 4.整数规划？ 5.动态规划？
建立动态规划模型: 设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