算法合集之圖論的基本思想及方法(參考版)
2024-10-19 20:30本頁面
【正文】 樣例的模擬 進(jìn)行遞推： f (1,3) = max{f (1,2), f (2,3)} + 1 = 3 1 2 3 4 5 6 f(1,2)=1 f(4,6)=1 f(2,3)=2 f(3,4)=2 f(3,5)=3 f(5,4)=3 f(5,6)=4 f(1,3)=3 f(2,4)=1 。 進(jìn)行遞推： f (5, 6) = max{f (4, 5), f (4,6)} + 1 = 4 將 6的前驅(qū)指針指向 5 1 2 3 4 5 6 f(1,2)=1 f(2,4)=1 f(4,6)=1 f(2,3)=2 f(3,4)=2 f(3,5)=3 f(5,4)=3 f(5,6)=4 回溯到 1 擴(kuò)展結(jié)點(diǎn) 3，發(fā)現(xiàn) 3已經(jīng)被擴(kuò)展。 進(jìn)行遞推： f (3, 5) = f (3, 4) + 1 = 3 f (5, 4) = f (3, 4) + 1 = 3 將 4的前驅(qū)指針指向 5 1 2 3 4 5 6 f(1,2)=1 f(2,4)=1 f(4,6)=1 f(2,3)=2 f(3,4)=2 f(3,5)=3 f(5,4)=3 樣例的模擬 擴(kuò)展結(jié)點(diǎn) 6，發(fā)現(xiàn) 6已經(jīng)被擴(kuò)展。 進(jìn)行遞推： f (2, 3) = f (2, 4) + 1 = 2 f (3, 4) = f (2, 4) + 1 = 2 將 4的前驅(qū)指針指向 3 f(1,2)=1 f(2,4)=1 f(4,6)=1 f(2,3)=2 f(3,4)=2 樣例的模擬 回溯到 3，擴(kuò)展結(jié)點(diǎn) 5 擴(kuò)展結(jié)點(diǎn) 4，發(fā)現(xiàn) 4已經(jīng)被擴(kuò)展。 兩個(gè)算法思考?xì)v程的共同點(diǎn) 實(shí)際問題 尋找合適的圖論模型 以圖論模型為平臺挖掘問題的性質(zhì) 設(shè)計(jì)相應(yīng)的算法 解決問題 結(jié)語 “模型” 圖論基本思想的精華 解決圖論問題的關(guān)鍵 建立模型 熟練掌握經(jīng)典模型 勇于探索，大膽創(chuàng)新 挖掘利用模型性質(zhì) 獨(dú)具慧眼 一擊中的 樣例的模擬 下面在樣例上模擬運(yùn)行算法二，說明算法二是如何執(zhí)行的： 1 2 3 4 5 6 從結(jié)點(diǎn) 1開始遍歷 一直深搜到結(jié)點(diǎn) 6 可知 (1,2), (2,4)和 (4,6)為最靠左的邊，所以 f 值為 1 f(1,2)=1 f(2,4)=1 f(4,6)=1 樣例的模擬 1 2 3 4 5 6 回溯到 2，擴(kuò)展結(jié)點(diǎn) 3 擴(kuò)展結(jié)點(diǎn) 4，發(fā)現(xiàn) 4已經(jīng)被擴(kuò)展。 總的復(fù)雜度為 O(n) 算法一直接根
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1