網(wǎng)絡(luò)優(yōu)化及實例ppt課件(已修改)
2025-05-15 01:56 本頁面
【正文】 網(wǎng)絡(luò)優(yōu)化與優(yōu)化 算法 例：中國郵遞員問題 (CPPChinese Postman Problem) 一名郵遞員負責(zé)投遞某個街區(qū)的郵件 . 如何設(shè)計一條最短的投遞路線 (從郵局出發(fā) ， 經(jīng)過投遞區(qū)內(nèi)每條街道至少一次 ，最后返回郵局 )？ 由于這一問題是我國學(xué)者 管梅谷 教授 1960年首先提出的 ， 所以國際上稱之為中國郵遞員問題 . 一、網(wǎng)絡(luò)優(yōu)化及實例 ?單向？ ?雙 向？ ? 歐拉把哥尼斯堡七橋問題轉(zhuǎn)化為一個圖論上的問題： 七橋問題 答案 的 是 否定的 因為圖中沒有偶度頂點 有些問題目前找不到現(xiàn)成的軟件 ? 也沒有快速求解最優(yōu)解的方法 }21{ nI ，， ??TSP（ Travel Sales Man Problem）問題 例 4 設(shè)有城市集合 ，城市 ij到城市 的費用為 ，ijc nji ,1, ??求從指定城市出發(fā)，經(jīng)過所有其他城市恰好 一次，且使總費用最少的旅行路線。 ?TSP問題可以通過枚舉的方法用計算機求解 ? 不同的路線共有 (n1)！條 枚舉城市數(shù)與計算時間的關(guān)系 城市數(shù) 24 25 26 27 28 29 30 31 計算時間 1s 24s 10m 325a 當城市個數(shù)增大到一定數(shù)量時枚舉方法 行不通 ? ? ?! 二、最優(yōu)算法與近似算法 ? 有一些問題在計算復(fù)雜性上被稱做 NP困難問題 ,對
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1