２０１３年第４期 文章编号：１００９—２５５２（２０１３）０４—０１４７—０４ 中图分类号：ＴＰ３０１．６ 文献标识码：Ａ 分支限界算法在导游系统路径优化中的应用 薛东伟，李东新，周黎明 （河海大学计算机与信息学院，南京２１１１００） 摘要：为解决游客出行时选取最短旅行线路的困扰，在导游系统中加入了路径分析的功能。 将分支限界算法应用于最短路径分析中，通过获取不同景点的ＩＤ号以及地理位置找到一条通过 每个景点且只通过一次的最短旅行路线，通过仿真，其结果达到了预期的目标。 关键词：最短路径；限界函数；分支限界算法 Ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｂｒａｎｃｈ ａｎｄ ｂｏｕｎｄ ａｌｇｏｒｉｔｈｍ ｉｎ ｔｏｕｒ ｇｕｉｄｅ ｓｙｓｔｅｍ ｆｏｒ ｐａｔｈ ｏｐｔｉｍｉｚａｔｉｏｎ ＸＵＥ Ｄｏｎｇ—ｗｅｉ，ＬＩ Ｄｏｎｇ—ｘｉｎ，ＺＨＯＵ Ｌｉ—ｍｉｎｇ （ＣｏＲｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ ｏｆ Ｈｏｈａｉ Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ ２１ １ １００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｏｒｄｅｒ ｔｏ ｓｏｌｖｅ ｔｈｅ ｐｒｏｂｌｅｍ ｔｈａｔ ｔｏｕｒｉｓｔｓ ｓｅｌｅｃｔ ｔｈｅ ｓｈｏｒｔｅｓｔ ｒｏｕｔｅ ｗｈｅｎ ｔｒａｖｅｌｌｉｎｇ，ｐａｔｈ ａｎａｌｙｓｉｓ ｆｕｎｃｔｉｏｎ ｉｓ ａｄｄｅｄ ｉｎ ｔｏｕｒ ｇｕｉｄｅ ｓｙｓｔｅｍ．Ｔｈｅ ｂｒａｎｃｈ ａｎｄ ｂｏｕｎｄ ａｌｇｏｒｉｔｈｍ ｉｓ ａｐｐｌｉｅｄ ｔｏ ｔｈｅ ｓｈｏｒｔｅｓｔ ｐａｔｈ ａｎａｌｙｓｉｓ，ｆｉｎｄｉｎｇ ｔｈｅ ｓｈｏｒｔｅｓｔ ｒｏｕｔｅ ａｌｏｎｇ ｗｈｉｃｈ ｅａｃｈ ｓｐｏｔ ｉｓ ｐａｓｓｅｄ ａｎｄ ｏｎｌｙ ｏｎｃｅ ｔｈｒｏｕｇｈ ａｃｃｅｓｓ ｔｏ ＩＤ ｎｕｍｂｅｒ ａｎｄ ｌｏｃａｔｉｏｎ ｏｆ ｄｉｆｆｅｒｅｎｔ ｓｐｏｔｓ．Ｔｈｒｏｕｇｈ ｔｈｅ ｓｉｍｕｌａｔｉｏｎ，ｔｈｅ ｒｅｓｕｌｔ ｈａｓ ａｃｈｉｅｖｅｄ ｔｈｅ ａｎｔｉｃｉｐａｔｅｄ ｔａｒｇｅｔ． Ｋｅｙ ｗｏｒｄｓ：ｔｈｅ ｓｈｏｒｔｅｓｔ ｐａｔｈ；ｂｏｕｎｄｉｎｇ ｆｕｎｃｔｉｏｎ；ｂｒａｎｃｈ ａｎｄ ｂｏｕｎｄ ａｌｇｏｒｉｔｈｍ ０ 引言 景点只能通过一次的情况下走过的最短距离ｄ＝ 路径分析问题是导游系统中必不可少的部分， 其主要作用是为游客提供一个遍历多个景点最短行 ｉｄ，∑ｄ ， 。 １．２分支限界算法的解空间树模型 程的方案，这是一个典型的旅行商问题 （Ｔｒａｖｅｌｉｎｇ 设有最小值化问题：ｍｉｎ Ｆ（ ）， ∈Ｚ，其中，Ｆ Ｓａｌｅｍａｎ Ｐｒｏｂｌｅｍ，ＴＳＰ），目前用来解决ＴＳＰ问题的 算法很多，例如蛮力算法－２］、回溯算法 Ｊ、遗传算 是问题的目标函数，Ｘ＝［ ，， ：，…， ］是问题的ｎ 法 ］、蚁群算法Ｌ４ 和粒子群优化算法 等。本文采 维决策变量，Ｚ＝［ ］ 是决策空间。如图１所示， 用分支限界算法－６ｊ，该算法是一类求解最优化问题 解空间树的第ｉ层共有ｍ 个节点，ｉ＝１，２，…，ｎ＋ 的重要算法，它将问题的解空间表示为解空间树，通 １，整棵解空间树的节点数目为（１＋ｍ＋ｍ ＋…＋ 过巧妙地设计限界函数，在搜索解空间树的过程中 ｍ ）＝（ｍ 一１）／（ｍ一１）。分支限界算法在根节 动态地剪除不可能找到最优解的子树，并不断地调 点处算出目标函数值的一个最差边界∞，在扩展根 整搜索方向来尽快找到最优解。 节点后，通过限界函数估计出节点１的子树所含最 １ 问题分析 好解的目标将差于 ，因此对节点１实行剪枝。这 １．１路径分析的数学模型 样，算法避免了无用搜索，提高了搜索效率。 设游客一次需要游览Ⅳ个景点，这些景点的集 收稿日期：２０１２一ｌ１—１５ 合Ｍ＝［ＩＤ。ＩＤ。ＩＤ：…ＩＤ ］，ＩＤ号表示游客走过景 作者简介：薛东伟（１９８７一），男，硕士研究生，研究方向为智能算 点的代号。对于任意两点ＩＤｉ、ＩＤ ，ｄ 表示两地之间 法、计算机应用技术。 的最短距离。所要做的是求出经过这些景点在每个 ｍ”个节点 图１ 分支限界算法的解空间树模型 分支限界算法首先确定目标函数Ｆ的一个最 差边界，在最小值优化问题中可以利用贪心算法 确定目标函数值的下界 。同时，设计一个限界函 数，该函数可用于估计解空间树中每一个分支点 其中， ①若ｉ∈｛ ， ｝，那么瓦（ ）已确定到达（或离 开）景点ｉ的人边（或出边）， 为该确定边及与景 点ｉ相邻的未访问边中最短边的长度之和。 的子树所包含解的最好函数值，表示为ｆ（ ），然后 算法以宽度优先的方式搜索解空间树。当ｆ（ ）＞ 时，ｒ（ ）溢出目标函数的最差边界，算法认为任 何经过 的路径所对应的解都不可能是最优解，对 ②若 ∈｛ ：， ，…， 一 ｝，那么 （ ）已确定 景点ｉ的人边和出边， 之和。 为人边与出边的长度 ③若ｉ隹 （ ），那么景点ｉ的入边和出边均未 确定， 为景点ｉ相邻边中两条最短边的长度 之和。 节点 进行剪枝，不再搜索从 生长出的子树。 ２ 导游系统中路径优化的实现 ２．１ 限界函数的设定 ２．２求解过程 导游系统路径优化问题属于最小值优化问题， 用分支限界算法求解该问题时，需要使用限界函数 定义部分解目标函数值的下界。 设有１７，个景点，景点间的距离矩阵为Ｄ＝ 以５个景点为例，分别编码为１、２、３、４、５，它们 的相邻关系映射为加权图，如图２所示，要求解的是 从任何一个景点出发，经过其它景点且每个景点只 经过一次又回到出发点的最短路径，即求加权图中 的最小哈密顿回路 Ｊ。根据加权图，获得景点间的 距离矩阵Ｄ。 ０ ３ １ ５ ８ ３ Ｏ ６ ７ ９ ［ｄ ，其中，ｄ 表示景点ｉ和 的距离且ｄ ＝略 （ｉ， ＝１，２，…，１７，）。在该问题的合法解中，每个景点 都有且仅有两条相邻边（离开该景点的出边和到达 该景点的入边）。因此在理想情况下，该问题的最 优解为距离矩阵Ｄ中每一行的两个最小元素之和 除以２，即： ＇ ｎ Ｄ＝［ｄ ］５ ５＝ １６ Ｏ ４ ２ ５ ７ ４ ０ ３ ８ ９ ２ ３ ０ Ｆ ≥寺 ［ 哩 （ ＋ ）］ 这一结论可用于辅助设计限界函数。 （１） 由于该问题的解是一个回路，求解时出发景点 的选择不影响解的质量，因此设定景点１为出发景 点。算法的部分求解过程如表１所示。 表１中按算法搜索解空间树的顺序列出了节点 编号ｉ，节点对应的部分解 。（ ），限界函数值 设解空间树中的节点 对应的部分解为 （ ）＝ ［ ， ：，…， ］，其中 ∈｛１，２，…，ｒ，／｝表示第ｉ位访 问的景点，ｉ＝１，２，…，ｍ（１≤ｍ＜ｎ）。那么在最好情 况下，每一个景点（包括已访问和未访问景点）所缺 少的出边或人边都正好是与该景点相邻的未访问边 中的最短边。由此，限界函数可定义为： ｆ（ ）以及算法当前状态下的最差边界 和待扩展 列表 。根据这几项数据，可以跟踪观察算法的搜 索行为： ｆ（ｕ）＝÷∑ ● ｎ ｉ＝１ ．．．——（２） ①令贪心算法从景点１出发并总选择相邻未访 问边中的最短者可得解［１，３，５，４，２，１］，其目标函 １４８－－—— ②在根节点处（ｉ＝１），部分解只包含出发景点 １（ （ ）＝１）。根据式（２）计算距离矩阵中所有行 中两个最小元素之和，可得根节点处的限界函数值 ｆ（ １）＝１４＜ ，将／，１１力Ⅱ入 。 ③从 中取出根节点并将其扩展，可得４个子 节点２，３，４，５，分别对应部分解［１，２］，［１，３］，［１， ４］，［１，５］。按式（２），可得４个节点的限界函数值 为ｒ（ ２）＝１４，ｒ（ ３）＝１４，／－（ ）＝１５．５， ｒ（／，ｔ ）＝１９。注意在该例问题中，所有边的权值均为 整数，不可能得到带小数的目标函数值，且限界函数 图２相邻关系加权图 求的是部分解目标函数值的下界，因此可以把 的 数值作为分支限界算法最差边界的初值，即 ＝１６。 限界函数值调整为大于１５．５的第一个整数，即 为了提高搜索效率，尽快找到最优解，将剪枝条件设 ｆ（ ）＝１６。这样根据剪枝条件ｒ（ ）≥∞，将节点 为ｒ（／，Ｐ）≥ ，即当Ｆ（ ）＜ 时，节点被加人待扩展 ／Ｊ２， 加入￡，而把 ，／．Ｐ 的子树剪去，如图３所示。 列表 中。 表１分支限界算法求最短路径的部分过程 ④按上述方式继续搜索，算法在节点 处找到 解［１，３，４，５，２，１］，该解的目标函数值为２０。由此 第一个叶节点，得到解［１，３，５，４，２，１］，该解的目标 可知［１，３，５，４，２，１］是问题的一个最优解。 函数值为１６；在节点 。，处找到另一个叶节点，得到 图３分支限界算法求最短路径的解空间树 图３给出了算法搜索过的解空间树，树中边上 园、莫愁湖、中山陵、总统府，通过检索ＧＩＳ数据库可 的权值为对应路径的长度，记号“×”标示发生了剪 以获得它们的ＩＤ号分别为：１０３５、２１２６、１０７８、３０７９、 枝的节点。 ２２６０。在获得ＩＤ号后，通过Ｅｓｕｐｅｒｍａｐ提供的类 ３ 实验与仿真 ＣｓｅＰａｔｈＡｎａｌｙｓｅ，获得各景点两两之间驾车游最短路 实验中假定从河海大学出发，经过白鹭洲公 径的矩阵： ——－——１４９．．．—— ０ ７２４６ ３５１７ ９９９９ ４４７６ ４ 结束语 ７２４６ ０ ５６８６ ７９７０ ４４８４ 分支限界算法采用限界函数来对解空间树进行 Ｄ＝ ３５１７ ５６８６ ０ ９７２４ ４３８９ 剪枝，缩小了搜索范围；同时它也根据限界函数来自 ９９９９ ７９７０ ９７２４ ０ ６９５８ 适应地调整搜索方向，优先搜索可能含有最优解的 ４４７６ ４４８４ ４３８９ ６９５８ ０ 分支。通过实验表明，该算法应用于导游系统中，能 通过分支限界算法获得经过各景点的最短路径 较快的求得最佳解，给游客提供一条最短旅行路径， 优化结果为：１０３５—１０７８—２１２６—３０７９—２２６０— 节省了时间，也减少了差旅费用，具有较好的应用 １０３５，将ＩＤ号转换为地点以后很明了最短路径所经 前景。 过的最优路线是：河海大学一莫愁湖一白鹭洲公 参考文献： 园一中山陵一总统府一河海大学。程序运行后如图 ［１］戴宗瑞．ＴＳＰ问题在物流配送车辆运行路线中的应用分析［Ｊ］． ４所示，最短路径长度为２８６０７，结果表明，通过分 软件导刊，２０１２，１１（６）：９３—９５． 支限界算法所求的最短路径是满足导游系统路径分 ［２］张军，钟竞辉，龚月娇，等．算法设计与分析［Ｍ］．北京：清华大学 析要求的，且效果明显。 出版社，２０１１． ［３］Ｒｕｄｏｌｐｈ Ｇ．Ｃｏｎｖｅｒｇｅｎｃｅ ｐｒｏｐｅｒｔｉｅｓ ｏｆ ｃａｎｏｎｉｃａｌ ｇｅｎｅｔｉｃ ａｌｇｏｉｒｔｈｍｓ ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ Ｎｅｕｒａｌ Ｎ ０ ｓ，１９９４，５（１）：９６—１０１． ［４］Ｄｏｒｉｇｏ Ｍ，Ｇａｍｂａｒｄｅｌｌａ Ｌ Ｍ，Ｍｉｄｄｅｎｄｏｒｆ Ｍ，ｅｔ ａ１．Ｇｕｅｓｔ ｅｄｉｔｏｒｉａｌ： ｓｐｅｃｉａｌ ｓｅｃｔｉｏｎ ｓｐｅｃｉａｌ ｓｅｃｔｉｏｎ ｏｎ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ，２００２，６（４）：３１７—３１９． ［５］高尚，韩斌，吴小俊，等．求解旅行商问题的混合粒子群优化算 法［Ｊ］．控制与决策，２００４，１９（１１）：１２８６—１２８９． ［６］陈涛，张思发．分支限界算法求解实际ＴＳＰ问题［Ｊ］．计算机工 程与设计，２００９，３０（１０）：２４３１—２４３４． ［７］常友渠，肖贵元，曾敏．贪心算法的探讨与研究［Ｊ］．重庆电力高 等专科学校学报，２００８，１３（３）：４０－４３． 图４最短路径求解结果 ［８］陈萍，申红莲．求哈密顿回路的若干技巧［Ｊ］．衡水学院学报， ２０１２，１４（１）：２６—２９． 责任编辑：刘新影 （上接第１４６页） 特性进行了分析，通过分析和计算，可以看出矢量有 董秘Ｉ 限元法可以有效地减少电场和磁场的冗余模。当 螂ｚｌ＃嘲｝ ｇ．自娃赫墒瞻 ｄ／ｂ取值０．２时，单模带宽和截止波长可以达到理 ．＃瓣，＃瑚 ５ 黟粥 ＃触 想情况。同时主模ＴＥｌ０的场图也可以明显改进。 舔未 鼬瓤‘黼 参考文献： ｌｅ啪 ＇．钠游ｔ－鼬§ ［１］Ｑｉｆｅｎｇ Ｓｕｎ，Ｍａｌ Ｌｕ，Ｘｉ￣ｑｉｎａｇ Ｃｈｅｎ．Ａｎａｌｙｓｉｓ ｏｆＴｒａｎｓｆｅｒ Ｃｈａｒａｅ— § 霜豁酶 日喜 ｔｅｒｉｓｔｉｃ ｏｆ Ｄｏｕｂｌｅ—Ｒｉｄｇｅ Ｐｏｓｉｔｉｏｎ ｏｎ ｔｈｅ Ｓｈｏｒｔ Ｓｉｄｅ ｏｆ Ｗａｖｅｇｕｉｄｅ 缸 船嘲§ Ｚ 豹蜥幛孵 ： ２００７，３２（６）：２９－３１． ’薅２§碗盼 ＝＝＝＝＝奠：冀 ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｍｉｃｒｏｗａｖｅｓ，［２］Ｕｔｓｕｍｉ Ｙ．Ｖａｒｉａｔｉｏｎａｌ ａｎａｌｙｓｉｓ ｏｆ ｉｒｄｇｅｄ ｗａｖｅｇｕｉｄｅ ｍｏｄｅｓ［Ｊ］．ＩＥＥＥ ．ｇｉｌ孵婶酶 ｌ 毒ｌ孽ｌ瞻嗡孽霉 Ｔｒａｎｓ Ｍｉｃｒｏｗａｖｅ Ｔｈｅｏｒｙ Ｔｅｃｈ，１９８５，３３（２）：１１１—１１９． ｌ，嚣辜 碡咚辜 裨 ※ 誊§瞬 ０ ［３］Ｓｕｎ Ｑ Ｆ，Ｌｕ Ｍ，Ｃｈｅｎ Ｘ Ｑ．Ａｎａｌｙｓｉｓ ｏｆ Ｔｒａｎｓｆｅｒ Ｃｈａｒａｃｔｅｒｉｓｔｉｃ ｏｆ ． 嘛 Ｄｏｕｂｌｅ—Ｒｉｄｇｅ Ｐｏｓｉｔｉｏｎ ｏｎ ｔｈｅ Ｓｈｏｒｔ Ｓｉｄｅ ｏｆ Ｗａｖｅｇｕｉｄｅ［Ｊ］．Ｊｏｕｒｎａｌ ．懒嘲 错戆 ｏｆ Ｍｉｃｒｏｗａｖｅｓ，２００７，２３（６）：２９—３１． ［４］Ｎｉ Ｇ Ｚ，Ｙａｎｇ Ｚ Ｙ．Ｅｎｇｉｎｅｅｉｒｎｇ ｅｌｅｃｔｒｏｍａｇｎｅｔｉｃ ｆｉｅｌｄ ｎｕｍｅｒｉｃａｌ ｃａｌ— ｃｕｌａｔｉｏｎ［Ｍ］．Ｍｅｃｈａｎｉｃａｌ Ｉｎｄｕｓｔｒｙ Ｐｒｅｓｓ，２００４． 圈５高次模ＴＥｌｌ电场图 ［５］Ｍｃｋａｙ Ｍ，Ｈｅｌｓｚａｊｎ Ｊ．Ｖｏｌｔａｇｅ—ｃｕｒｒｅｎｔ ｄｅｆｉｎｉｔｉｏｎ ｏｆ ｉｍｐｅｄａｎｃｅ ｏｆ 稀少。高次模ＴＥｌ１的电场则被分隔成两个对称的 ｓｉｎｇｌｅｒｉｄｇｅ ｗａｖｅｇｕｉｄｅ［Ｊ］．ＩＥＥＥ Ｍｉｃｒｏｗａｖｅ ａｎｄ Ｇｕｉｄｅｄ Ｗａｖｅ Ｌｅｔ— ｔｅｒｓ，１９９９，９（２）：６６—６８． 区域。 责任编辑：肖滨 ３ 结束语 本文通过矢量有限元法对窄边双脊波导的传输 ．．．——１５０・－－——