信息學奧林匹克競賽輔導課件：搜索法

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