• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆 - 70  文章 - 160  trackbacks - 0

            公告:
            知識共享許可協議
            本博客采用知識共享署名 2.5 中國大陸許可協議進行許可。本博客版權歸作者所有,歡迎轉載,但未經作者同意不得隨機刪除文章任何內容,且在文章頁面明顯位置給出原文連接,否則保留追究法律責任的權利。 具體操作方式可參考此處。如您有任何疑問或者授權方面的協商,請給我留言。

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            搜索

            •  

            積分與排名

            • 積分 - 179896
            • 排名 - 147

            最新評論

            閱讀排行榜

            評論排行榜

            半年前在POJ上遇到過一次剪枝的題目,那時覺得剪枝好神秘。。。今天在網上查了半天資料,終于還是摸索到了一點知識,但是相關資料并不多,在我看來,剪枝是技巧,而不是方法,也就是說,可能一點實用的小技巧,讓程序可以少判斷一點,這就是剪枝,剪枝無處不在,

            搜索的進程可以看作是從樹根出發,遍歷一棵倒置的樹—-搜索樹的過程。而所謂的剪枝,顧名思義,就是通過某種判斷,避免一些不必要的遍歷過程,形象的說,就是減去了搜索樹中的某些“枝條”,故稱剪枝。
            (杭電課件上是這么說的:即剪去解答樹上已被證明不可能存在可行解或最優解的子樹.)

            既然采用了搜索,剪枝就顯得十分的必要,即使就簡簡單單的設一個檻值,或多加一兩條判斷,就可對搜索的效率產生驚人的影響。例如N后問題,假如放完皇后再判斷,則僅僅只算到7,就開始有停頓,到了8就已經超過了20秒,而如果邊放邊判斷,就算到了10,也沒有停頓的感覺。所以,用搜索一般都就要剪枝。

            剪枝至少有兩方面,一是從方法上剪枝,如采用分枝定界,啟發式搜索等,適用范圍比較廣;二是使用一些小技巧,這類方法適用性雖不如第一類,有時甚至只能適用一道題,但也十分有效,并且幾乎每道題都存在一些這樣那樣的剪枝技巧,只是每題有所不同而已。

            剪枝的原則:
            1.正確性:必須保證不丟失正確的結果。
            2.準確性:能夠盡可能多的減去不能通向正解的枝條
            3.高效性:在很多時候,為了加強優化的效果,我們會增加一些判斷,這樣對程序效率也帶來了副作用,所以要考慮剪枝的高效性,否則得不償失。

            最后說一下:剪枝在搜索中用的是非常的廣泛的。

            參照杭電課件第47頁一句話:
            ACMer們:
            為了ACM事業,努力地剪枝吧?。?br>)

            題目我不多說,HDOJ 1010就是一個很好的剪枝題目。
            HDOJ 1010解答:
            http://www.wutianqi.com/?p=1345

            另外,杭電的課件–搜索篇里面也講了搜索與剪枝。

            posted on 2010-09-19 15:12 Tanky Woo 閱讀(2148) 評論(0)  編輯 收藏 引用
            国内精品久久久久影院日本| 伊人久久无码精品中文字幕| 久久综合狠狠综合久久| 综合网日日天干夜夜久久 | 久久精品亚洲精品国产欧美| 久久精品免费大片国产大片| 久久这里只精品99re66| 国产精品久久久久久影院| 看全色黄大色大片免费久久久| 精品人妻伦九区久久AAA片69| 国产欧美一区二区久久| 亚洲国产天堂久久久久久| 精品久久久久久久久午夜福利| 久久久久无码中| 99久久er这里只有精品18| 亚洲一区精品伊人久久伊人| 国产韩国精品一区二区三区久久 | 色播久久人人爽人人爽人人片AV| 无码人妻精品一区二区三区久久 | 一本一道久久精品综合| 丁香色欲久久久久久综合网| 精品久久久无码中文字幕天天| 无码人妻久久一区二区三区| 99久久香蕉国产线看观香| 久久精品无码一区二区三区免费| 91精品国产综合久久婷婷| 久久精品国产亚洲AV无码麻豆| 中文字幕无码精品亚洲资源网久久| 久久九色综合九色99伊人| 一本色道久久88加勒比—综合| 久久AV高清无码| 国产成人精品久久二区二区| 久久棈精品久久久久久噜噜| 午夜人妻久久久久久久久| 久久久久久久波多野结衣高潮| 午夜精品久久久久久影视riav| 久久久久久国产精品无码下载 | 久久婷婷五月综合97色一本一本| 热久久视久久精品18| 久久午夜无码鲁丝片秋霞| 一本久道久久综合狠狠爱|