信息學(xué)奧林匹克競(jìng)賽輔導(dǎo)課件：搜索法

第四章、搜索法下面介紹3種最常用的搜索策略(1)枚舉法(2)回溯法(3)分支限界法(廣度優(yōu)先搜索)信息學(xué)奧林匹克競(jìng)賽輔導(dǎo)課件：搜索法第四章、搜索法下面介紹3種最常用的搜索策略(1)枚舉法(2)回溯法(3)分支限界法(廣度優(yōu)先搜索)無(wú)論什么類型的試題,只要能歸納出數(shù)學(xué)模型,就盡量用解析方法求解。因?yàn)橐粋€(gè)好的數(shù)學(xué)模型建立了客觀事物間準(zhǔn)確的運(yùn)算關(guān)系,運(yùn)用這個(gè)數(shù)學(xué)模型直接求解是再合適不過(guò)的了。當(dāng)然,這僅是一種可能性,因?yàn)椴⒎撬羞x手都能在競(jìng)賽的“一瞬間”把問(wèn)題分析得如此透徹,并非所有給定的問(wèn)題都能建立數(shù)學(xué)模型,即便有了數(shù)學(xué)模型,解該模型的準(zhǔn)確方法也不·定能套用現(xiàn)成算法。因此在某些情況下,還需要通過(guò)搜索(列舉所有可能情況)來(lái)尋求問(wèn)題的解。第一節(jié)枚舉法枚舉法的基本思想是根據(jù)提出的問(wèn)題枚舉所有可能狀態(tài),并用問(wèn)題給定的條件檢驗(yàn)?zāi)男┦切枰?哪些是不需要的。能使命題成立,即為其解。雖然枚舉法本質(zhì)上屬于搜索策略,但是它與后面講的回溯法有所不同,因?yàn)檫m用枚舉法求解的問(wèn)題必須滿足兩個(gè)條件無(wú)論什么類型的試題,只要能歸納出數(shù)學(xué)模型,就盡量用解析方法求解。因?yàn)橐粋€(gè)好的數(shù)學(xué)模型建立了客觀事物間準(zhǔn)確的運(yùn)算關(guān)系,運(yùn)用這個(gè)數(shù)學(xué)模型直接求解是再合適不過(guò)的了。當(dāng)然,這僅是一種可能性,因?yàn)椴⒎撬羞x手都能在競(jìng)賽的“一瞬間”把問(wèn)題分析得如此透徹,并非所有給定的問(wèn)題都能建立數(shù)學(xué)模型,即便有了數(shù)學(xué)模型,解該模型的準(zhǔn)確方法也不·定能套用現(xiàn)成算法。因此在某些情況下,還需要通過(guò)搜索(列舉所有可能情況)來(lái)尋求問(wèn)題的解。第一節(jié)枚舉法枚舉法的基本思想是根據(jù)提出的問(wèn)題枚舉所有可能狀態(tài),并用問(wèn)題給定的條件檢驗(yàn)?zāi)男┦切枰?哪些是不需要的。能使命題成立,即為其解。雖然枚舉法本質(zhì)上屬于搜索策略,但是它與后面講的回溯法有所不同,因?yàn)檫m用枚舉法求解的問(wèn)題必須滿足兩個(gè)條件(1)可預(yù)先確定每個(gè)狀態(tài)的元素個(gè)數(shù)n(2)狀態(tài)元素a,a2a的可能值為一個(gè)連續(xù)的值域設(shè)狀態(tài)元素a:的最小值;ak一狀態(tài)元素a的最大值(1<=i<=n),即我們稱狀態(tài)元素為枚舉變量。例如某問(wèn)題的枚舉變量有3個(gè):a1,a2,a3。其中:1<=a1<=2,2<=a2<=4,5<=ax<=7則問(wèn)題的可能狀態(tài)集為(a1,a2a3)={(1,25),(1,2,6),(1,2,7)(1,35),(1,3,6)、1,3,7),(1,4,5),(14,6),(1,47),(2,25)(22,6)、(2,27)23,5),(2,36),(23,7)(245),(246),(247)在上述18個(gè)可能的狀態(tài)集中,滿足問(wèn)題給定的檢驗(yàn)條件的狀態(tài)即為問(wèn)題的解。般來(lái)說(shuō),如果確定了枚舉變量的個(gè)數(shù)及其值域,我們則可以利用for語(yǔ)句和條件判斷語(yǔ)句逐步求解或證明ora=all;al<=alk;al++)for(a2=a21:a2<=a2k;a2++)for(ai=ail,ai<=aik;ai++)for(an=anl;an<=ank;an++)if狀態(tài)(a1,a2….ai,…an)滿足檢驗(yàn)條件輸出問(wèn)題的解;由此可見(jiàn),枚舉的次數(shù)為a,-a:1)枚舉法的優(yōu)點(diǎn)(1)于枚舉算法一般是現(xiàn)實(shí)生活中問(wèn)題的“直譯”,因此比較直觀,易于理解;(2)由于枚舉算法建立在考察大量狀態(tài)、甚至是窮舉所有狀態(tài)的基礎(chǔ)上,所以算法的正確性比較容易證明。枚舉法的缺點(diǎn):枚舉算法的效率取決于枚舉狀態(tài)的數(shù)量及單個(gè)狀態(tài)枚舉的代價(jià),因此效率比較低當(dāng)然,由于模型建立的不同,信息提取量的不同,同一個(gè)問(wèn)題可以有多個(gè)枚舉算法,效率也可能有所不同,甚至可能有很大的差異。、“直譯”的枚舉算法將自然語(yǔ)言描述的問(wèn)題“翻譯”成算法的過(guò)程,即為“直譯”?，F(xiàn)實(shí)生活中的許多問(wèn)題可以“直譯”成枚舉算法例如古代著名的“百雞百錢”(公雞一只5文錢,母雞一只3文錢,小雞3只一文錢。要求計(jì)算一百錢可買3種雞一百只的數(shù)量。)問(wèn)題就是一個(gè)典型的枚舉問(wèn)題for(intx=l;X