[拼音]：sousuo

[外文]：search

尋找問題的解的過程或技術，是人工智能中問題求解的基本方法。

搜索空間與搜索圖

在問題求解中搜索空間包括狀態(tài)空間和一切非狀態(tài)空間。搜索過程中在計算機內部實際形成的部分搜索空間稱為搜索圖。搜索的目的就是用盡量小的搜索圖找到問題的解。

在問題求解系統(tǒng)中，問題表示有兩種基本方法：狀態(tài)空間表示法和問題歸約表示法。在狀態(tài)空間表示法中，狀態(tài)空間的節(jié)點表示狀態(tài)，即問題求解過程的不同階段，兩節(jié)點之間的有向弧線則代表狀態(tài)轉移。在問題歸約表示法中，原始問題被分解為若干子問題，這些子問題又進一步被分解為更低層次的若干子問題，節(jié)點之間的有向弧線則代表問題的歸約，這樣就形成了問題歸約空間。問題歸約空間和狀態(tài)空間是不同類型的搜索空間。

搜索空間一般用圖表示。在實際問題中有時搜索空間是無限的(如定理的機器證明情形)。在棋類游戲中雖然搜索空間有限，但有些棋類其不同棋局總數高達10¹²⁰。因此把同整個搜索空間對應的圖（稱為隱含圖）全部顯式表示出來既無可能也無必要。通常只將與部分搜索空間對應的隱含圖的子圖，即搜索圖顯式表示出來。

限制搜索量

搜索必須在合理的時間和計算機存儲容量條件下完成。對復雜的現實問題，窮舉搜索難以實現。例如要列出某種棋類游戲的全部可能著法，那么搜索空間內節(jié)點數將隨步數n成指數規(guī)律增長,這種現象稱為指數爆炸。限制搜索量的基本途徑是改進問題表示方法，采用啟發(fā)式搜索，引入問題求解的其他技術，例如行動計劃等。

無信息搜索

如果在搜索過程中不使用與問題領域有關的啟發(fā)信息，這種搜索就稱為無信息搜索，或盲式搜索。例如對搜索樹可按節(jié)點擴展順序予以分類。所謂擴展某一節(jié)點，指的是將該節(jié)點所有后繼節(jié)點全部求出。寬度優(yōu)先搜索是按照節(jié)點與起始節(jié)點相隔輩分的高低來擴展節(jié)點的,也就是說在所有長度為n的算子序列分析完畢以前不考慮長度為 n+1的算子序列。如果問題的解存在，用寬度優(yōu)先搜索策略可望得到最短的算子序列，即最短的解題通路。深度優(yōu)先搜索的特征是首先擴展最新生成的或最深的節(jié)點，直到已無可擴展的節(jié)點或搜索深度已達到規(guī)定限度。這時返回到最鄰近的分支，繼續(xù)搜索。無信息搜索雖然方法簡單，但效率很低，難以用于直接解決復雜的實際問題。

啟發(fā)式搜索

一種依靠直觀和經驗知識的搜索方法。如運用得當，能大幅度地減少搜索工作量。但是啟發(fā)式搜索并不保證獲得問題的最優(yōu)解，甚至還不一定保證得到問題的一個解。實踐表明，如果問題有解，好的啟發(fā)式搜索方法在大多數場合下能給出令人滿意的結果。運用啟發(fā)式搜索的基本方法如下：

（1）決定下一步要擴展的節(jié)點（并不機械地遵循寬度優(yōu)先或深度優(yōu)先方法），有序搜索或稱最佳優(yōu)先搜索就遵循這一途徑。每次選擇最有希望的節(jié)點優(yōu)先擴展。為了對“有希望”的程度進行度量，需要建立評價函數?！坝邢Ｍ钡暮x和相應評價函數的具體構造完全取決于問題的性質和要求。這里需要權衡的兩個因素是解的簡明性（搜索圖的解題通路所花費的節(jié)點和有向弧線數目最?。┖退阉鞴ぷ髁康拇笮　τ谟行驙顟B(tài)空間搜索，已按照使解題通路花費最小的目的建立了A^* 算法和相應的評價函數。這類A^* 算法還以分枝限界法的名稱在運籌學中得到廣泛的應用。

