本文選題：光纖網(wǎng)絡(luò) + NP完全問題�。� 參考：《北京交通大學(xué)》2017年碩士論文

【摘要】：隨著信息時代人們對通信容量及通信質(zhì)量要求的日益提高,光纖通信的重要地位日益凸顯,為了能夠?qū)⒐饫w傳輸?shù)奶匦詰?yīng)用于更多的領(lǐng)域,在本文中,通過搭建由LD,調(diào)制器,脈沖發(fā)生器,光耦合器,EDFA,普通光纖等組成的光纖網(wǎng)絡(luò),選擇了 NP完全問題這一數(shù)學(xué)界的代表性難題進行求解,具體的工作如下:(1)以哈密爾頓回路和旅行商問題這兩個典型NP完全問題為代表,搭建由LD,調(diào)制器,脈沖發(fā)生器,光耦合器,EDFA,普通光纖等組成的光纖網(wǎng)絡(luò),利用該網(wǎng)絡(luò)分別求解了 6節(jié)點和9節(jié)點的哈密爾頓回路,以及6節(jié)點和9節(jié)點的旅行商問題。利用輸入脈沖代表行人,不同的耦合器則代表不同的城市。(2)通過設(shè)置各個耦合器的輸入光纖長度不同而引進不同的時間延遲來代表到達(dá)不同城市所需的時間的不同,輸入的脈沖經(jīng)所給定地圖輸出,通過輸出脈沖的延遲時間以及振幅的變化來分析問題并尋求問題的最終解。(3)本文的第二章和第三章分別利用該方法從實驗的角度上求解了哈密爾頓回路問題和旅行商問題,并通過窮舉法驗證了該方法的準(zhǔn)確性及可行性,為求解NP完全問題提供了又一新的方法思路。同時,旅行商問題作為組合優(yōu)化問題中的典型難題,通過求解TSP這一典型的組合優(yōu)化問題,為現(xiàn)實生活中的組合優(yōu)化問題,如波長分配和路由選擇問題提供了理論上的又一方案。
[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.
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TN929.11

【相似文獻】

相關(guān)期刊論文 前10條

1 周同衡;一個NP-完全問題[J];計算機學(xué)報;1986年06期

2 唐曉芬;;生物信息學(xué)中的NP-完全問題研究綜述[J];計算機與現(xiàn)代化;2013年08期

3 郝克剛;;NP完全問題及有關(guān)的理論研究[J];計算機科學(xué);1980年01期

4 許道云;王曉峰;;一個正則NP-完全問題及其不可近似性[J];計算機科學(xué)與探索;2013年08期

5 呂義忠,孫慧澄;關(guān)于NP完全問題的多項式線路可判定性[J];南京航空航天大學(xué)學(xué)報;1996年05期

6 R.Schroeppel ,A.Shamir ,向生建;對某些NP完全問題的T·S~2=0(2~n)時/空權(quán)衡[J];通信保密;1989年01期

7 馬垣,劉剛,張小平,李曉瑞,張紅云;分子計算機的誕生與現(xiàn)狀[J];鞍山鋼鐵學(xué)院學(xué)報;2002年02期

8 韓臘萍,李燕;DNA計算方法在求解NP完全問題中的應(yīng)用[J];華北工學(xué)院學(xué)報;2003年04期

9 周金鳳;;DNA計算在求解NP-完全問題的應(yīng)用[J];科技視界;2012年35期

10 Michael R.Garey ;David S.Johnson;沈泓;;NP-完全問題匯編[J];計算機工程與應(yīng)用;1981年07期

相關(guān)會議論文 前2條

1 姜新文;;MSP問題及其求解研究[A];中南六�。▍^(qū)）自動化學(xué)會第24屆學(xué)術(shù)年會會議論文集[C];2006年

2 吳學(xué)江;;利用膨脹圖求解SAT問題[A];中國通信學(xué)會第五屆學(xué)術(shù)年會論文集[C];2008年

相關(guān)碩士學(xué)位論文 前5條

1 孫，

本文編號：1876517