最小权度的网络构建问题 李 睿 ． 吕小俊 （云南大学旅游文化学院信息科学与技术系，丽江６７４１００） 摘要：网络构建问题是组合最优化中的经典问题，而连通性是网络设计问题中的一个核心１－＇３题。 考虑这样一个最优化问题：给定无向图Ｇ＝（Ｖ，Ｅ；Ｗ），Ｗ：Ｅ＿＿＋Ｑ 是权重函数，Ｇ ＝（Ｖ，Ｅ ） 为Ｇ的一个子图．要寻找Ｅ的一个子集Ｅ”ＣＥ，使得由Ｅ ＵＥ”所得的诱导子图是一个连通 图，其目标是使得所有方案中权度最大者的权度值达到最小。经过对问题分析．对问题的特 殊情况Ｅ ＝ ．设计了两个时间复杂度分别为０（ｎ。）和Ｏ（ａｍ）的启发式算法。而Ｅ”≠ 的 情况也可以类似讨论 关键词：网络构建：搜索算法：近似算法 １ 问题的描述 现实中经常遇到这样的问题．在若干个城市之间 需要建立一个关系．例如各城市之间修建网络通信或 道路．使得各城市之间能相互连通，其目标一般是要求 所修建网络或道路的费用总和达到最小．这就是典型 的最小支撑树问题（Ｍｉｎｉｍｕｍ Ｓｐａｎｎｉｎｇ Ｔｒｅｅ．简记为 ＭｓＴ）。但在没有宏观的时候。其目标可能会发生 Ｅ．使得Ｅ ＵＥ”所得的诱导子图是一个连通图，其目标 是使得所有方案中权度最大者的权度值达到最小。其 中此处定义某个点ｖ的权度ｗｄ（ｖ）为ＥｆＩ中跟这个点相 关联的所有边的权重之和．即： ｄ（ ）：Ｊ【∑印（ｅ），ｅ∈ ’， 是ｅ的一个端点 ０．其他 改变 例如，若修建某一条道路时所需的费用由用这条 道路直接相连的两个城市共同出资．这样每个城市所 出的费用为跟这个城市相关联的道路的费用之和 为 了使得各城市所出资的数目差距不太大．通常是要达 到这样的目标：使得所有城市中出资最多的城市出的 资金尽可能少，这就是最小权度的支撑树问题。上面的 ２ 问题的研究现状 最小度的支撑树问题实际上是推广的哈密尔顿问 题．因此它是ＮＰ一完备的．即使是图Ｇ满足三角不等 式．该问题仍是ＮＰ一完备的 对于最小度的支撑树问 题．Ｆｔｉｒｅｒ和Ｒａｇｈａｖａｃｈａｆｉｍ给出了一个０（１ｏｇｎ）一近似的 算法．并且将其推广到只有部分点需要连通（Ｓｔｅｉｎｅｒ 树）和有向图的情况 而对于满足三角不等式的最小权 度支撑树问题．Ｇｈｏｄｓｉ等［２】给出了一个４．５一近似的算 法．并证明了除非Ｐ＝ＮＰ．否则满足三角不等式的最小 权度支撑树问题是２一不可近似的。度最小支撑树 问题．常见的一些办法是放宽度的条件得到一个 问题实际上描述的是要构建一个全新网络．但现实中 也可能是在已存在的网络上构建一个新的网络．使得 已有网络中具有的边能完全地被应用于新网络中．此 问题称为最小权度的网络构建问题（Ｍｉｎｉｍｕｍ Ｗｅｉｇｈｔ— ｅｄ Ｄｅｇｒｅｅ Ｎｅｔｗｏｒｋ Ｄｅｓｉｇｎ，简记为ＭＷＤＮＤ），此问题可 以被描述为如下： 给定无向图Ｇ＝（Ｖ，Ｅ；Ｗ），ｗ：Ｅ—Ｑ 是权重函数，Ｇ ＝最优解。Ｇｏｅｍａｎｓ［３］给出了一个（１ Ｂ＋２）一近似的算法。此 后，Ｓｉｎｇｈ和Ｌａｕ问将近似度改进为（１，Ｂ＋Ｉ）一近似。另外， 在特殊图上．ＣｉｅｓｌｉｋＩ￣给出了一些特殊图的度的最 （Ｖ，Ｅ ）为Ｇ的一个子图，要寻找Ｅ的一个子集ＥｆＩ ｃ 收稿日期：２０１２—０３—１６ 修稿日期：２０１２—０４—０１ 作者简介：李睿（１９８３－），男，云南丽江人，硕士，研究方向为组合最优化 现代计算机２０１２．０４ ＼ 研究与开发 ＼ 小支撑树问题的一些情况．在欧氏平面图上．当度的限 制Ｂ是２和３时．求解度的最小支撑树问题是ＮＰ 一难的．当Ｂ＞４时，此问题是多项式可解的。权度的 最小支撑树问题是度的最小支撑树问题的推广． Ｒａｖｉｌ６１￣ｎ出了一个（１ｏｇｎ。ｌｏｇｎ）一近似的算法。后来，Ｆｕ— ｋｕｎａｇａ和ＮａｇａｍｏｃｈｉＩ７ｔ￣出了（１，４）一近似的算法，并将 其推广应用到满足三角不等式的最小权度支撑树问题 上．得到一个４一近似的算法 ３ 算法 首先讨论Ｅ ＝ 的情况。当Ｅ ＝ 时，上面问题可描 述为： 给定Ｇ＝（Ｖ，Ｅ；ｗ），ｗ：Ｅ—Ｑ ，要寻找Ｇ的一个支撑 子图Ｔ． 目标：ｍｉｎｍａｘｗｄ（ｖ）。 其中ｗｄ（ｖ）＝ ∑ （ｅ）。 ＂是ｅ的一个端点 为解决Ｅ ：０的最小权度的网络构建问题．我们设 计了如下的算法： 算法１（ＭＷＤＮＤ１） 输入：无向图Ｇ：（Ｖ，Ｅ；ｗ）。 输出：图Ｇ的一个支撑子图Ｔ。 Ｂｅｇｉｎ ①Ａ（ｖｉ）＝０，ｉ＝ｌ，２，…，ｎ，Ｅ”＝ ； ②判断Ｔ：（Ｖ，Ｅ”）是否为连通图。若Ｔ连通，停止， 输出ｍａｘ｛Ａ（Ｖｉ）ｌ及Ｔ＝（Ｖ，Ｅ”）； ③在Ｖ中选取使得 （ｖｉ）最小的点 （ｖｉ）＝ｍｉｎ｛ｈ （ｖ．）｝，在ｖｊ所关联的边Ｅ ＝（。 ＥＥ—Ｅ．ｔｌｖｉ，ｖｊ位于不同的 连通分图｝中，选取使得ｍａｘ｛ｈ（ｖ。）＋ｗ ，Ｘ（ｖｊ）＋ｗ ｌ达到最 小的边，不妨设为ｅ＝ｖｋｖ；； ＤＡ ｖｋ）＝ （ｖｋ）＋ｗ ，Ｘ（ｖｊ）： （ｖＪ）＋ｗ ，Ｅ”＝Ｅ”ｕ｛ＶｋＶｊ｝， 转②。 Ｅｎｄ 上面的算法能在Ｏ（ｎｚ）时间内得到一个可行解，并 且可以推广出下面算法： 算法２（ＭＷＤＮＤ２） 输入：无向图Ｇ＝（Ｖ，Ｅ；Ｗ）。 输出：图Ｇ的一个支撑子图Ｔ。 Ｂｅｇｉｎ ④Ａ（Ｖｉ）＝０，ｉ＝ｌ，２，…，ｎ，Ｅ”＝ ； ＠ 现代计算机２０１２．０４ ②判断 ｒ＝（Ｖ，Ｅ”）是否为连通图。若Ｔ连通，转⑤； ③在Ｖ中选取使得 （ｖ。）最小的点 （ｖ ）＝ｍｉｎ｛ｋ （Ｖｉ）ｌ，在ｖ 所关联的边中，选取使得ｍａｘ｛ｈ（ｖ。）＋ｗｉｊ， ｖ ）＋ｗ 达到最小的边，不妨设为ｅ￣ＶｋＶ ； ９Ａ（Ｖｋ）＝ （ＶＫ）＋Ｗ ， （ｖｊ）＝ｋ（ｖｊ）＋ｗ ，Ｅ”＝Ｅ”ｕ｛Ｖｋｖｊ｝， 转②。 ⑤判断当前得到的图Ｇ中是否有圈。若Ｇ中无 圈，停止，输出ｍａｘ｛Ｘ（ｖｉ）｝及Ｔ＿（Ｖ，Ｅ”）； ⑥若⑤中得到一个圈Ｃ，则选取圈ｃ上Ｘ（ｖ。）最大 的点．并去掉圈上跟它关联的两条边中权重最大者．Ｔ＝ Ｔ｛ｅ１，转⑤。 Ｅｎｄ 算法２能在Ｏ（ｍｎ）时间内得到一个可行解．并且 得到的可行解比算法１的精确度要高 ４ 结语 本文给出了最小权度的网络构建问题的两个算 法．该算法可用于解决实际工作中的一些相关问题．特 别是在一些大规模的管理规划中．其可行解是比较接 近最优解的．具有一定的实际意义 算法中我们只给出 了Ｅ，＿ 的情况．若Ｅ”＝ ．则问题实际上是Ｅ，＿ 中的 一种特殊情况．进而可以用本文中所给出的算法求解。 但如果我们对一部分点进行收缩．可能得到一个多重 图．这样在我们选边的过程中可能更容易选到较小的 边．那么又应该如何选择满足条件的边并对其进行调 整？在今后的学习中．我们将着重考虑这方面的问题， 同时寻找与此相关的一些问题，把它概括为更一般地、 更合乎实际的问题模型．然后加以解决 参考文献 ［ＨＭ．Ｆｒｉｅｒ，Ｂ．Ｒａｇｈａｖａｃｈａｒｉ．Ａｎ ＮＣ Ａｐｐｒｏｘｉｍａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ Ｍｉｎｉｍｕｎ Ｄｅｇｒｅｅ Ｓｐａｎｎｉｎｇ Ｔｒｅｅ Ｐｒｏｂｌｅｍ［Ｒ］．Ｉｎ：Ｐｒｏｃ． ｏｆ ｔｈｅ ２８ｔｈ Ａｎ Ａｌｌｅｒｔｏｎ Ｃｏｎｆ￣ ｒｅｎｃｅ ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎ，Ｃｏｎ— ｔｒｏｌ ａｎｄ Ｃｏｍｐｕｔｉｎｇ，１９９０，：２７４－２８１ 【２１Ｍ．Ｇｈｏｄｓｉ，Ｈ．Ｍａｈｉｎｉ，Ｋ．Ｍｉｒｊａｌａｌｉ，Ｓ．Ｏ．Ｇｈａｒａｎ，Ａ．Ｓ．Ｓａｙｅｄｉ， Ｍ．Ｚａｄｉｍｏｇｈａｄｄａｍ．Ｓｐａｎｎｉｎｇ Ｔｒｅｅ ｗｉｔｈ Ｍｉｎｉｍｕｍ Ｗｅｉｇｈｔｅｄ Ｄｅｇｒｅｅｓ『Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｌｅｔｔｅｒｓ，２００７，１０４：１ １３ ｌ１６ ［３］Ｍ．Ｘ．Ｇｏｅｍａｎｓ．Ｍｉｎｉｍｕｍ Ｂｏｕｎｄｅｄ Ｄｅｇｒｅｅ Ｓｐａｎｎｉｎｇ Ｔｒｅｅｓ［Ｊ］． Ｐｒｏｃｅｅｄｉｎｇ ｏｆ ｔｈｅ ４７ｔｈ Ａｎｎｕａｌ ＩＥＥＥ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｆｏｕｎｄａ—— ｔｉｏｎｓ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，２００６：２７３－２８２ 硒究与开发 ————————————．———————— ———————————— ———— ———————————————— ———— ———————— ——— ———————．．．．／ ／ ／ ／ ／ ［４］Ｍ．Ｓｉｎｇｈ，Ｌ．Ｃ．Ｌａｕ．Ａｐｐｒｏｘｉｍａｔｉｎｇ Ｍｉｎｉｍｕｍ Ｂｏｕｎｄｅｄ Ｄｅｇｒｅｅ Ｓｐａｎｎｉｎｇ Ｔｒｅｅｓ ｔｏ Ｗｉｔｈｉｎ Ｏｎｅ ｏｆ Ｏｐｔｉｍａｌ［Ｊ］．Ｉｎ：Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ３９ｔｈ ＡＣＭ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｔｈｅｏｒｙ ｏｆ Ｃｏｍｐｕｔｉｎｇ，２００７： ６６１—６７０ ［６］Ｒ．Ｒａｖｉ．Ｓｔｅｉｎｅｒ Ｔｒｅｅｓ ａｎｄ Ｂｅｙｏｎｄ：Ａｐｐｒｏｘｉｍａｔｉｏｎ Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ Ｎｅｔｗｏｒｋ Ｄｅｓｉｇｎ［Ｄ］．Ｐｈ．Ｄ．Ｔｈｅｓｉｓ，Ｄｅｐａｔｒｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｂｒｏｗｎ Ｕｎｉｖｅｒｓｉｔｙ，１９９３ ［７］Ｔ．Ｆｕｋｕｎｎｇａ，Ｈ．Ｎａｇａｍｏｃｈｉ．Ｎｅｔｗｏｒｋ Ｄｅｓｉｇｎ ｗｉｔｈ Ｗｅｉｇｈｔｅｄ Ｄｅｇｒｅｅ Ｃｏｎｓｔｒａｉｎｔｓ ｆＪ］．Ｄｉｓｃｒｅｔｅ Ｏｐｔｉｍｉｚａｔｉｏｎ，２０１０，７：２４６～ ２５５ ［５］Ｄ．Ｃｉｅｓｌｉｋ．Ｔｈｅ Ｖｅｒｔｅｘ Ｄｅｇｒｅｅ ｏｆ Ｍｉｎｉｍｕｍ Ｓｐａｎｎｉｎｇ Ｔｒｅｅｓ［Ｊ］． Ｅｕｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅｒａｔｉｏｎａｌ Ｒｅｓｅａｒｃｈ，２０００，１２５：２７８～ ２８２ Ｎｅｔｗｏｒｋ Ｃｏｎｓｔｒｕｃｔｉｏｎ Ｐｒｏｂｌｅｍ ｏｆ Ｍｉｎｍｕｍ Ｗｅｉｇｈｔｅｄ Ｄｅｇｒｅｅ ＬＩ Ｒｕｉ ． ＬＶ Ｘｉａｏ－ｊＵＢ （Ｃｏｌｌｅｇｅ ｏｆ Ｔｏｕｒｉｓｍ ａｎｄ Ｃｕｌｔｕｒｅ，Ｙｕｎｎａｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｌｉｊｉａｎｇ ６７４１００） Ａｂｓｔｒａｃｔ： Ｎｅｔｗｏｒｋ ｃｏｎｓｔｒｕｃｔｉｏｎ ｐｒｏｂｌｅｍ ｉｓ ａ ｃｌａｓｓｉｃ ｏｎｅ ｉｎ ｃｏｍｂｉｎａｔｏｒｉａｌ ｏｐｔｉｍｉｚａｔｉｏｎ．ａｎｄ ｔｈｅ ｃｏｎｎｅｃｔｉｖｉ— ｔｙ ｐｒｏｂｌｅｍ ｉｓ ｏｎｅ ｏｆ ｔｈｅ ｍｏｓｔ ｉｍｐｏｒｔａｎｔ ｐｒｏｂｌｅｍｓ ｉｎ ｎｅｔｗｏｒｋ ｃｏｎｓｔｒｕｃｔｉｏｎ．Ｗｅ ｃｏｎｓｉｄｅｒ ｔｈｅ ｆｏｌ・ ｌｏｗｉｎｇ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ｍｏｄｅｌ：ｇｉｖｅｓ ａ ｎｏｎｄｉｇｒａｐｈ Ｇ ：（Ｖ，Ｅ；ｗ）ａｎｄ ｉｔｓ ｓｕｂｇｒａｐｈ Ｇ ＝（Ｖ， Ｅ ），ｗ：Ｅ— Ｑ ｉｓ ａ ｃｏｓｔ－ｆｕｎｃｔｉｏｎ．Ｗｅ ａｒｅ ａｓｋｅｄ ｔｏ ｉｆｎｄ ａ ｓｕｂｓｅｔ Ｅ”ｃ Ｅ，ａｎｄ ｔｈｅ ｇｒａｐｈ ｉｎｄｕｃｅｄ ｂｙ Ｅ ｕ Ｅ”ｉｓ ｃｏｎｎｅｃｔｅｄ．Ｔｈｅ ｏｂｊｅｃｔ ｉｓ ｔｏ ｍｉｎｉｍｉｚｅ ｔｈｅ ｍａｘｉｍｕｍ ｃｏｓｔ ｏｆ ｆｕｎｃｔｉｏｎ ｗｄ（ｖ），ｗｈｅｒｅ ｗｄ（ｖ）ｉｓ ｔｈｅ ｗｅｉｇｈｔｅｄ ｄｅｇｒｅｅ ｏｆ ｖｅｒｔｅｘ ｖ．Ｂｙ ａｎａｌｙｓｉｎｇ ｔｈｅ ｐｒｏｂｌｅｍ，ｄｅｓｉｇｎｓ ｔｗｏ ｈｅｕｒｉｓｔｉｃ ａｌｇｏ— ｒｉｔｈｍｓ ｔｏ ｓｏｌｖｅ ｔｈｅ ｓｐｅｃｉａｌ ｃｌａｓｓ ｏｆ ｔｈｅ ｐｒｏｂｌｅｍ ｉｆ Ｅ ≠０．ａｎｄ ｔｈｅ ｐｒｏｂｌｅｍ ｃａｎ ｂｅ ｓｉｍｉｌａｒｌｙ ｓｏｌｖｅｄ ｉｆ Ｅ”≠ ． Ｋｅｙｗｏｒｄｓ： Ｎｅｔｗｏｒｋ Ｃｏｎｓｔｒｕｃｔｉｏｎ；Ｓｃａｎｎｉｎｇ Ａｌｇｏｒｉｔｈｍ；Ａｐｐｒｏｘｉｍａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ （上接第７页） Ｓｐｅｅｃｈ—ＤｒｉＶｅｎ Ｌｉｐ Ａｎｉｍａｔｉｏｎ Ｍｅｔｈｏｄ Ｂａｓｅｄ ｏｎ ＳＡＰＩ ＹＡＮＧ Ｍａｏ—ｗｅｉ ， ＺＨＥＮＧ Ｂｏ—ｃｈｕａｎ ，ＧＡＯ Ｃｈｕｎ—ｍｅｉ （１．Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ Ｌａｂｏｒａｔｏｒｙ，Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｓｉｃｈｕａｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｅｎｇｄｕ ６１００６４ ２．Ｃｏｌｌｅｇｅ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ，Ｃｈｉｎａ Ｗｅｓｔ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｃｈｏｎｇ ６３７００２） Ａｂｓｔｒａｃｔ：Ｖｏｉｃｅ—ｌｉｐ ａｎｉｍａｔｉｏｎ ｉｓ ａ ｃｒｕｃｉａｌ ｐａｒｔ ｉｎ ｆａｃｉａｌ ｅｘｐｒｅｓｓｉｏｎ ａｎｉｍａｔｉｏｎ．Ｐｒｅｓｅｎｔｓ ａ ｒｅａｌ，ｎａｔｕｒａｌ ｖｏｉｃｅ ｌｉｐ ａｎｉｍａｔｉｏｎ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｔｈｅ ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ ｂｅｔｗｅｅｎ ｖｏｉｃｅ ａｎｄ ｌｉｐ ａｎｉｍａｔｉｏｎ．Ｔｈｅ ｍｅｔｈｏｄ ｆｉｒｓｔｌｙ ｓｅｇｍｅｎｔｓ ｓｐｅｅｃｈ ｉｎｔｏ ｐｉｅｃｅｓ ｏｆ ｓｍａｌｌ ｓｐｅｅｃｈ，ａｎｄ ｉｄｅｎｔｉｉｆｅｓ Ｃｈｉ． ｎｅｓｅ ｓｅｑｕｅｎｃｅｓ ｂｙ ｕｓｉｎｇ ＳＡＰＩ．Ｔｈｅｎ ｔｒａｎｓｌａｔｅｓ ｔｈｅ Ｃｈｉｎｅｓｅ ｓｅｑｕｅｎｃｅｓ ｉｎｔｏ ｓｙｌｌａｂｌｅ ｓｅｑｕｅｎｃｅｓ， ａｎｄ ｆｉｎａｌｌｙ ｔｒａｎｓｌａｔｅｓ ｔｈｅ ｓｙｌｌａｂｌｅ ｓｅｑｕｅｎｃｅｓ ｉｎｔｏ ｌｉｐ ｓｅｑｕｅｎｃｅｓ ｗｉｔｈ ｌｉｐ ｔｉｍｅ ｉｆｏｒｎｍａｔｉｏｎ．Ｔｈｅ ｒｅａｌ ａｎｄ ｎａｔｕｒａｌ ｅｆｆｅｃｔｓ ｏｆ ｔｈｅ ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ ｂｅｔｗｅｅｎ ｖｏｉｃｅ ａｎｄ ｌｉｐ ａｎｉｍａｔｉｏｎ ａｒｅ ａｂｔａｉｎｅｄ ｔｈｒｏｕｇｈ ｄｒｉｖｉｎｇ ｔｈｅ ｌｉｐ ａｎｉｍａｔｉｏｎ ｏｆ ｔｈｅ ３Ｄ ｆａｃｉａｌ ｍｏｄｅｌ ｂｙ ｔｈｅ ｌｉｐ ｓｅｑｕｅｎｃｅｓ． Ｋｅｙｗｏｒｄｓ：Ｓｐｅｅｃｈ—Ｄｒｉｖｅｎ；ＳＡＰＩ；Ｌｉｐ Ａｎｉｍａｔｉｏｎ；Ｓｐｅｅｃｈ Ｓｅｇｍｅｎｔａｔｉｏｎ；Ｓｐｅｅｃｈ Ｒｅｃｏｇｎｉｔｉｏｎ 现代计算机２０１２．ｏ４
