遞歸回溯與剪枝

遞歸回溯與剪枝第一頁(yè)，共三十三頁(yè)，2022年，8月28日遞歸與回溯我們有時(shí)會(huì)碰到一些題目，它們既不能通過(guò)建立數(shù)學(xué)模型解決，又沒(méi)有現(xiàn)成算法可以套用，或者必須遍歷所有狀況才可以得出正確結(jié)果。這時(shí)，我們就必須采用搜索算法來(lái)解決問(wèn)題。搜索算法按搜索的方式分有兩類，一類是深度優(yōu)先搜索，一類是廣度優(yōu)先搜索。而對(duì)于深度優(yōu)先搜索來(lái)說(shuō)，我們需要使用到的一個(gè)技術(shù)就是遞歸與回溯。第二頁(yè)，共三十三頁(yè)，2022年，8月28日回溯法（試探法），在問(wèn)題的解空間中，將問(wèn)題的所有候選解按某種順序逐一枚舉和檢驗(yàn)，從而找到符合要求的解的集合或最優(yōu)解。關(guān)鍵詞：向前試探，回溯遞歸法為求解規(guī)模為N的問(wèn)題，設(shè)法將它分解成一些規(guī)模較小的問(wèn)題，然后從這些較小的問(wèn)題方便地構(gòu)造出大問(wèn)題的解，并且這些規(guī)模較小的問(wèn)題也能采用同樣的分解和綜合方法，分解成規(guī)模更小的問(wèn)題，特別的，當(dāng)N=1時(shí)，能夠直接得到解。關(guān)鍵詞：遞進(jìn)，回歸問(wèn)題分析（代碼架構(gòu)）回溯法遞歸法棧第三頁(yè)，共三十三頁(yè)，2022年，8月28日常見(jiàn)的剪枝的方法限界剪枝法最優(yōu)性剪枝可行性剪枝奇偶剪枝第四頁(yè)，共三十三頁(yè)，2022年，8月28日“和最小”題目描述設(shè)有一個(gè)長(zhǎng)度為N的數(shù)字串，要求使用K個(gè)加號(hào)將它分成K+1個(gè)部分，找出一種分法，使得這K+1個(gè)部分的和能夠?yàn)樽钚?。有一個(gè)數(shù)字串：312，當(dāng)N=3，K=1時(shí)會(huì)有以下兩種分法：1)3+12=152)31+2=33

這時(shí)，符合題目要求的結(jié)果是：3+12=15第五頁(yè)，共三十三頁(yè)，2022年，8月28日遞歸回溯法算法框架[一]procedureSearch(k:integer);beginfori:=1to算符種數(shù)Doif滿足條件thenbegin

保存結(jié)果

if到目的地then輸出解

elseSearch(k+1);

恢復(fù)：保存結(jié)果之前的狀態(tài){回溯一步}end;end;第六頁(yè)，共三十三頁(yè)，2022年，8月28日遞歸回溯法算法框架[二]procedureSearch(k:integer);beginif到目的地then輸出解

elsefori:=1to算符種數(shù)Doif滿足條件thenbegin

保存結(jié)果

Search(k+1,參數(shù)表); end;end;第七頁(yè)，共三十三頁(yè)，2022年，8月28日搜索策略題目要求的就是在每個(gè)數(shù)字之間：或者填加號(hào)，或者什么都不填。根據(jù)這個(gè)要求，我們可以從頭開(kāi)始掃描整個(gè)數(shù)字串，逐個(gè)考察是否要填加號(hào)，然后檢查下一個(gè)數(shù)字間的位置，直到最后一個(gè)數(shù)字。下面是一個(gè)例子和它的狀態(tài)樹(shù)第八頁(yè)，共三十三頁(yè)，2022年，8月28日數(shù)字7629需要插入2個(gè)加號(hào)這是一棵完整的搜索樹(shù)。結(jié)點(diǎn)內(nèi)表示當(dāng)前處理的狀態(tài)，每向后處理一個(gè)空位即深入一層。我們可以看到，在最后的所有葉子結(jié)點(diǎn)中，有三個(gè)黃色的結(jié)點(diǎn)是滿足條件的。7+6+2+9

77+6

767+6+27+6276+2

7627+62+97+62976+2+976+29

