算法合集之淺談圖論模型的建立與應用-wenkub
2022-10-31 20:33:41 本頁面
【正文】 2 1 1 2 3 4 6 5 7 8 于是，問題轉(zhuǎn)化為求圖的最大獨立集問題。 例題 1 Place the Robots（ ZOJ） 問題描述 有一個 N*M(N,M=50)的棋盤，棋盤的每一格是三種類型之一：空地、草地、墻。淺談圖論模型的建立與應用 廣東省中山市第一中學 黃源河 引言 ? 圖論是數(shù)學的一個有趣的分支。機器人只能放在空地上。 在問題的原型中，草地，墻這些信息不是我們所關心的，我們關心的只是空地和空地之間的聯(lián)系。我們把這些塊編上號。 例題 1 Place the Robots（ ZOJ） 模型二 1 2 3 4 1 2 3 5 4 1 1 2 2 3 3 4 4 5 比較前面的兩個模型：模型一過于簡單，沒有給問題的求解帶來任何便利；模型二則充分抓住了問題的內(nèi)在聯(lián)系，巧妙地建立了二部圖模型。一天中每個小時需要出納員的最少數(shù)量為 R0,R1,R2,...,R23。然而，對于本題，這些算法都無能為力。我們要求 S[23]的最小值，就是要求頂點0到頂點 23的最短路。 至于 S[23]，我們可以用二分法枚舉，逐步縮小范圍，用迭代法判斷是否存在負權回路（判定可行性），最終求得S[23]的最小值。做這類題目，關鍵是要把題目中的約束條件表示為不等式，再把不等式轉(zhuǎn)化為圖的最短路或最長路模型。請計算使用哪些卡片，以及使用卡片的哪項能力，可以使相應的能力值之和最大。因此，更確切地說，本題是一個最大費用最大流模型。 例題 3 貪婪之島 （ ZOJ） 構圖 S P2 P1 P3 1 2 3 4 5 T B,0 1,0 從頂點ｉ (1≤i≤N) 向匯點引一條弧，容量為 1，費用為 0。 什么樣的卡片是沒有用的呢？ 先考慮第一種能力的選取：如果把全部卡片按第一種能力值從大到小排序，顯然我們應該盡量從前面選 A張出來，由于每張卡片只能使用一次，所以有可能會和其他的兩種能力發(fā)生沖突，而沖突的卡片數(shù)最多是 B+C張，所以實際上對我們有用的卡片只是前面的 A+B+C張。 至此，算法已經(jīng)
教學課件相關推薦
鄂ICP備17016276號-1