一类旅行总费用最小路线模型及其求解策略.pdfVIP

第l9卷 第4期 塔 里 木 大 学 学 报 VO1．19 No．4 2007年12月 Journal of Tarim University Dec．20o7 文章编号：1009—0568(2007)04—0022—03 一 类旅行总费用最小路线模型及其求解策略 王继顺 闫敏伦 王传斌 (连云港师范高等专科学校数学系，江苏连云港 222006) 摘要 旅行总费用最小路线问题是生活实际中常见的一类问题，本文建立了该类问题的赋权多阶段有向图模型。多阶段有 向图是应用中常见的一种有向图，有许多运输、工程、管理等的实际问题能转化为有向图最短路问题进行求解，尤其赋权多阶 段有向图对解决该类实际问题更具有重要意义。研究了赋权多阶段有向图的最短路问题，从图上逆序标号法、表上作业法和 动态规划法不同的角度对文中模型给出了赋权多阶段有向图最短路求解策略。 关键词 有向图；赋权多阶段有向图；最短路 中图分类号：O157．5 文献标识码：A A Shortest Path Model for the Most Economical Traveling and Its Solutions Wang Jishun Yan Minlun Wang Chuanbin’ (Department of Mathematics-Lianyungang Teacherg College，Lianyungang-Jiangsu-222006) Abstract The shortest path problem of the most economical traveling is popular practically．The multi—stage weighted directed graph model for the problem is set up．Multi—stage weighted directed graph is popular in application．Many practical issues such as trans— port，engineering，management can be solved by transforming into the shortest path problem．In particular，shortest path problem of the multi—stage weighted directed graph is more significance in solving such practical problems．In this paper，we study the shortest path problem of the multi—-stage weighted directed graph and several solutions to it are presented by using an example from different per· spective that is reverse labeling method on the graph，the tabular method and dynamic programming． Key words directed graph；multi—stage weighted directed graph；shortest path 1 引言 工具，用于解决其他的优化问题。 旅行总费用最小路线问题是生活实际中常见的 本文主要通过一个旅行总费用最小路线问题， 一 类问题，同管道铺设、线路安排、厂区布局、设备更 建立该类问题的赋权多阶段有向图模型，然后从图 新等问题一样都可以转化为最短路问题。最短路问