基本介紹
- 中文名：多主機搜尋
- 外文名：Multi-master Search
- 學科：計算機科學
- 定義：在多台主機上進行搜尋信息
- 目的：避免延遲、個性化服務
- 套用：搜尋引擎
簡介,搜尋,概述,搜尋策略,搜尋引擎,
簡介
特別是近年來，移動設備不斷增多，移動設備如筆記本電腦、電子書籍、智慧型手機都要進行聯網。隨著用戶的增多，網路服務不可能完全滿足不同的各種個性化的需求，proxy也會變為通信的瓶頸，一種解決方法是以移動代碼的形式實現這些個性化的工具，這些移動代碼可以按用戶要求移動到相應的伺服器或proxy上，甚至可以移動到客戶主機上，移動代碼方法可以在通信雙方連結斷開的情況下繼續工作。
多主機搜尋是指用戶在網路上搜尋信息時不可能在一台伺服器上得到全部信息，往往要搜尋多台主機。為避免大的延遲，就要避免“星性循環”，即移動代碼首先進入第一個網址進行搜尋並將結果返回客戶，然後同樣的或不同的移動代碼又從客戶端出發進入第二個指定的網址……如此進行，直到用戶找到所需的信息。
搜尋
概述
人工智慧的基本技術之一，指計算機找出從初始狀態轉化到目標狀態的途徑，根據給定條件求解一個問題正確答案的過程。一個有趣的例子是：3個馴獸員帶著3隻熊和1條船在左岸(初始狀態)，要把人、熊、船都渡到右岸去(目標狀態)，給定條件是人或熊都會划船、但船每次最多只能裝載或兩人或兩熊或一人一熊、而且無論左岸或右岸都不允許出現熊多於人的情況(否則熊會傷人)，為順利到達右岸而尋找正確解決這個問題的可靠方法的過程就叫搜尋。
搜尋要講究策略方法，一個最佳搜尋的標準是：
(1)在問題有解的場合下能保證成功；
(2)必須花的搜尋工作量最少；
(3) 找到的途徑是最短的 (捷徑)；
(4)沿著找到的途徑進行實際操作的費用最小。實際上這4點很難同時滿足，只能根據具體情況選擇一種滿意的搜尋方法。
研究得較多的搜尋方法有： 狀態圖搜尋 (包括寬度優先搜尋和深度優先搜尋)、與或圖搜尋 (又稱問題分解搜尋)、啟發式搜尋等。
搜尋策略
寬度優先搜尋算法是沿著樹的寬度遍歷樹的節點，如果發現目標，則算法中止。屬於盲目搜尋。
深度優先搜尋沿著樹的最大深度方向生成節點並與目標節點進行比較，只有當上次訪問的節點不是目標節點，而且沒有其他節點可以生成的時候，才轉到上次訪問節點的父節點，然後搜尋該節點的其他子節點。因此深度優先搜尋也稱為回溯搜尋。它既不是完備的，也不是最優的。有時候，某些特定的問題會產生大量重複的節點。例如“八數碼”問題就是這樣的，當每次運用向上、向下、向左、向右移動空格的算符時，可能產生與已經產生的節點重複的節點。當再次搜尋到這個重複節點時，由於套用的算符基本一致，還會產生重複，所以為了節約時間和存儲空間，往往在深度優先算法中設立一個機制，用來刪除這些重複的節點，以提高效率。
疊代加深搜尋（ID搜尋）
對深度優先搜尋進行了一定改進，對搜尋樹的深度進行控制，即有界深度優先搜尋。
在程式找到目標之前，通過疊代不斷增大d以保證完備性和最優性。雖然會有不少重複搜尋，但是鑒於每增加一次d，則搜尋的時間複雜度會以指數級別增加，所以重複搜尋的時間可以忽略，亦可以與A*算法結合（即IDA*搜尋算法）來剪枝。
疊代加深搜尋通常用於那種搜尋樹又深又寬、但是解並不是很深的情況，這時廣度優先搜尋會超空間，而深度優先搜尋會逾時。這時疊代加深搜尋很有用，可是說是在用遞歸方法在實現廣度優先搜尋。
啟發式OR圖搜尋算法
爬山算法
模擬退火算法
最好優先
通用圖
A*
AND-OR圖啟發式搜尋
一個特殊問題：博弈論
約束滿足搜尋
搜尋策略還可以指在使用搜尋引擎中所使用的策略，它通常是搜尋之母，一個好的搜尋過程必定有一個好的搜尋策略來支持。
搜尋引擎
多主機搜尋套用最多的領域是搜尋引擎。
搜尋引擎（Search Engine）是指根據一定的策略、運用特定的電腦程式從網際網路上蒐集信息，在對信息進行組織和處理後，為用戶提供檢索服務，將用戶檢索相關的信息展示給用戶的系統。搜尋引擎包括全文索引、目錄索引、元搜尋引擎、垂直搜尋引擎、集合式搜尋引擎、門戶搜尋引擎與免費連結列表等。
一個搜尋引擎由搜尋器 、索引器 、檢索器 和用戶接口 四個部分組成。搜尋器的功能是在網際網路 中漫遊，發現和蒐集信息。索引器的功能是理解搜尋器所搜尋的信息，從中抽取出索引項，用於表示文檔 以及生成文檔庫的索引表。檢索器的功能是根據用戶的查詢在索引庫中快速檢出文檔，進行文檔與查詢的相關度評價，對將要輸出的結果進行排序，並實現某種用戶相關性反饋機制。用戶接口的作用是輸入用戶查詢、顯示查詢結果、提供用戶相關性反饋機制。
搜尋引擎的工作原理大致可以分為：
蒐集信息：搜尋引擎的信息蒐集基本都是自動的。搜尋引擎利用稱為網路蜘蛛的自動搜尋機器人程式來連上每一個網頁上的超連結。機器人程式根據網頁鏈到其中的超連結，就像日常生活中所說的“一傳十，十傳百……”一樣，從少數幾個網頁開始，連到資料庫上所有到其他網頁的連結。理論上，若網頁上有適當的超連結，機器人便可以遍歷絕大部分網頁。
整理信息：搜尋引擎整理信息的過程稱為“創建索引”。搜尋引擎不僅要保存蒐集起來的信息，還要將它們按照一定的規則進行編排。這樣，搜尋引擎根本不用重新翻查它所有保存的信息而迅速找到所要的資料。想像一下，如果信息是不按任何規則地隨意堆放在搜尋引擎的資料庫中，那么它每次找資料都得把整個資料庫完全翻查一遍，如此一來再快的計算機系統也沒有用。
接受查詢：用戶向搜尋引擎發出查詢，搜尋引擎接受查詢並向用戶返回資料。搜尋引擎每時每刻都要接到來自大量用戶的幾乎是同時發出的查詢，它按照每個用戶的要求檢查自己的索引，在極短時間內找到用戶需要的資料，並返回給用戶。目前，搜尋引擎返回主要是以網頁連結的形式提供的，這樣通過這些連結，用戶便能到達含有自己所需資料的網頁。通常搜尋引擎會在這些連結下提供一小段來自這些網頁的摘要信息以幫助用戶判斷此網頁是否含有自己需要的內容。
整理信息及接受查詢的過程，大量套用了文本信息檢索技術，並根據網路超文本的特點，引入了更多的信息。
