图论在旅游线路选择中的应用.pdfVIP

第 卷 第 期 长 春 工 业 大 学 学 报 自然科学版 年 月 图论在旅游线路选择中的应用 方冬云 ’, 福州大学 离散数学研究 中心 , 福建 福州 莆 田学院 数学系 , 福建 莆 田 摘 要 运用 “最邻近插入法 ”和 “分枝定界法 ”两种方法建立寻找近似最佳旅游线路 的图论模 型 ,提 出求解 的算法 ,并 以莆 田市为例具体分析它们 的求解过程 ,为旅游者设计旅游线路提供 理论依据和参考 。 关键词 旅游线路 哈密顿 圈 最邻近插入法 分枝定界法 中图分类号 文献标识码 文章编号 一 一 一 一 · , , , , , , 一 一 , 几一 , , 和分枝定界法 ,来寻找旅游 的近似最佳线路 ,实现 问题 的提 出 旅游者 的最大愿望 。 相 当一部分旅游者希望能充分利用一次难得 假设公路没有等级差别 ,即可将所有路 面的 的外出旅游时机 ,或在有 限的假期 内游览较多的 状况视为等同 ,在汽车速度为恒速 的条件下 ,旅游 旅游 区域 。对于他们来说 ,尽可能缩短旅行在途 路程与旅游所用 的时间成正 比关系 。在较短的时 时间 , 既可提 高时 间利用效率 ,也可减轻旅途劳 间内 ,旅游较多的景点 ,实际上是制定一个合理的 顿 ,因此对于旅游者而言 ,选择设计合理 的旅游线 路线 ,尽量缩短旅游 的路程 ,使总路程最短 〕。这 路 ,既可节省时间 ,又可省钱 〔’〕。文 中利用 图论 中 个 问题可 以用求加权无 向图总权数最小的哈密顿 的求最小哈密顿 圈的两种方法 — 最邻近插人法 圈来寻找近似的最短旅游线路 。 收稿 日期 一 一 基金项 目 福建省科技计划重点基金资助项 目 作者简介 方冬云 一 ,女 ,汉族 ,福建莆 田人 ,莆 田学院讲师 ,福州大学硕士研究生 ,主要从事 图论及其应用研究 , © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. 第 期