算法合集之信息學(xué)競(jìng)賽中搜索問題的常見優(yōu)化技巧(已修改)
2024-10-28 20:30 本頁面
【正文】 深度優(yōu)先搜索問題的優(yōu)化技巧 重慶一中 黃曉愉 深度優(yōu)先搜索的優(yōu)化技巧 在深度優(yōu)先搜索中如何運(yùn)用題目中的約束條件為我們提供剪枝是影響程序效率的關(guān)鍵。而 搜索的順序 和 搜索的對(duì)象 對(duì)于這一點(diǎn)是十分重要的。 搜索順序的選擇 我們先來看一道比較簡(jiǎn)單的題目： (zju1937) 已知一個(gè)數(shù)列 a0,a1......am其中 a0 = 1 am = n a0 a1 a2 ... am1 am 對(duì)于每個(gè) k(1=k=m),ak=ai+aj (0 = i, j = k1)，這里 i與 j可以相等 。 現(xiàn)給定 n的值 ， 要求 m的最小值 簡(jiǎn)單的分析 ? 依次搜索是很容易想到的方法，而對(duì)于每個(gè)數(shù)的取值，我們顯然可以采用從小到大搜索和從大到小搜索兩種搜索方法。 由于題目要求的是 m的最小值，也就是需要我們盡快構(gòu)造出 n，所以每次構(gòu)造的數(shù)應(yīng)當(dāng)是盡可能大的數(shù) 。 不同搜索順序效率比較 兩種搜索順序比較： 01210 30 50 60
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1