单人最优巡回路问题算法研究.pdfVIP

维普资讯 第 33卷 第 2期 河南师范大学学4gL(自然科 学版) Z．33 No．2 2005年5月 』 !堡 HeanNormalUniversity (NaturalScience) Mav．2005 文章编 号 ：10oO一2367(2005)02--0109—04 单人最优巡 回路 问题算法研究 孙立博 ，罗定 昆，王钰琨 (华中师范大学 数学与统计学学院，武汉 430079) 摘 要 ：基于生活实例，引出问题讨论 。建立 了理论模型及实用简化模型，在 BORLANDC环境中编程实现了 最小生成树算法和递归穷举法．最后 ，分析了理论模型的缺陷，并运用递归穷举法对结果进行检验． 关键词 ：最优巡回路；数学模型；哈密尔顿圈；最小生成树；递归穷举法 中图分类号 ：O157．5 文献标识码 ：A 最优巡回路 问题是组合优化中的著名难题，其应用例如交通 车辆的最佳巡回路线 、教师任课 的班级分配、数控机 床的运 行、最优兑换率等，在生活中具有极大的实用价值．在一定条件下最优巡 回路可 以转化为最优 Hamilton路 问题求解 ．便求解最 优 HamiltonCycle，当规模较大时，由于计算繁杂 ，欲求得真正的最优解往往十分困难 ，而只能用近似的方法得到近似最优解． 本文将数学理论与计算机编程相结合 ，对单人最优巡回路算法进行讨论，力求在结点数 目较大的情况下求得问题的最优解． 1 问题 的提 出与符号系统 1．1 提 出问题 图 l为我 国部分旅游城市铁路的交通 费用图 ，每条边 的 权表示火车票价 (单价元)，且火车均为特快．武汉某高校学生 甲、乙、丙计划利用暑期一起出游 ，假设他们从武汉 出发，游经 每个城市 ，最后仍回到武汉 ，问应该如何选择行走路线使总乘 车费用最低 ． 1．2 初步分析 这是一个典型的网络组合运筹问题 ，主要是运 用运筹 学 的理论和方法解决．将 问题一般化 ，n个城市记为 ， ，…， y ，Ⅳ “表示从 i城到 城的距离．他们三人从城市 (武汉) 出发到其他每个城市去至少一次，然后 回到城市 y 。要求使 总的乘车费用最少． 1．3 模型的假设 L海 (1)所有的旅游景点所在地均看作其所在 城市 ，用图中 节点表示 ； (2)假设 甲、乙、丙 三人 的交通工具 只有火 车，在某一 城 图 l 我囤部分旅游铁路交通 费f}】圈 市内各景点问的交通费用忽略不计 ； (3)不考虑交通意外，如火车晚点等 ； (4)假设这三人一定会安排好时间乘坐预先假定好的特快列车． 1．4 符号系统 N(V。E，Ⅳ)，No(Vo，Eo，Wo)。N ( E 。W )都表示图；y， ， 表示点集合 ，E， ，E 表示边的集合 ，W ，W。，W 表示权 收稿 日期 ：2004—12—24 基金项 目：国家 自然科学基金资助项 目 作者简介 ：孙立博 (1983一 )。男。河南新 乡人，华 中师范大学学士，研究方 向：计算数学 维普资讯 11O 河南师范大学学报 (自然科 学版) 2005生 的集合． V．(i一 1，2…，)表示第 i个旅游城市 ； W ，表示乘火车从城市 到 ，的费用 ； ． w嘶， ．w。 分别表示 No，N 中的相