7629762+97+6+297和6之間不添加加號(hào)7和6之間添加一個(gè)加號(hào)第九頁(yè)，共三十三頁(yè)，2022年，8月28日迷宮問(wèn)題給出一個(gè)迷宮的地圖，有一些格子中有障礙，問(wèn)從起點(diǎn)到終點(diǎn)的最短路徑，并輸出所有的最短路徑?；厮莘ń忸}思路1、

這個(gè)方向有路可走，我沒(méi)走過(guò)，

往這個(gè)方向前進(jìn)2、

是死胡同,往回走,回到上一個(gè)路口3、

重復(fù)第一步，直到找著出口第十頁(yè)，共三十三頁(yè)，2022年，8月28日但是回溯法的缺點(diǎn)暴露無(wú)遺：搜索耗時(shí)極巨，無(wú)法忍受。那么我們可否提前判斷我們前進(jìn)的方向是否可能得到最優(yōu)解呢？如果可以的話，搜索效率豈不是能夠提高了嗎答案就是：剪枝！第十一頁(yè)，共三十三頁(yè)，2022年，8月28日關(guān)于剪枝剪枝的概念，其實(shí)就跟走迷宮避開(kāi)死胡同差不多.。若我們把搜索的過(guò)程看成是對(duì)一棵樹(shù)的遍歷，那么剪枝顧名思義,就是將樹(shù)中的一些“死胡同”，不能到達(dá)我們需要的解的枝條“剪”掉，以減少搜索的時(shí)間。搜索算法，絕大部分需要用到剪枝。

然而，不是所有的枝條都可以剪掉，這就需要通過(guò)設(shè)計(jì)出合理的判斷方法，以決定某一分支的取舍。

在設(shè)計(jì)判斷剪枝條件的時(shí)候，就需要有一定的方法。

第十二頁(yè)，共三十三頁(yè)，2022年，8月28日最優(yōu)性剪枝又稱為上下界剪枝一種重要的搜索剪枝策略記錄當(dāng)前得到的最優(yōu)值如果當(dāng)前結(jié)點(diǎn)已經(jīng)無(wú)法產(chǎn)生比當(dāng)前最優(yōu)解更優(yōu)的解時(shí)，可以提前回溯第十三頁(yè)，共三十三頁(yè)，2022年，8月28日回到加號(hào)題兒子結(jié)點(diǎn)的數(shù)一定比父親大即搜索樹(shù)深度越深得到的解越大滿足最優(yōu)性剪枝的條件我們可以記錄當(dāng)前得到的解的最小值如果當(dāng)前得到的和值已經(jīng)超過(guò)保存的最小解，即不必再繼續(xù)深入搜索，回溯。第十四頁(yè)，共三十三頁(yè)，2022年，8月28日再看搜索樹(shù)我們可以看到紅色結(jié)點(diǎn)的子節(jié)點(diǎn)不可能有最優(yōu)解

77+6

767+6+27+6276+2

7627+62+97+62976+2+976+29

7629762+97+6+2+97+6+29第十五頁(yè)，共三十三頁(yè)，2022年，8月28日最優(yōu)性剪枝結(jié)果結(jié)點(diǎn)數(shù)大大減少。

77+6767+6+27+627+6+2+97+6+29第十六頁(yè)，共三十三頁(yè)，2022年，8月28日可行性剪枝除最優(yōu)性剪枝外，另一種重要的搜索剪枝策略判斷繼續(xù)搜索能否得出答案，如果不能直接回溯第十七頁(yè)，共三十三頁(yè)，2022年，8月28日再看搜索樹(shù)對(duì)于圖中藍(lán)色結(jié)點(diǎn)。后面能夠插入’+’的位置已經(jīng)少于未用完’+’的數(shù)量，肯定不可能有解。對(duì)于這種結(jié)點(diǎn)，其子節(jié)點(diǎn)不可能有解，可以回溯。這個(gè)節(jié)點(diǎn)的加號(hào)不可能有解,可以進(jìn)行可行性剪枝

77+6

767+6+27+6276+2

7627+62+97+62976+2+976+29

