cy分治解題報告ppt課件-資料下載頁
2024-12-08 02:42本頁面
【正文】 aximal(son[i][1],k2)。 if (tm) m=t。 } if (j==0) m++。 return m。} 01( , ) m a x{ ( ( , 0), 1 ) ( ( , 1 ) , 2)} 1m a x{ ( ( , 0), 1 ) ( ( , 1 ) , 2)} 1 11 2 { , , }iF i j F so n i j F so n i j i j gr e e nF so n i j F so n i j i j gr e e nj j j re d gr e e n bl ue????? ? ?? ? ???? ? ? ?? ? ???其 中 、 、 但 互 不 相 同 。算法效率分析 01( , ) m a x{ ( ( , 0), 1 ) ( ( , 1 ) , 2)} 1m a x{ ( ( , 0), 1 ) ( ( , 1 ) , 2)} 1 11 2 { , , }iF i j F so n i j F so n i j i j gr e e nF so n i j F so n i j i j gr e e nj j j re d gr e e n bl ue????? ? ?? ? ???? ? ? ?? ? ???其 中 、 、 但 互 不 相 同 。?每個節(jié)點可以染 3種顏色，最壞情況的計算量為 O(3n)。 ?n10000 ?本算法在 幾年 之內(nèi)無法得出結(jié)果！ 算法改進 (1,red) (1,green) (0,blue) (2,blue) (2,green) (2,red) (2,blue) 可以用一個數(shù)組記錄下已經(jīng)搜索過的子問題的答案，避免重復(fù)搜索 記憶化搜索 int maximal(int i,int j) { int k1,k2,t,m。 if (i==1) return 0。 if (max[i][j]!=1) return max[i][j]。 m=1。 for (k1=0。k13。k1++) if (k1!=j) for (k2=0。k23。k2++) if (k2!=jamp。amp。k2!=k1) { t=maximal(son[i][0],k1)+maximal(son[i][1],k2)。 if (tm) m=t。 } if (j==0) m++。 max[i][j]=m。 return m。 } 復(fù)雜度分析： 最壞情況是 max數(shù)組的所有 值均被計算過，即至多計算 10000*3次。 編制測試數(shù)據(jù) ? 用手工可以檢驗的小數(shù)據(jù)，驗證程序的正確性 ? 編寫程序隨機生成大數(shù)據(jù)，檢驗程序的執(zhí)行效率（使用隨機函數(shù)） ? 注意檢驗邊界條件。例如，本題中 0或200，判斷程序是否正確。 小結(jié) ? 本題也可以倒著推，從葉子節(jié)點逐步往上窮舉著色方案。這樣就需要每個節(jié)點的父節(jié)點號。做的時候同樣要注意去除重復(fù)計算，這個方法就叫做動態(tài)規(guī)劃。 ? 搜索算法是通用的解題法，當(dāng)遇到其它辦法無法解決時，都可以使用搜索，但算法的效率不高。要熟悉用遞歸關(guān)系來表達問題。 ? 如果本題改為 k叉樹 m著色 怎么做？ Question amp。 Answer
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1