（2）在對節(jié)點進行擴展時決定哪一個或哪一些后繼節(jié)點首先生成，而不是盲目地同時生成所有后繼節(jié)點，許多博弈程序遵循這一途徑，如對策樹搜索。

（3）決定有些節(jié)點不再展開，應從搜索樹中剪除。剪除的原因可能是因為展開這些節(jié)點對找到解題通路的作用不大，也可能是出于其他策略的考慮。

對策樹搜索

采用最小最大方法的基本技術。下圖為一對策樹，樹中每一節(jié)點代表一個棋局的局面。樹的非終端標上棋手代碼，表示此時由該方走下一步棋。所謂最小最大方法是兩人共同遵循的策略，即一方希望自己得分最大，因此稱max方,而另一方則希望自己得分最小,因此稱min方。對策樹的終端節(jié)點（終結局面）用靜態(tài)評價函數評分。當棋手從某一局面出發(fā)決定下一步棋時,要對該局面用返回法評分。對策樹是一種與或樹(見問題求解),凡一方能控制的局面其后繼節(jié)點是或節(jié)點，一方不能控制的局面其后繼節(jié)點則是與節(jié)點。圖中的對策樹是站在max一方畫出的。在圖a中，不管評價函數F(5)的值是多少,max一方在局面①能確保的下限值（或稱α 值）為F(2)=15,所以節(jié)點⑤已沒有必要擴展而予以剪除，稱為α 截枝；同理圖b不管評價函數 F(7)的值是多少,max一方在局面①得分的上限值（或稱β值）為F(4)=20,節(jié)點⑦也不再擴展而予以剪除,稱為β 截枝，α截枝和β 截枝統(tǒng)稱為α–β剪枝技術,它改進了原來實施窮舉搜索的最小最大法，從而提高了搜索效率。人們一度曾將α–β剪枝技術看成是啟發(fā)式方法,后來證明它有嚴格的理論算法。

參考書目

1. N.J.尼爾遜著，石純一等譯：《人工智能原理》，科學出版社，北京，1983。(N.J.Nilsson, Principles of Artificial Intelligence, Tioga Publ. Co., New York, 1980.)
2. Judea Pearl,Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley Publ.Co.,Inc., Reading, Mass.,1984.

參考文章

• 小馬發(fā)現拼多多APP上有砍價免費拿活動，但在缺少助力無法提現，遂到QQ群搜索”拼多多代砍”，并添加了一名”代砍人員”。該”代砍人員”發(fā)送給小馬一個付款二維碼，并告知小馬此二維碼為拼多多付款程序的破解程序，按照程序給定指示完成不扣費付款即可拿到拼多多的活動生活安全
• 搜索枯腸造句素材
• 百度APP移動搜索落地頁體驗白皮書5.0全文在線閱讀信息技術
• 2018年6月，江蘇一男子因2歲兒子被泰迪咬傷后與狗主人發(fā)生糾紛，結果遭遇“人肉搜索”和死亡威脅，其妻迫于網絡暴力割腕自殺，所幸搶救及時；2018年4月，陜西一男童在餐廳內被一孕婦絆腳的視頻在網絡曝光，孕婦遭遇“人肉搜索”，卻導致另一名孕婦“躺槍”，個人信息被生活安全
• 帶“搜索”的詩句大全（13句）文學

建筑資質代辦咨詢熱線：13198516101

標簽：搜索

版權聲明：本文采用知識共享 署名4.0國際許可協議 [BY-NC-SA] 進行授權

文章名稱：《搜索》

文章鏈接：http://www.fjemb.com/13495.html

該作品系作者結合建筑標準規(guī)范、政府官網及互聯網相關知識整合。如若侵權請通過投訴通道提交信息，我們將按照規(guī)定及時處理。