算法合集之信息學(xué)競賽中搜索問題的常見優(yōu)化技巧-wenkub
2022-10-31 20:30:49 本頁面
【正文】 值，我們顯然可以采用從小到大搜索和從大到小搜索兩種搜索方法。深度優(yōu)先搜索問題的優(yōu)化技巧 重慶一中 黃曉愉 深度優(yōu)先搜索的優(yōu)化技巧 在深度優(yōu)先搜索中如何運用題目中的約束條件為我們提供剪枝是影響程序效率的關(guān)鍵。 由于題目要求的是 m的最小值，也就是需要我們盡快構(gòu)造出 n，所以每次構(gòu)造的數(shù)應(yīng)當(dāng)是盡可能大的數(shù) 。 如何改進(jìn)？ 太慢了 ? 但是這個算法最壞的情況下擴(kuò)展的節(jié)點為5001000，這個算法 從已知入手分析 s2 s 0 s1 s 3 s 4 t 4 t 3 t 2 t 1 t 0 我們用 Si表示前 I個數(shù)的和 Ti表示后 I個數(shù)的和 對題目中數(shù)據(jù)分類 s0 s1 s2 s3 s4 t 4 t3 t 2 t 1 t 0 集合 A 集合 B 任意 I滿足： Si+TnI=Sn=Tn 分析 在集合 A和集合 B中： {S0S1S2……S n} {T0T1T2……T n} s 0 s1 s2 s
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1