如何使用回溯法實現(xiàn)網(wǎng)絡(luò)設(shè)計問題算法的設(shè)計
資料介紹
1.問題背景及描述
隨著石油在人們?nèi)粘I钪械膹V泛應(yīng)用,石油公司需要通過管道輸送大量的石油,目前,中國油氣管道正呈現(xiàn)出蓬勃發(fā)展的勢頭,已成為我國第五大運(yùn)輸業(yè),而在石油傳輸網(wǎng)絡(luò)的設(shè)計中通常會遇到最少增壓器的問題,選題中網(wǎng)絡(luò)設(shè)計問題對石油傳輸網(wǎng)絡(luò)最少增壓器的問題有了詳細(xì)的描述,再次,我們選用回溯法來解決這個問題,并對時間復(fù)雜度進(jìn)行了分析和討論。
2.方法介紹
2.1 回溯法的基本思想確定了解空間的組織結(jié)構(gòu)后,回溯法從開始結(jié)點(根節(jié)點)出發(fā),以深度優(yōu)先方法搜索整個解空間,在開始結(jié)點成為活節(jié)點,同時成為當(dāng)前的擴(kuò)展結(jié)點,在當(dāng)前結(jié)點處,搜索向縱深方向移至一個新節(jié)點,這個新節(jié)點成為新的活結(jié)點,并成為當(dāng)前擴(kuò)展結(jié)點,如果在當(dāng)前擴(kuò)展結(jié)點處不能再想縱深方向移動,則當(dāng)前擴(kuò)展結(jié)點就成為死結(jié)點。此時,應(yīng)往回移動(回溯)至最近的或節(jié)點處,并使這個活結(jié)點成為當(dāng)前擴(kuò)展結(jié)點。回溯法以這種工作方式遞歸的在解空間中搜索,直至找到所要求的解或解空間中已無活結(jié)點時為止。
2.2 回溯法的基本步驟
(1)確定問題類型;
(2)確定解空間;
(3)確定解空間的組織結(jié)構(gòu);
(4)從根節(jié)點出發(fā),利用深度優(yōu)先算法來遍歷解空間;
(5)當(dāng)找到答案或只剩下死結(jié)點時,該問題完成。
3.問題分析
本題可以理解為北京石油公司通過管道將石油輸送到其他多個城市石油公司的網(wǎng)絡(luò)結(jié)構(gòu),在這個網(wǎng)絡(luò)結(jié)構(gòu)中,各個石油公司為網(wǎng)絡(luò)的結(jié)點,北京公司為根節(jié)點 S,在運(yùn)輸過程中,需要保持網(wǎng)絡(luò)中最低油壓 Pmin,因此設(shè)置了增壓器,,在設(shè)置增壓器的頂點處油壓可升至 Pmax,油壓從 Pmax 減至 Pmin 可是石油傳輸?shù)木嚯x至少為 d。可建立如圖所示的解空間(0 表示不在該點設(shè)置增壓器,表示在該點設(shè)置增壓器):
声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
- 人工智能-BP神经网络算法的简单实现12次下载
- 基于拓扑和权值的虚拟网络映射算法4次下载
- 可实现RFID网络规划的改进型灰狼算法9次下载
- 基于矩阵分解的网络表示学习算法ANEMF11次下载
- 基于SQAG模型的网络攻击建模优化算法6次下载
- 基于SQAG模型的网络攻击建模优化算法14次下载
- 基于长短时记忆网络的自适应零速检测算法8次下载
- 基于深度神经网络的结构化剪枝算法2次下载
- 回溯的共轭梯度迭代硬阈值算法如何解决迭代次数多重构时间长的问题0次下载
- Viterbi译码器回溯算法实现33次下载
- 求组合问题的不同算法比较分析22次下载
- 模板方法模式在回溯算法中的应用0次下载
- 模板方法模式在回溯算法中的应用20次下载
- 基于回溯的RFID防冲撞算法18次下载
- 一种无回溯的最长前缀匹配搜索算法18次下载
- RVBacktrace RISC-V极简栈回溯组件577次阅读
- 使用NumPy实现前馈神经网络2631次阅读
- 神经网络优化算法有哪些832次阅读
- 基于Python实现随机森林算法1406次阅读
- 一种完全由LLM + 启发式搜索算法结合的TOT算法1827次阅读
- 基于System Generator中实现算法的FPGA设计方案详解1822次阅读
- C语言重解经典回溯算法案例5023次阅读
- 一文详解Linux内核的栈回溯与妙用5593次阅读
- 基于FPGA的Cordic算法实现的设计与验证2941次阅读
- 分支限界法与回溯法算法的详细资料概述7693次阅读
- 五大常用算法之回溯法6069次阅读
- 应用于方向回溯天线阵的分形双极化天线详细教程4595次阅读
- 电路板排列问题 回溯(C语言)6098次阅读
- OpenCV白平衡算法之灰度世界法_OpenCV实现马赛克和毛玻璃滤镜效果6900次阅读
- 一种改进的无线传感器网络非测距定位算法1358次阅读
下載排行
本周
- 1TC358743XBG評估板參考手冊
- 1.36 MB | 330次下載 | 免費(fèi)
- 2開關(guān)電源基礎(chǔ)知識
- 5.73 MB | 11次下載 | 免費(fèi)
- 3嵌入式linux-聊天程序設(shè)計
- 0.60 MB | 3次下載 | 免費(fèi)
- 4DIY動手組裝LED電子顯示屏
- 0.98 MB | 3次下載 | 免費(fèi)
- 5基于FPGA的C8051F單片機(jī)開發(fā)板設(shè)計
- 0.70 MB | 2次下載 | 免費(fèi)
- 651單片機(jī)窗簾控制器仿真程序
- 1.93 MB | 2次下載 | 免費(fèi)
- 751單片機(jī)大棚環(huán)境控制器仿真程序
- 1.10 MB | 2次下載 | 免費(fèi)
- 8基于51單片機(jī)的RGB調(diào)色燈程序仿真
- 0.86 MB | 2次下載 | 免費(fèi)
本月
- 1OrCAD10.5下載OrCAD10.5中文版軟件
- 0.00 MB | 234315次下載 | 免費(fèi)
- 2555集成電路應(yīng)用800例(新編版)
- 0.00 MB | 33566次下載 | 免費(fèi)
- 3接口電路圖大全
- 未知 | 30323次下載 | 免費(fèi)
- 4開關(guān)電源設(shè)計實例指南
- 未知 | 21549次下載 | 免費(fèi)
- 5電氣工程師手冊免費(fèi)下載(新編第二版pdf電子書)
- 0.00 MB | 15349次下載 | 免費(fèi)
- 6數(shù)字電路基礎(chǔ)pdf(下載)
- 未知 | 13750次下載 | 免費(fèi)
- 7電子制作實例集錦 下載
- 未知 | 8113次下載 | 免費(fèi)
- 8《LED驅(qū)動電路設(shè)計》 溫德爾著
- 0.00 MB | 6656次下載 | 免費(fèi)
總榜
- 1matlab軟件下載入口
- 未知 | 935054次下載 | 免費(fèi)
- 2protel99se軟件下載(可英文版轉(zhuǎn)中文版)
- 78.1 MB | 537798次下載 | 免費(fèi)
- 3MATLAB 7.1 下載 (含軟件介紹)
- 未知 | 420027次下載 | 免費(fèi)
- 4OrCAD10.5下載OrCAD10.5中文版軟件
- 0.00 MB | 234315次下載 | 免費(fèi)
- 5Altium DXP2002下載入口
- 未知 | 233046次下載 | 免費(fèi)
- 6電路仿真軟件multisim 10.0免費(fèi)下載
- 340992 | 191186次下載 | 免費(fèi)
- 7十天學(xué)會AVR單片機(jī)與C語言視頻教程 下載
- 158M | 183279次下載 | 免費(fèi)
- 8proe5.0野火版下載(中文版免費(fèi)下載)
- 未知 | 138040次下載 | 免費(fèi)
評論