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

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

【相似文獻(xiàn)】

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

1 周同衡;一個(gè)NP-完全問(wèn)題[J];計(jì)算機(jī)學(xué)報(bào);1986年06期

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

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

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

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

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

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

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

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

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

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

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

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

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

1 孫，

本文編號(hào)：1876517