算法合集之平面圖在信息學(xué)中的應(yīng)用-在線瀏覽
2024-12-03 20:30本頁(yè)面
【正文】 max) 總計(jì)： O(NlogYmax) 空間性能分析 線段： O(N) 線段樹(shù)： O(Ymax) 邊表： O(N) 應(yīng)用 例 1:水平可見(jiàn)線段 (CEPC2021) ? 算法一 枚舉所有的三元組，判斷三個(gè)頂點(diǎn)是否兩兩相鄰。根據(jù)水平可見(jiàn)的定義可知 G為平面圖， G中的邊數(shù)為 O(N)，故算法二的復(fù)雜度為 O(N2) ? 算法一 與 算法二 的比較 算法一只是單純的枚舉，沒(méi)有注意到問(wèn)題的實(shí)際情況，而實(shí)際上三角形的數(shù)目是很少的，算法一作了許多無(wú)用的枚舉，因此效率很低。 統(tǒng)計(jì)圖 G中三角形的數(shù)目 應(yīng)用 例 1:水平可見(jiàn)線段 (CEPC2021) ? 算法三 —換個(gè)角度，從點(diǎn)出發(fā) 每次選取度最小的點(diǎn) v，由推論 2知 d(v)≤5，只需花常數(shù)時(shí)間就可以計(jì)算含點(diǎn) v的三角形的數(shù)目 . 應(yīng)用二叉堆可以提高尋找和刪除點(diǎn) v的效率，總的時(shí)間復(fù)雜度僅為O(NlogN) ? 算法二與算法三的比較 算法二是以邊作為出發(fā)點(diǎn)的，從整體上看，平面圖中三角形的個(gè)數(shù)只是 O(N)級(jí)的，而算法二的復(fù)雜度卻是 O(N2)，這種浪費(fèi)是判斷條件過(guò)于復(fù)雜造成的。 有沒(méi)有更好的辦法？ 應(yīng)用 例 2:洞穴 (CEOI97) 在同一水平面上有 N(N=500)個(gè)洞穴，洞穴之間有通道相連，且每個(gè)洞穴恰好連著三個(gè)通道。 (給定所有通道的信息和在外圈上的洞穴 ) 應(yīng)用 例 2:洞穴 (CEOI97) 分析 ? 本題求的是最優(yōu)路徑，但最優(yōu)路徑具備什么性質(zhì)并不明顯，故考慮深度優(yōu)先搜索。 ? 基本剪枝條件：若當(dāng)前路徑的難度值的總和比當(dāng)前最優(yōu)值大則放棄當(dāng)前路徑。 ? 剪枝條件一 在所有未訪問(wèn)的洞穴中，與其相鄰的已訪問(wèn)過(guò)的洞穴（第 1個(gè)與當(dāng)前訪問(wèn)的最后一個(gè)除外）的個(gè)數(shù)小于等于 1。由于圖是平面圖，其中必有一部分點(diǎn)不能被訪問(wèn)到。 根據(jù)地圖的平面性可知：轉(zhuǎn)化后的圖是平面圖。（區(qū)域數(shù) =500） 對(duì)于任意平面圖 G，是否都能用不超過(guò) 5種顏色著色？ 應(yīng)用 例 3:地圖著色 (ACM Shanghai 2021) 定理：對(duì)于任意平面圖 G，都能用不超過(guò) 5種顏色著色 . 證明：只需考慮 G是連通簡(jiǎn)單平面圖的情形 . 若 |V|≤5，則命題顯然成立 . 假設(shè)對(duì)所有的平
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1