acm算法淺談圖論模型的建立與應(yīng)用-資料下載頁
2025-10-07 19:05本頁面
【正文】 本題的卡片總數(shù)有十萬之多，而最終要選取的卡片數(shù)不超過 100張。如果在構(gòu)圖之前，把沒有用的卡片先刪掉，必將大大提高效率。 什么樣的卡片是沒有用的呢？ 先考慮第一種能力的選?。喝绻讶靠ㄆ吹谝环N能力值從大到小排序，顯然我們應(yīng)該盡量從前面選 A張出來，由于每張卡片只能使用一次，所以有可能會(huì)和其他的兩種能力發(fā)生沖突，而沖突的卡片數(shù)最多是 B+C張，所以實(shí)際上對我們有用的卡片只是前面的 A+B+C張。 優(yōu)化 例題 3 貪婪之島 （ ZOJ） 同理，對于第二種和第三種能力的選取，也只需保留其能力值最大的前 A+B+C張卡片。這一步可以在線性時(shí)間內(nèi)解決。 這是一個(gè)既簡單又有效的方法，經(jīng)過這一步處理，保留下來的卡片數(shù)不會(huì)超過 3(A+B+C)張，頂點(diǎn)數(shù)大大減少，求解最大費(fèi)用最大流的時(shí)間復(fù)雜度降為 O((A+B+C)3)。 至此，算法已經(jīng)優(yōu)化到了一個(gè)可以接受的地步，時(shí)間復(fù)雜度僅為 O(N+(A+B+C)3)。 優(yōu)化 例題 3 貪婪之島 （ ZOJ） 如果還要進(jìn)一步提高效率，可以用更有效的算法刪掉多余的頂點(diǎn)。不過這樣做意義不大，而且也不是本文討論的要點(diǎn)。 另外，本題還可以轉(zhuǎn)化為二部圖模型，用最佳匹配算法求解。這一步留給讀者自己思考。 小結(jié) 例題 3 貪婪之島 （ ZOJ） 本題建立的是網(wǎng)絡(luò)流模型。這類模型的算法系數(shù)大，編程復(fù)雜度也大，在競賽中往往作為走投無路時(shí)的 “ 候補(bǔ)算法 ” 。但是，網(wǎng)絡(luò)流模型的適用性廣，一些較復(fù)雜，或者約束較多的問題，網(wǎng)絡(luò)流模型可以很好地解決，而基于網(wǎng)絡(luò)流模型的問題又比較明顯，這使得網(wǎng)絡(luò)流模型有著廣泛的應(yīng)用。 結(jié)語 問題是千變?nèi)f化的，如何建立問題的圖論模型并沒有通用的準(zhǔn)則。前面的幾個(gè)例子都比較簡單，在更復(fù)雜的問題中，有時(shí)我們會(huì)感到難以建立適當(dāng)?shù)哪Ｐ停@時(shí)，我們需要在不改變問題原型本身的性質(zhì)的前提下，對原型進(jìn)行抽象，簡化，在此基礎(chǔ)上建立合適，有效的模型。有時(shí)，我們建立了問題的一個(gè)模型之后，可能會(huì)感到難以求解，這時(shí)，我們可能需要對模型進(jìn)行修改，轉(zhuǎn)化，或者對原型進(jìn)行更深入的分析，抽取其中較關(guān)鍵的要素，建立一個(gè)易于求解的模型。這些都需要我們有豐富的經(jīng)驗(yàn)，靈活的思維以及良好的創(chuàng)造力。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1