7629762+97+6+2+97+6+29第十八頁(yè)，共三十三頁(yè)，2022年，8月28日迷宮問(wèn)題最優(yōu)性剪枝我們可以將每一次搜索出的路徑長(zhǎng)度與上界比較（初始上界＝∞），不斷降低上界，一旦出現(xiàn)路徑長(zhǎng)超出上界而仍未到達(dá)目標(biāo)點(diǎn)，則放棄該搜索進(jìn)程。因?yàn)榫退憷^續(xù)搜索下去，這一條路徑也必然比其他路徑長(zhǎng)，不是最優(yōu)解。第十九頁(yè)，共三十三頁(yè)，2022年，8月28日總結(jié)深度優(yōu)先搜索的程序簡(jiǎn)潔易懂，空間需求也比較低，但是這種方法的時(shí)間復(fù)雜度往往是指數(shù)級(jí)的，倘若不加優(yōu)化，其時(shí)間效率簡(jiǎn)直無(wú)法忍受；所以，如何用正確的方法對(duì)程序進(jìn)行優(yōu)化，就成為搜索算法編程中最關(guān)鍵的一環(huán)。那么，剪枝就是搜索優(yōu)化中最基本的方法之一。第二十頁(yè)，共三十三頁(yè)，2022年，8月28日總結(jié)兩種常用的剪枝方法：最優(yōu)性剪枝適用范圍：子結(jié)點(diǎn)的代價(jià)全部高于或低于父結(jié)點(diǎn)又之稱為多米諾性質(zhì)?？尚行约糁Ω鶕?jù)題意作出判斷是否繼續(xù)搜索還有可能得到解第二十一頁(yè)，共三十三頁(yè)，2022年，8月28日剪枝的原則1.正確性：必須保證不丟失正確的結(jié)果。2.準(zhǔn)確性：能夠盡可能多的減去不能通向正解的枝條3.高效性：在很多時(shí)候，為了加強(qiáng)優(yōu)化的效果，我們會(huì)增加一些判斷，這樣對(duì)程序效率也帶來(lái)了副作用，所以要考慮剪枝的高效性，否則得不償失。第二十二頁(yè)，共三十三頁(yè)，2022年，8月28日總結(jié)在搜索算法中，幾乎都需要采用程序優(yōu)化,以減少時(shí)間復(fù)雜度。而這里所說(shuō)的兩種剪枝方法，是最常見(jiàn)的優(yōu)化方法之一。然而，盡管可以采用眾多優(yōu)化算法使得程序的效率有所提高，搜索算法本身的時(shí)間復(fù)雜度不能從本質(zhì)上減少是不可改變的事實(shí)。不妨在使用搜索算法之前先仔細(xì)想想，有沒(méi)有其他更好的算法。第二十三頁(yè)，共三十三頁(yè)，2022年，8月28日?qǐng)?jiān)持就有希望，努力就有回報(bào)！目標(biāo)都能實(shí)現(xiàn)！夢(mèng)想都能成真！第二十四頁(yè)，共三十三頁(yè)，2022年，8月28日演講稿的寫(xiě)法

七個(gè)階段的準(zhǔn)備

一、決定話題和目的二、分析聽(tīng)眾和場(chǎng)合三、滿足聽(tīng)眾的本能欲求四、收集材料五、編制提綱六、練習(xí)詞語(yǔ)七、練習(xí)篇章第二十五頁(yè)，共三十三頁(yè)，2022年，8月28日一、演說(shuō)者和聽(tīng)眾分析

1、演說(shuō)的成敗，首先決定于演說(shuō)者的良好心理素質(zhì)和充分準(zhǔn)備。必須克服羞怯、拘謹(jǐn)、冷談、自卑，做到勇敢、輕松、親切、自信。任何演講都必須有滿腔熱情和必勝的信心。

2、在演講前對(duì)聽(tīng)眾的人數(shù)、年紀(jì)、性別、教育程度、有關(guān)話題的、關(guān)注焦點(diǎn)和愿望、固定的態(tài)度和信仰等要進(jìn)行調(diào)查，做到有的放矢，才可能收到理想的效果。

3、在演說(shuō)過(guò)程中，必須目視聽(tīng)眾，必須察言觀色，注意聽(tīng)眾情緒反應(yīng)做適當(dāng)?shù)狞c(diǎn)整。第二十六頁(yè)，共三十三頁(yè)，2022年，8月28日二、確定目的和選擇話題

