文档介绍：带约束路由问题的扑阊芯与应用湖南大学硕士学位论文鹳鎏峤荒科冢生§目论文答避旦期;生学校代号:密级:普通学号:
帅Ⅲ唧㈣椰—●胛瓻.
作者虢孝施训,嗍:伽年尹眇日湖南大学学位论文原创性声明学位论文版权使用授权书今秒年伊日曷拊本人郑重声明:所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外,本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。本学位论文作者完全了解学校有关保留、使用学位论文的规定,同意学校保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。年解密后适用本授权书。朐谝陨舷嘤Ψ娇蚰诖颉啊獭本学位论文属于作者签名:导师签名:⒈C芸冢⒉槐C芸凇期:骹
摘要带约束路由算法问题一直是通信领域的热点问题。然而,,除非,否则无法给出多项式时间算法。对于这些问题,已经出现各种伪多项式算法,但这些算法必须在一定的限制条件内才能保证算法时间效率。年┦渴状翁岢隽薉计算的概念,并设计了惴ǔ功解决了龆サ愕墓芏俾肪段侍猓允玖薉计算解决复杂问题的巨大潜力。由于路由问题的特点,可以利用扑愀叨鹊牟⑿行越侍獾氖奔涓丛佣转化为肿恿吹目占涓丛佣龋佣诙嘞钍绞奔淠诘贸鑫侍獾木方狻1疚提出一套通用的路由问题的嗦敕桨福⒍粤街痔厥獾拇际酚晌侍饨扑闼惴ㄉ杓啤指定结点路由问题可一般性地定义为带指定结点约束的最短路径问题,是一个难问题。本文提出一种将电子计算机算法与扑闼惴ㄏ嘟岷系姆椒ㄇ蠼指定结点路由问题。算法由转化算法,源宿结点搜索切割算法,转化图结果搜索算法和结果读取算法共四个子算法组成。分析结果表明:执行算法的电子计算机部分可显著减少参与生化反应的吹氖浚谑怨苣贒链数恒定的情况下,增加了可解决问题的结点和链路的规模。算法的扑悴糠侄宰疃搪肪督行并行搜索,可以在多项式时间内得出问题的解。链路分离路径对可用于保障网络传输稳定性,增加传输带宽和实现负载均衡。本文对计算链路分离路径对的电子计算机算法惴ń兴惴ㄓ呕慕提出基于扑愕母咝Р⑿兴惴ā8盟惴ㄖ饕S勺疃搪肪端阉魉惴ǎ肪斗掷算法,链路分离路径构造算法组成。在扑阒校梢越獿算法中多个需要指数时间复杂度的操作改进为多项式时间。本文主要探讨了扑阏攵粤街痔囟ㄔ际酚晌侍獾乃惴ǎ⑽F渌由问题的扑惚嗦牒突静僮魈峁┝送ㄓ梅桨浮V灰N蠢垂赜贒计算的生物技术走向成熟,扑阃耆ǹ梢栽诼酚晌侍庵蟹⒒痈蟮淖饔谩关键词:扑悖恢付ń岬懵酚桑涣绰贩掷肼肪叮完全问题带约束路由问题的扑阊芯俊甶应用
..甅,畉.—琤琣瑆瓸,甋..甌猘,,.瓵.,瓵瑀