人工智能算法（Python語言版）PPT第3章-減治法

提綱減治法策略拓?fù)渑判蚩偨Y(jié)減治法策略大規(guī)模核酸檢測：在席卷全球的新冠病毒感染檢測和疫情防控中，由于人口眾多，如果對每個人的核酸檢測樣本逐一檢測以確診感染病毒，實施難度較大。多人混檢降低大規(guī)模篩查成本：針對40人以內(nèi)的待檢測人員群體，可將被檢測人員根據(jù)人數(shù)均分為兩組進(jìn)行核酸混樣檢測，將每組檢測人員的全部樣本放到一起統(tǒng)一檢測。隨著核酸檢測成本的逐漸降低，混檢數(shù)量從40減少到10和5等。逐步縮小篩查范圍：如果是陰性，則表明該組被檢人員均不是病毒感染患者；如果是陽性，則表明該組被檢人員中存在病毒感染患者。然后，對該組人員做進(jìn)一步分組，繼續(xù)進(jìn)行核酸混樣檢測，循環(huán)往復(fù)，直至找出患者。減治法減治法策略減治法（Decrease-and-Conquer）利用給定規(guī)模與較小規(guī)模問題解之間的關(guān)系，從頂至下（遞歸）或從底至上（非遞歸）求解問題的一種方法3種類型（1）減常量法：常量通常為1即減1法，也有減2的（如奇偶數(shù)分別處理）（2）減常因子法：常因子通常為2（減半技術(shù)）（3）減可變規(guī)模法：規(guī)模減小的模式不同常量為1常量因子為2提綱減治法策略拓?fù)渑判蚩偨Y(jié)拓?fù)渑判?1)問題描述假設(shè)我們要安排一系列任務(wù)，如任務(wù)分工、教學(xué)計劃中的各門課程的安排順序（先修課），項目中各子課題的研究順序，建筑項目等每個任務(wù)只有其當(dāng)先決條件具備時，才能著手安排這個任務(wù)去完成找到在滿足先決條件情況下，各個任務(wù)如何安排的一個線性序列（先決條件不矛盾）例如：5門必修課的集合{C1,C2,C3,C4,C5}，學(xué)生必須修完這些課程。先決條件：1）C1和C2沒有先決條件2）修完C1和C2才能修C33）修完C3才能修C44）修完C3和C4才能修C5問題：-學(xué)生按什么順序?qū)W習(xí)這些課程？-解不唯一？拓?fù)渑判?2)建?！獔D頂點——任務(wù)，邊——某個任務(wù)的先決條件(1)有向圖：任務(wù)之間有先后關(guān)系（有向邊）(2)無環(huán)圖：若為有環(huán)圖，回路中就存在相互矛盾的條件，問題無解拓?fù)渑判蛴薪獾膱D，必然是有向無環(huán)圖基于深度優(yōu)先遍歷的拓?fù)渑判?執(zhí)行一次深度優(yōu)先查找，記住頂點變成死端（出棧）的順序-拓?fù)渑判虻囊粋€解：將出棧次序反過來基于減一技術(shù)的拓?fù)渑判?在余下的有向圖中找一個源（沒有入邊的頂點），刪除該源及出邊-源不存在，算法停止-拓?fù)渑判虻囊粋€解：頂點被刪除的次序拓?fù)渑判?3)

輸入：G：給定n個頂點、m條邊的有向無環(huán)圖輸出：List或False：輸出存儲拓?fù)湫蛄许旤c的列表，或不存在拓?fù)湫蛄?/p>

拓?fù)渑判?4)基于減一技術(shù)的拓?fù)渑判颍ㄔ磩h除算法）C1C2C4C3C5刪除C1C2C4C3C5刪除C2C4C3C5刪除C3C4C5刪除C4C5拓?fù)渑判虮恚篊2C1C3C4C5拓?fù)渑判?5)課程修讀的先后次序拓?fù)渑判蛲負(fù)渑判?6)源刪除算法的實現(xiàn)——基于數(shù)組（圖存儲：鄰接矩陣）用一個入度數(shù)組保存每個頂點的入度（無取出規(guī)則）找到入度為0的點，將其存入數(shù)組中，再將其從圖中刪除（與它相關(guān)的邊都刪除，相鄰的頂點的入度均減1）重復(fù)步驟(1)執(zhí)行，直至所有的頂點都被找到為止時間復(fù)雜度為O(n2)（即圖的遍歷）源刪除算法的實現(xiàn)——基于隊列（圖存儲：鄰接表）(1)在圖中找出所有無先決條件的源頂點，將它們?nèi)咳腙牐ㄈ〕鲆?guī)則）若無源，算法停止，輸出記錄的頂點序列，得到解（無未訪問頂點）(2)隊頭頂點出隊（實現(xiàn)刪除操作），且按出隊順序記錄頂點，并同時刪除

從這個頂點出發(fā)的所有的邊（隊列的出入隊順