1、目的要么讓人快樂(lè)；要么給人知識(shí)；要么讓人行動(dòng)；社交是聯(lián)絡(luò)感情，鑒賞目的是讓人快樂(lè)、讓人感動(dòng)。可概括三大主要目的:知行目的，人際目的，語(yǔ)篇目的。

2、話題要令人親近、關(guān)注，因此要具有社會(huì)性，特別要關(guān)注社會(huì)的熱點(diǎn)。要明確、集中、正確、易懂，要有一定得形象性。要具有針對(duì)性，針對(duì)某種意見(jiàn)做辯答，或解決某個(gè)要解決問(wèn)題，或針對(duì)某些人思想情緒。第二十七頁(yè)，共三十三頁(yè)，2022年，8月28日三、文字口語(yǔ)化，語(yǔ)言的節(jié)奏感演講的聲音稍縱即逝，因而演講稿必須要寫(xiě)得入耳。

1、多用群眾創(chuàng)造的形象生動(dòng)的語(yǔ)言演講要盡量把不易聽(tīng)懂的書(shū)面語(yǔ)言改為口語(yǔ)，如書(shū)面語(yǔ)“對(duì)壘”、“角逐”改為“比賽”、“競(jìng)爭(zhēng)”等口語(yǔ)。

2、避免同音相混的語(yǔ)言如期中---期終；終年----中年；全部---全不等

3、多用象聲語(yǔ)言如，載重超負(fù)荷-----裝多了，車(chē)壓得吱吱的響；不說(shuō)“正、草、隸、篆他會(huì)寫(xiě)”應(yīng)改為“什么正楷啦，草書(shū)啦，隸書(shū)啦，篆書(shū)啦他全部會(huì)寫(xiě)”第二十八頁(yè)，共三十三頁(yè)，2022年，8月28日四、演講稿的開(kāi)頭1、提問(wèn)開(kāi)頭法有這樣一個(gè)問(wèn)題常在我的腦海里縈回：是什么力量使愛(ài)因斯坦名揚(yáng)天下之后仍在攀登科學(xué)高峰呢？是什么力量使張海迪在死神纏繞之時(shí)仍銳志奮進(jìn)呢？，這大概是當(dāng)代青年，特別是我們大學(xué)生討論最多的問(wèn)題之一，也是我今天演講的題目。第二十九頁(yè)，共三十三頁(yè)，2022年，8月28日2、套近乎開(kāi)頭林肯的演說(shuō)：聽(tīng)說(shuō)在場(chǎng)的就有些人要下決心和我作對(duì)，我實(shí)在不明白為什么要這樣做，我也和你們一樣是一位爽直的平民，我為什么不能和你們一樣有發(fā)表意見(jiàn)的權(quán)力呢？好朋友，我不是來(lái)干涉你們的，我是你們中間的一員。第三十頁(yè)，共三十三頁(yè)，2022年，8月28日

3、引用入題法同學(xué)們，有一首詩(shī)這樣寫(xiě)道：“多少人愛(ài)你青春歡暢的時(shí)候，愛(ài)慕你的美麗，也許假意或真心。只要我愛(ài)你朝圣者的靈魂，愛(ài)你衰老的臉上臉上的痛苦的皺紋?！痹?shī)中傾訴的是深沉真摯的愛(ài)，正如別林基斯所說(shuō)：“愛(ài)是理解的別名?！敝?，才能愛(ài)之愈切，今天，帶著這種愛(ài)，我要講一講我的祖國(guó)，講一講生我的這片土地。第三十一頁(yè)，共三十三頁(yè)，2022年，8月28日

4、開(kāi)門(mén)見(jiàn)山我主張將我們?nèi)h的學(xué)習(xí)方法和學(xué)習(xí)制度改造一下。（改造我們的學(xué)習(xí)）

5、懸念開(kāi)頭法剛才，我會(huì)見(jiàn)了一個(gè)歐洲代表團(tuán)，他們問(wèn)我對(duì)一部分先富起來(lái)的政策持什么看法。我對(duì)特們說(shuō)，這個(gè)問(wèn)題我已經(jīng)不感興趣了！因?yàn)椋@已經(jīng)成為現(xiàn)實(shí)了！他們接著問(wèn)我，那你對(duì)什么感興趣？我對(duì)他們說(shuō)，我對(duì)一部分縣富