算法合集之探尋深度優(yōu)先搜索中的優(yōu)化技巧(已修改)
2025-10-23 20:30 本頁面
【正文】 探尋深度優(yōu)先搜索中的優(yōu)化技巧 —— 從正方形剖分問題談起 長沙市長郡中學(xué) 金愷 正方形剖分問題 問題描述： 將 n n 個小格組成的大正方形分割成若干個較小的整數(shù)邊長的正方形，要求分成的小正方形數(shù)目最小。 范圍： 1≤n≤32。 編程環(huán)境： FreePascal。 可用 64MB空間 n=7時的一個最小數(shù)目的剖分方案，需要 9個小正方形。 分析 當(dāng) n為偶數(shù)時最少需要 4個小正方形： 1 2 3 4 n/2 n/2 n/2 n/2 當(dāng) n為奇數(shù)時，很難發(fā)現(xiàn)有什么數(shù)學(xué)規(guī)律。 ???????????????????????????? 0,0)0()0(m i n,1000,, jiNjijijkffikffNijijifkjikijkijkji或或設(shè) fi,j表示一個 i j的矩形最少可以被剖分成多少個小正方形 : n=7時，求出結(jié)果為 10，并不是最優(yōu)值。原因：最優(yōu)方案不一定能被某條直線分割。 i j k jk i j k ik n 7 11 13 17 19 23 29 31 其他 fn,n 10 12 12 14 14 16 16 16 相同 最優(yōu)值 9 11 11 13 13 13 14 15 相差 1 1 1 1 1 3 2 1 0 fn,n僅是一個可行解，不過其值與最優(yōu)解十分接近的。 目前只能用搜索！ 優(yōu)化：搜索之前先用上述動態(tài)規(guī)劃方程求出一個較優(yōu)值，限制搜索層次。 搜索量巨大，僅用這一條優(yōu)化，效率十分低下。 如何搜索？ 搜索的對象和順序 從大量的搜索題 (比如說 IOI的 Depot等 )可以看出 ，搜索的順序和對象是十分重要的 ， 本題應(yīng)該用什么作為搜索對象 ， 搜索順序又是怎樣呢 ？ 搜索的對象：每個小正方形的位置和邊長 。 一種最簡單的搜索順序?yàn)椋航o大正方形中第 i行第 j列的小格編號 (i1)n+j， 每次選擇編號最小的未覆蓋的小格作
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1