利用光纤网络求解典型的NP完全问题

发布时间：2018-05-12 01:27

本文选题：光纤网络 + NP完全问题　；参考：《北京交通大学》2017年硕士论文

【摘要】：随着信息时代人们对通信容量及通信质量要求的日益提高,光纤通信的重要地位日益凸显,为了能够将光纤传输的特性应用于更多的领域,在本文中,通过搭建由LD,调制器,脉冲发生器,光耦合器,EDFA,普通光纤等组成的光纤网络,选择了 NP完全问题这一数学界的代表性难题进行求解,具体的工作如下:(1)以哈密尔顿回路和旅行商问题这两个典型NP完全问题为代表,搭建由LD,调制器,脉冲发生器,光耦合器,EDFA,普通光纤等组成的光纤网络,利用该网络分别求解了 6节点和9节点的哈密尔顿回路,以及6节点和9节点的旅行商问题。利用输入脉冲代表行人,不同的耦合器则代表不同的城市。(2)通过设置各个耦合器的输入光纤长度不同而引进不同的时间延迟来代表到达不同城市所需的时间的不同,输入的脉冲经所给定地图输出,通过输出脉冲的延迟时间以及振幅的变化来分析问题并寻求问题的最终解。(3)本文的第二章和第三章分别利用该方法从实验的角度上求解了哈密尔顿回路问题和旅行商问题,并通过穷举法验证了该方法的准确性及可行性,为求解NP完全问题提供了又一新的方法思路。同时,旅行商问题作为组合优化问题中的典型难题,通过求解TSP这一典型的组合优化问题,为现实生活中的组合优化问题,如波长分配和路由选择问题提供了理论上的又一方案。
[Abstract]:With the increasing requirements of communication capacity and communication quality in the information age, the important position of optical fiber communication is increasingly prominent. In order to be able to apply the characteristics of optical fiber transmission to more fields, in this paper, by building LDD, modulator, The optical fiber network composed of pulse generator, optical coupler EDFAand ordinary optical fiber has chosen the NP complete problem, which is a representative problem in the field of mathematics, to be solved. The specific work is as follows: (1) taking the Hamilton circuit and the traveling salesman problem as representatives of two typical NP-complete problems, an optical fiber network consisting of LDD, modulator, pulse generator, optical coupler EDFA, ordinary optical fiber, etc. The network is used to solve the Hamiltonian loop with 6 and 9 nodes, and the traveling salesman problem with 6 and 9 nodes respectively. Using input pulses to represent pedestrians and different couplers to represent different cities.) different time delays are introduced by setting different input fiber lengths for each coupler to represent the difference in the time required to arrive in different cities. The input pulse is output from the given map, The second and third chapters of this paper use this method to solve the Hamiltonian loop problem and the traveling salesman problem from the experimental point of view, respectively. The accuracy and feasibility of the method are verified by exhaustive method, which provides a new method for solving NP complete problem. At the same time, as a typical problem in combinatorial optimization problem, traveling salesman problem (TPS) is a real life combinatorial optimization problem by solving TSP, a typical combinatorial optimization problem. For example, wavelength assignment and routing problems provide another theoretical scheme.
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TN929.11

【相似文献】