计算机科学 ›› 2014, Vol. 41 ›› Issue (8): 70-74.doi: 10.11896/j.issn.1002-137X.2014.08.015
• 2013年全国理论计算机科学学术年会 • 上一篇 下一篇
董高秀,凌珊,陈卫东
DONG Gao-xiu,LING Shan and CHEN Wei-dong
摘要： 针对无线网络中寻找从源点s到汇点t的两条非干扰不相交路径这一NP难问题,提出了一种拟人算法。该算法首先基于网络流方法得到两条点不相交的s-t路径,然后通过一种拟人化的策略逐步调整这两条路径,力图使得它们变为两条非干扰不相交的s-t路径。模拟实验表明,与现有的算法相比,拟人算法可以快速地以更高的概率找到两条长度较短的非干扰不相交路径。
| [1] Rabin M O．Efficient dispersal of information for security,load balancing,and fault tolerance[J]．Journal of the ACM,1989,36 (2):335-348 [2] Hsu D F,Lyuu Y D．A graph-theoretical study of transmission delay and fault tolerance [J]．International Journal of Mini and Microcomputers,1994,16 (1):35-42 [3] Kleinberg J．Approximation algorithms for disjoint paths problems[D]．MIT,Cambridge,MA,May 1996 [4] Li C,McCormick T,Simich-Levi D．The complexity of finding two disjoint paths with min-max objective function [J]．Discrete Applied Mathematics,1989,26(1):105-115 [5] Xu D,Chen Y,Xiong Y,et al．On the complexity of and algorithms for finding the shortest path with a disjoint counterpart [J]．IEEE/ACM Transactions on Networking,2006,14(1):147-158 [6] 张品,章坚武,李乐民,等．QoS 约束下的链路分离路径问题研究 [J]．通信学报,2006,27(6):36-42 [7] 熊轲,裘正定,郭宇春,等.多约束最短链路分离路径精确算法[J]．软件学报,2010,21(7):1744-1757 [8] 方效林,石胜飞,李建中.无线传感器网络一种不相交路径路由算法[J]．计算机研究与发展,2009,46(12):2053-2061 [9] Voigt T,Dunkels A,Braun T．On-Demand construction of non-interfering multiple paths in wireless sensor networks[C]∥Proceedings of the 2nd Workshop on Sensor Networks at Informatik 2005．Bonn,Germany,2005:150-154 [10] Kawarabayashi K,Kobayashi Y．The induced disjoint pathsproblem[C]∥Proceedings of the 13th Integer Programming and Combinatorial Optimization(LNCS5035)．Bertinoro,Italy,Springer,2008:47-61 [11] Zhang Ke-jia,Gao Hong,Li Jian-zhong．Finding multiple induced disjoint paths in general graphs[J]．Information Processing Letters,2011,111:1022-1026 [12] Teo J Y,Ha Y,Tham C K．Interference-Minimized MultipathRouting with Congestion Control in Wireless Sensor Network for High-Rate Streaming[J]．IEEE Transations on Mobile Computing,2008,7:1124-1137 [13] Marathe M V,Breu H,Hunt H B,et al．Simple heuristics for unit disk graphs[J]．Networks,1995,25(2):59-68 [14] 黄文奇,金人超．求解SAT问题的拟物拟人算法—Solar [J]．中国科学(E辑),1997,27(2):179-186 [15] Huang Wen-qi,He Kun．A pure quasi-human algorithm for solving the cuboid packing problem[J]．Science in China Series F:Information Sciences,2009,52(1):52-58 [16] 黄文奇,许如初．近世计算理论导引—NP难度问题的背景、前景以及其求解算法研究[M].北京:科学出版社,2004:47-70 |
| No related articles found! |
|
||
首页