mafia淺析ppt課件-資料下載頁(yè)
2025-05-01 23:39本頁(yè)面
【正文】 4448 593 ? maf15b 200 355 31 ? maf15c 200 18588 2672 完全版？ 算法復(fù)雜性分析 ? EdmondsKarp算法的時(shí)間復(fù)雜度為O(NM2) ? 廣度優(yōu)先搜索尋找連通分量的時(shí)間復(fù)雜度不超過(guò) O(N+M)； ? 時(shí)間復(fù)雜度的主要因素還是計(jì)算網(wǎng)絡(luò)流算法的耗時(shí) 網(wǎng)絡(luò)流的廣泛應(yīng)用 ? 網(wǎng)絡(luò)最大流在工程技術(shù)中的應(yīng)用非常廣泛 ? 水資源調(diào)度，配電網(wǎng)計(jì)算， ? 交通網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)，物流配送等 ? 甚至音樂(lè)作曲上也有涉及 ? 大調(diào)音階和弦進(jìn)行圖 網(wǎng)絡(luò)流與作曲 ? 確定要作的曲子的風(fēng)格。 ? 通過(guò)各個(gè)和弦與主和弦的相關(guān)度（依風(fēng)格不同而各異，從庫(kù)中調(diào)用）確定權(quán)重。 ? 確定起點(diǎn)，按最大流問(wèn)題求解。 ? 將求得的最小割包含的弧兩端的和弦按一定規(guī)律進(jìn)行組合，即可得到音樂(lè)作品。 ? 可見，若將網(wǎng)絡(luò)流模型引入樂(lè)曲創(chuàng)作，或許可以開辟出算法作曲的另一條蹊徑。 ? 網(wǎng)絡(luò)流算法是一種高效實(shí)用的算法 ? 相對(duì)于其它圖論算法來(lái)說(shuō)，模型更加復(fù)雜，編程復(fù)雜度也更高。 ? 但是它綜合了圖論中的其它一些算法，因而適用范圍也更廣，經(jīng)常能夠很好地解決一些搜索與動(dòng)態(tài)規(guī)劃無(wú)法解決的，看似 NP的問(wèn)題。 ? 最小割是最大流的對(duì)偶問(wèn)題。 ? 但在實(shí)際建模過(guò)程中，最小割不如最大流表現(xiàn)的直觀（更為抽象），模型也往往隱蔽得很深，不容易找到構(gòu)圖方法。 ? 需要根據(jù)具體問(wèn)題具體分析，通過(guò)研究最小割模型的一些實(shí)際應(yīng)用，揭示和掌握最小割模型應(yīng)用的構(gòu)圖方法與思維方式。 ? 建立原問(wèn)題與最小割的一一對(duì)應(yīng)關(guān)系是求解方法的必要步驟。 ? 將原問(wèn)題的決策方案與具有特定性質(zhì)的割，構(gòu)造性地一一對(duì)應(yīng)起來(lái)，并且保證具有該特定性質(zhì)的割一定能被最小割取到。便可成功地將模型進(jìn)行轉(zhuǎn)化。 ? 具體問(wèn)題中的應(yīng)用，最具挑戰(zhàn)性的部分是模型的構(gòu)造。 ? 一般而言并無(wú)現(xiàn)成的模式可以套用，需要對(duì)各種網(wǎng)絡(luò)流的性質(zhì)了如指掌（比如結(jié)點(diǎn)可以有容量、容量有上下限、可以有多重邊等等） ? 注意歸納總結(jié)，發(fā)揮我們的創(chuàng)造性。 參考文獻(xiàn) ? BOI’2021 Tasks and Solutions. ? Introduction to Algorithms 【 美 】Thomas ， Charles ? A Friendly Introduction to Graph Theory, Fred Buckley, Marty Lewinter
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1