搜索

在人工智能中，搜索問題一般包括兩個(gè)重要的問題：

• 搜索什么：通常指目標(biāo)
• 在哪里搜索：即搜索空間，通常指一系列狀態(tài)的匯集，因此也稱為狀態(tài)空間

目錄

• 1 搜索引擎
• 2 搜索策略
  • 2.1 寬度優(yōu)先搜索
  • 2.2 深度優(yōu)先搜索
  • 2.3 迭代加深搜索
• 3 評(píng)價(jià)準(zhǔn)則
• 4 相關(guān)條目
• 5 參考資源

搜索引擎

搜索引擎（search engines）是一個(gè)為你提供信息“檢索”服務(wù)的網(wǎng)站，它使用某些程序把因特網(wǎng)上的所有信息歸類以幫助人們?cè)诿Ｃ＞W(wǎng)海中搜尋到所需要的信息，它包括信息搜集、信息整理和用戶查詢?nèi)糠?。目前常用的網(wǎng)絡(luò)搜索引擎有百度，Google，搜狐，雅虎，有道，中搜，搜搜，搜客等。

早期的搜索引擎是把因特網(wǎng)中的資源服務(wù)器的地址收集起來，由其提供的資源的類型不同而分成不同的目錄，再一層層地進(jìn)行分類。人們要找自己想要的信息可按他們的分類一層層進(jìn)入，就能最后到達(dá)目的地，找到自己想要的信息。這其實(shí)是最原始的方式，只適用于因特網(wǎng)信息并不多的時(shí)候。隨著因特網(wǎng)信息按幾何式增長(zhǎng)，出現(xiàn)了真正意義上的搜索引擎，這些搜索引擎知道網(wǎng)站上每一頁(yè)的開始，隨后搜索因特網(wǎng)上的所有超級(jí)鏈接，把代表超鏈接的所有詞匯放入一個(gè)數(shù)據(jù)庫(kù)。這就是現(xiàn)在搜索引擎的原型。

隨著yahoo!的出現(xiàn)，搜索引擎的發(fā)展也進(jìn)入了黃金時(shí)代，相比以前其性能更加優(yōu)越。現(xiàn)在的搜索引擎已經(jīng)不只是單純的搜索網(wǎng)頁(yè)的信息了，它們已經(jīng)變得更加綜合化，完美化了。以搜索引擎權(quán)威yahoo!為例，從1995年3月由美籍華裔楊致遠(yuǎn)等人創(chuàng)辦 yahoo!開始，到現(xiàn)在，他們從一個(gè)單一的搜索引擎發(fā)展到現(xiàn)在有電子商務(wù)、新聞信息服務(wù)、個(gè)人免費(fèi)電子信箱服務(wù)等多種網(wǎng)絡(luò)服務(wù)，充分說明了搜索引擎的發(fā)展從單一到綜合的過程。

然而由于搜索引擎的工作方式和因特網(wǎng)的快速發(fā)展，使其搜索的結(jié)果讓人越來越不滿意。例如，搜索 “電腦”這個(gè)詞匯，就可能有數(shù)百萬頁(yè)的結(jié)果。這是由于搜索引擎通過對(duì)網(wǎng)站的相關(guān)性來優(yōu)化搜索結(jié)果，這種相關(guān)性又是由關(guān)鍵字在網(wǎng)站的位置、網(wǎng)站的名稱、 標(biāo)簽等公式來決定的。這就是使搜索引擎搜索結(jié)果多而雜的原因。而搜索引擎中的數(shù)據(jù)庫(kù)因?yàn)橐蛱鼐W(wǎng)的發(fā)展變化也必然包含了死鏈接。

在百度、Google、雅虎等主流搜索引擎愈發(fā)發(fā)展成熟以外，各類不同的搜索大全也在今日的互聯(lián)網(wǎng)逐漸興起。搜索大全即為集各種不同類型搜索引擎，涵蓋多語言于一身的搜索集合。該類搜索引擎大全的興起，讓搜索變得更加簡(jiǎn)單。幾乎所有的內(nèi)容都能在“一頁(yè)之間”完成。

搜索策略

寬度優(yōu)先搜索

寬度優(yōu)先搜索算法是沿著樹的寬度遍歷樹的節(jié)點(diǎn)，如果發(fā)現(xiàn)目標(biāo)，則算法中止。屬于盲目搜索。 寬度優(yōu)先搜索的實(shí)現(xiàn)一般采用open-closed表。

深度優(yōu)先搜索

深度優(yōu)先搜索沿著樹的最大深度方向生成節(jié)點(diǎn)并與目標(biāo)節(jié)點(diǎn)進(jìn)行比較，只有當(dāng)上次訪問的節(jié)點(diǎn)不是目標(biāo)節(jié)點(diǎn)，而且沒有其他節(jié)點(diǎn)可以生成的時(shí)候，才轉(zhuǎn)到上次訪問節(jié)點(diǎn)的父節(jié)點(diǎn)，然后搜索該節(jié)點(diǎn)的其他子節(jié)點(diǎn)。因此深度優(yōu)先搜索也稱為回溯搜索。它既不是完備的，也不是最優(yōu)的。 有時(shí)候，某些特定的問題會(huì)產(chǎn)生大量重復(fù)的節(jié)點(diǎn)。例如“八數(shù)碼”問題就是這樣的，當(dāng)每次運(yùn)用向上、向下、向左、向右移動(dòng)空格的算符時(shí)，可能產(chǎn)生與已經(jīng)產(chǎn)生的節(jié)點(diǎn)重復(fù)的節(jié)點(diǎn)。當(dāng)再次搜索到這個(gè)重復(fù)節(jié)點(diǎn)時(shí)，由于應(yīng)用的算符基本一致，還會(huì)產(chǎn)生重復(fù)，所以為了節(jié)約時(shí)間和存儲(chǔ)空間，往往在寬度優(yōu)先算法中設(shè)立一個(gè)機(jī)制，用來刪除這些重復(fù)的節(jié)點(diǎn)，以提高效率。

迭代加深搜索

對(duì)深度優(yōu)先搜索進(jìn)行了一定改進(jìn)，對(duì)搜索樹的深度進(jìn)行控制，即有界深度優(yōu)先搜索。

但是深度限制值d的選取是一個(gè)問題，因此試圖嘗試所有可能的深度限制，即在找到目標(biāo)之前，通過迭代不斷增大d以保證完備性和最優(yōu)性。

啟發(fā)式OR圖搜索算法

• 爬山算法
• 模擬退火算法
• 最好優(yōu)先
• 通用圖
• A*

AND-OR 圖啟發(fā)式搜索

一個(gè)特殊問題：博弈論

約束滿足搜索

搜索策略還可以指在使用搜索引擎中所使用的策略，它通常是搜索之母，一個(gè)好的搜索過程必定有一個(gè)好的搜索策略來支持。

評(píng)價(jià)準(zhǔn)則

• 完備性
• 時(shí)間復(fù)雜性
• 空間復(fù)雜性
• 最優(yōu)性

相關(guān)條目

• SEO
• 數(shù)據(jù)結(jié)構(gòu)

參考資源

• 參考資源1
• 參考資源2