搜索演算法產生的時間

㈠ 啟發式搜索演算法的產生背景

何謂啟發式搜索演算法
在說它之前先提狀態空間搜索。狀態空間搜索，如果按專業點的說法就是將問題求解過程表現為從初始狀態到目標狀態尋找這個路徑的過程。通俗點說，兩點之間求一線路，這兩點是求解的開始和問題的結果，而這一線路不一定是直線，可以是曲折的。由於求解問題的過程中分枝有很多，主要是求解過程中求解條件的不確定性，不完備性造成的，使得求解的路徑很多這就構成了一個圖，我們說這個圖就是狀態空間。問題的求解實際上就是在這個圖中找到一條路徑可以從開始到結果。這個尋找的過程就是狀態空間搜索。
常用的狀態空間搜索有深度優先和廣度優先。深度優先是從初始狀態一層一層向下找，直到找到目標為止。廣度優先是按照一定的順序前查找完一個分支，再查找另一個分支，以至找到目標為止。這兩種演算法在數據結構書中都有描述，可以參看這些書得到更詳細的解釋。
前面說的廣度和深度優先搜索有一個很大的缺陷就是他們都是在一個給定的狀態空間中窮舉。這在狀態空間不大的情況下是很合適的演算法，可是當狀態空間十分大，且不預測的情況下就不可取了。他的效率實在太低，甚至不可完成。在這里就要用到啟發式搜索了。

㈡ 演算法-二分搜索演算法

演算法：二分搜索演算法（折半查找演算法）
時間復雜度：

二分搜索演算法，也稱折半查找演算法，即在一個有序數組中查找某一個特定元素。整個搜索過程從中間開始，如果要查找的元素即中間元素，那麼搜索過程結束；反之根據中間元素與要查找元素的關系在數組對應的那一半查找，例如查找元素大於中間元素，則在整個數組較大元素的那一半查找，反復進行這個過程，直到找到元素，或者數組為空，查找不到元素。

給定一個數組 A_0,A_1...A_{n-1} ， A_0 \le A_1 \le \cdot \le A_{n - 1} ，待查找元素為 searchnum ：

BINARY-SEARCH-WHILE(A, searchnum, left, right)

BINARY-SEARCH-RECURSION(A, searchnum, left, right)

外部定義全局變數：

㈢ 幾種常見的查找演算法之比較

二分法平均查找效率是O(logn)，但是需要數組是排序的。如果沒有排過序，就只好先用O（nlogn)的預處理為它排個序了。而且它的插入比較困難，經常需要移動整個數組，所以動態的情況下比較慢。

哈希查找理想的插入和查找效率是O(1)，但條件是需要找到一個良好的散列函數，使得分配較為平均。另外，哈希表需要較大的空間，至少要比O(n)大幾倍，否則產生沖突的概率很高。

二叉排序樹查找也是O(logn)的，關鍵是插入值時需要做一些處理使得它較為平衡（否則容易出現輕重的不平衡，查找效率最壞會降到O(n)），而且寫起來稍微麻煩一些，具體的演算法你可以隨便找一本介紹數據結構的書看看。當然，如果你用的是c語言，直接利用它的庫類型map、multimap就可以了,它是用紅黑樹實現的，理論上插入、查找時間都是O(logn)，很方便，不過一般會比自己實現的二叉平衡樹稍微慢一些。

㈣ 搜索技術

問題求解過程是 搜索答案（目標） 的過程，所以問題求解技術也叫做搜索技術——通過對 狀態空間 的搜索而求解問題的技術。

問題可形式化地定義成四個組成部分

在解題過程中 達到過的所有狀態 的集合。不同於狀態空間，搜索空間是其中一部分。狀態空間和搜索空間都屬於 過程性知識表示 。

八數碼問題詳解

兩種搜索技術

無信息搜索策略也稱 盲目搜索 ：沒有任何附加信息，只有生成後繼和區分目標和非目標狀態。
五種盲目搜索策略有：廣度優先搜索，代價一直搜索，深度優先搜索，深度有限搜索，迭代深入深度優先搜索。

從四種度量來評價廣度優先搜索

性能：通常使用遞歸函數實現，一次對當前節點的子節點調用該函數。相比廣度優先，內存需求少(分支因子 * 最大深度+1)。但 不是完備的也不是最優的 *。

深度優先搜索的無邊界問題可以通過提供一個 預先設定的深度限制I 來解決。深度=I的節點當作無後繼節點看待；雖然解決了無邊界問題，但 有可能無解 ； 如果選擇I>d則深度優先原則也不是最優解 。

每次改變限制深度 ，多次調用深度有限搜索，當 搜索到達最淺的目標節點深度 時就可以發現目標節點，稱為迭代深入深度優先搜索。這種搜索結合了廣度優先和深度優先兩種搜索方式的優勢。 解決了深度優先的完備性問題 。空間需求是(b * d),時間需求是(b d )。當搜索空間很大且深度未知時，迭代深入深度優先搜索 是首選的無信息搜索方式 。

迭代深入搜索中因為多次重復搜索上層節點，使部分狀態反復生成，看起來很浪費內存空間和時間。但是因為 在分支因子比較均衡的搜索樹 中， 多數節點都是葉子節點 *（葉子節點數遠大於上層節點總和），所以上層節點多次生成的影響並不大，與廣度優先相比，效率還是很高。

用於目標狀態已知，求解過程的問題。通常通過 廣度優先搜索 實現。從 起始節點和目標狀態兩個方向 開始擴展，當 兩個OPEN表出現交集 時表明搜索到了一條從起始到結果的一條路徑。 缺點 ：演算法編寫難。但一旦實現，效率要遠高於其他盲目搜索。

評價函數 ：f ( n ) = h ( n ) ；評價函數等於啟發函數
解釋：貪婪最佳優先搜索中 無條件選擇 當前離目標最近（代價最小）的結點進行擴展。但是 局部最佳不是全局最佳，即非最優。 其中h（ n ）稱為 啟發函數 ，是從節點n到目標節點的最低代價的 估計值 。

評價函數 ：f ( n ) = g ( n ) + h ( n )；評價函數等於啟發函數加路徑耗散函數
解釋：

另，對於有向圖的搜索還可以採用圖搜索方式。詳情： 圖搜索和樹搜索詳解

稱啟發函數是可採納的，如果h( n ) 滿足 h( n ) ≤ h * ( n ) ，其中 h * ( n )是從當前節點 n到達目標的最低真實代價 ，即h( n )的估值永遠小於真實耗散值；因為f ( n ) = g ( n ) + h ( n )，且g（n）為已知常數，所以 f（n）永遠不會高估經過結點n的解的實際代價 ，所以是最優解。

如果採用 A* 圖搜索演算法，則不一定返回最優解 。因為如果最優路徑不是第一個生成的，可能因為有重復狀態而被丟棄了。見上個鏈接： 圖搜索和樹搜索詳解

如果對於每個結點n，以及n的行為a產生的後繼結點n'滿足如下公式： h ( n ) ≤ c ( n, n', a) + h( n ') （c ( n, n', a)可以理解為g（n'）），則稱這個h ( n )啟發函數是一致的。

A* 搜索由初始結點出發開始搜索，以同心帶狀增長f（n）耗散值的方式擴展結點。如果h（n）= 0 意味著只按g（n）值排序，即同心帶為「圓形」。使用啟發函數則同心帶向目標節點拉伸（橢圓越來越扁）。

如果C*是最優路徑的耗散值，則：

A* 搜索的關鍵就是 設計可採納的或一致的（單調的）啟發函數 。

絕不高估 到達目標的耗散值，盡可能的接近真實耗散值

子問題的解耗散是完整問題的 耗散下界 。

從實例中學習，每個實例包含了解路徑上各狀態及其到達解的耗散值。每個最優解實例提供了可學習h(n)的實例，由此產生可預測其他狀態解消耗的啟發函數。

聯機搜索智能體需要行動和感知，然後擴展當前狀態的環境地圖

智能體初始位置在S，其已知信息為：

A* 搜索在不同子空間結點的跳躍式擴展， 模擬而非實際行動 ；聯機搜索只擴展實際占據的結點——採用深度優先。 聯機搜索必須維護一個回溯表

博弈搜索是智能體之間的對抗，每個智能體的目的是沖突的。本節需要解決兩個問題：如何搜索到取勝的 路徑 /如何提高搜索 效率 。相應的辦法是 極大極小決策和α-β剪枝 。

兩個智能體博弈時，可令一方為MAX，一方為MIN。MAX希望終局得分高，MIN希望終局得分低。

博弈搜索中，最優解是導致取勝的終止狀態的一系列招數。MAX制定取勝策略時，必須不斷考慮MIN應對條件下如何取勝。

如果博弈雙方 都按照最優策略 進行，則一個結點的 極大極小值就是對應狀態的效用值

簡單的遞歸演算法——按照定義計算每個後繼結點的極大極小值/搜索是從目標到初始結點的 反向推導

如果博弈樹最大深度為m，每個節點的合法招數為b，則

剪掉那些不可能影響最後決策的分支，返回和極大極小值相同的結果。
α-β剪枝可以應用樹的任何深度。

如果在結點n的父節點或更上層有一個更好的選擇m，則在搜索中永遠不會到達n。

很大程度上取決於檢查後繼節點的次序—— 應先檢查那些可能更好的後繼 。如果能先檢查那些最好的後繼，則 時間復雜度為O(b (d/2) ) 。優於極大極小演算法的O(b d )

許多問題中 路徑是無關緊要的 。從當前狀態出發，通常 只移動到相鄰狀態 ，且路徑不保留。

內存消耗少，通常是一個常數。

向目標函數值增加的方向持續移動，直到相鄰狀態沒有比它更高的值。 取到一個局部最優則終止 。
使新狀態估計值優於當前狀態值和其他所有候補結點值，則取新狀態放棄其他狀態。

將 爬山法 （停留在局部最優）和 隨機行走 （下山）以某種方式結合，同時擁有 完備性和效率 。
技巧是，概率足夠大可以彈出局部最優；但概率不能太大而彈出全局最優。

按照模擬退火的思想， T隨時間逐漸減小 。如果 T下降的足夠慢 ，則找到全局最優解是 完備的 。

隨機移動，如果評價值改善則採納； 否則以小於一的概率接受 。

從 k個隨機生成的狀態開始 ，每步生成k個結點的所有後繼狀態。如果其中之一是目標狀態則停止演算法；否則從全部後繼狀態中選擇最佳的k個狀態繼續搜索。
有用的信息 在k個並行的 搜索線程之間傳遞 ，演算法會很快放棄沒有成果的搜索，而把資源放在取得最大進展的搜索上。

局部剪枝搜索的變種。因為局部剪枝搜索搜索是貪婪的，因而用隨機剪枝搜索代替。不是選擇最好的k個後代，而是按照一定概率選取k個後繼狀態。

類似於自然界的選擇過程。狀態對應個體，其 值對應適應性 ，後代就是狀態。因此如果k個狀態缺乏多樣性，則局部搜索會受影響。

局部剪枝演算法已有 群體進化 （優勝劣汰）的趨勢。遺傳演算法是隨機剪枝的變種。

包括選擇，交叉和變異

又稱繁殖，按照一定的概率選擇兩對個體生成後繼狀態

計算每個個體i被選中的概率： pi = f(i) / [f(1)+...+f(n)] .然後根據概率將圓盤分為n個扇形，每個扇形大小為 2Πpi 。

繁殖過程中，後代是父串在雜交點上進行雜交得來的。這樣一來，後代子串保留了父串的優良特性又與父串不同。

首先以概率p隨機在種群中選擇pa和pb兩個個體，再從{1,2,...,m}中（可以按一定概率，如兩邊概率小於中間概率）選擇一個數i，作為交叉點。而後將兩個個體的交叉點後面的部分交換。

在新生成的後繼狀態中各個位置都會按照一個 獨立的很小的概率 隨機變異。
變異時要做到 一致變異 ；即相同概率地變異所有個體的每一位。

結合了「上山」和隨機行走，並在並行搜索線程之間交換信息。遺傳演算法的 最大優點在於雜交 。因為雜交可以 將獨立發展的若干個磚塊組合起來 ，提高搜索的粒度。

個體編碼某些位置上數字仍未確定的一個狀態子串。

如果 一個模式的實例的平均適應值超過均值 ，則種群內這個模式的實例數量會隨時間而增長（優勝）；反之則減少（劣汰）

長度較短，高於平均適應度的模式在遺傳運算元的作用下， 相互結合 ，能生成長度較長、適應度較高的 模式 。

Constraint Satisfying Problem，CSP。

由一個 變數集合{X1~Xn} 和一個 約束集合{C1~Cn} ；每個變數都有一個 非空可能的值域Di 。每個約束指定了 若干變數的一個子集內各變數的賦值范圍 。

CSP的一個狀態是，對一些或每個變數賦值

一組既是 相容賦值 又是 完全賦值 的對變數的賦值就是CSP的解。

提前考慮某些約束，以減少搜索空間

若X被賦值，檢查與X相連的Y，判斷是否滿足約束，去掉Y中不滿足約束的賦值。（進行某種檢驗，可以不為有問題的Y集合賦值 ）

㈤ 搜索演算法的介紹

搜索演算法是利用計算機的高性能來有目的的窮舉一個問題解空間的部分或所有的可能情況，從而求出問題的解的一種方法。

㈥ 二分查找法的具體演算法

折半查找法也稱為二分查找法，它充分利用了元素間的次序關系，採用分治策略，可在最壞的情況下用O(log n)完成搜索任務。它的基本思想是，將n個元素分成個數大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，演算法終止。如果x<a[n/2]，則我們只要在數組a的左半部繼續搜索x（這里假設數組元素呈升序排列）。如果x>a[n/2]，則我們只要在數組a的右半部繼續搜索x。二分搜索法的應用極其廣泛，而且它的思想易於理解，但是要寫一個正確的二分搜索演算法也不是一件簡單的事。第一個二分搜索演算法早在1946年就出現了，但是第一個完全正確的二分搜索演算法直到1962年才出現。Bentley在他的著作《Writing Correct Programs》中寫道，90%的計算機專家不能在2小時內寫出完全正確的二分搜索演算法。問題的關鍵在於准確地制定各次查找范圍的邊界以及終止條件的確定，正確地歸納奇偶數的各種情況，其實整理後可以發現它的具體演算法是很直觀的，我們可用C++描述如下：

template<class Type>

int BinarySearch(Type a[],const Type& x,int n)

{

int left=0;

int right=n-1;

while(left<=right){

int middle=(left+right)/2;

if (x==a[middle]) return middle;

if (x>a[middle]) left=middle+1;

else right=middle-1;

}

return -1;

}

模板函數BinarySearch在a[0]<=a[1]<=...<=a[n-1]共n個升序排列的元素中搜索x,找到x時返回其在數組中的位置，否則返回-1。容易看出，每執行一次while循環，待搜索數組的大小減少一半,因此整個演算法在最壞情況下的時間復雜度為O(log n)。在數據量很大的時候，它的線性查找在時間復雜度上的優劣一目瞭然。

㈦ 百度地圖的路徑搜索演算法

這個還是要問程序猿，現在比較流行A*演算法，至於網路是否開發出了新的演算法不得而知，畢竟沒有完全相同的程序。
給你看一篇文獻：
地圖中最短路徑的搜索演算法研究
學生:李小坤 導師：董巒
摘要：目前為止, 國內外大量專家學者對「最短路徑問題」進行了深入的研究。本文通過理論分析, 結合實際應用，從各個方面較系統的比較廣度優先搜索演算法(BFS)、深度優先搜索演算法(DFS)、A* 演算法的優缺點。
關鍵詞:最短路徑演算法；廣度優先演算法；深度優先演算法；A*演算法；
The shortest path of map's search algorithm
Abstract:So far, a large number of domestic and foreign experts and scholars on the" shortest path problem" in-depth study. In this paper, through theoretical analysis and practical application, comprise with the breadth-first search algorithm ( BFS ), depth-first search algorithm ( DFS ) and the A * algorithms from any aspects of systematic.
Key words: shortest path algorithm; breadth-first algorithm; algorithm; A * algorithm;
前言：
最短路徑問題是地理信息系統（GIS）網路分析的重要內容之一，而且在圖論中也有著重要的意義。實際生活中許多問題都與「最短路徑問題」有關, 比如: 網路路由選擇, 集成電路設計、布線問題、電子導航、交通旅遊等。本文應用深度優先演算法，廣度優先演算法和A*演算法，對一具體問題進行討論和分析，比較三種算的的優缺點。

在地圖中最短路徑的搜索演算法研究中，每種演算法的優劣的比較原則主要遵循以下三點:[1]
(1)演算法的完全性：提出一個問題，該問題存在答案，該演算法能夠保證找到相應的答案。演算法的完全性強是演算法性能優秀的指標之一。
(2)演算法的時間復雜性: 提出一個問題，該演算法需要多長時間可以找到相應的答案。演算法速度的快慢是演算法優劣的重要體現。
(3)演算法的空間復雜性:演算法在執行搜索問題答案的同時，需要多少存儲空間。演算法佔用資源越少，演算法的性能越好。
地圖中最短路徑的搜索演算法:
1、廣度優先演算法
廣度優先演算法(Breadth-First-Search)，又稱作寬度優先搜索，或橫向優先搜索，是最簡便的圖的搜索演算法之一，這一演算法也是很多重要的圖的演算法的原型,Dijkstra單源最短路徑演算法和Prim最小生成樹演算法都採用了和寬度優先搜索類似的思想。廣度優先演算法其別名又叫BFS，屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位址，徹底地搜索整張圖，直到找到結果為止。BFS並不使用經驗法則演算法。
廣度優先搜索演算法偽代碼如下：[2-3]
BFS(v)//廣度優先搜索G，從頂點v開始執行
//所有已搜索的頂點i都標記為Visited(i)=1.
//Visited的初始分量值全為0
Visited(v)=1;
Q=[];//將Q初始化為只含有一個元素v的隊列
while Q not null do
u=DelHead(Q);
for 鄰接於u的所有頂點w do
if Visited(w)=0 then
AddQ(w,Q); //將w放於隊列Q之尾
Visited(w)=1;
endif
endfor
endwhile
end BFS
這里調用了兩個函數：AddQ(w,Q)是將w放於隊列Q之尾；DelHead(Q)是從隊列Q取第一個頂點，並將其從Q中刪除。重復DelHead(Q)過程，直到隊列Q空為止。
完全性：廣度優先搜索演算法具有完全性。這意指無論圖形的種類如何，只要目標存在，則BFS一定會找到。然而，若目標不存在，且圖為無限大，則BFS將不收斂（不會結束）。
時間復雜度：最差情形下，BFS必須尋找所有到可能節點的所有路徑，因此其時間復雜度為,其中|V|是節點的數目，而 |E| 是圖中邊的數目。
空間復雜度：因為所有節點都必須被儲存，因此BFS的空間復雜度為，其中|V|是節點的數目，而|E|是圖中邊的數目。另一種說法稱BFS的空間復雜度為O(B),其中B是最大分支系數，而M是樹的最長路徑長度。由於對空間的大量需求，因此BFS並不適合解非常大的問題。[4-5]
2、深度優先演算法
深度優先搜索演算法（Depth First Search）英文縮寫為DFS，屬於一種回溯演算法，正如演算法名稱那樣，深度優先搜索所遵循的搜索策略是盡可能「深」地搜索圖。[6]其過程簡要來說是沿著頂點的鄰點一直搜索下去，直到當前被搜索的頂點不再有未被訪問的鄰點為止，此時，從當前輩搜索的頂點原路返回到在它之前被搜索的訪問的頂點，並以此頂點作為當前被搜索頂點。繼續這樣的過程，直至不能執行為止。
深度優先搜索演算法的偽代碼如下：[7]
DFS(v) //訪問由v到達的所有頂點
Visited(v)=1;
for鄰接於v的每個頂點w do
if Visited(w)=0 then
DFS(w);
endif
endfor
end DFS
作為搜索演算法的一種，DFS對於尋找一個解的NP（包括NPC）問題作用很大。但是，搜索演算法畢竟是時間復雜度是O(n!)的階乘級演算法，它的效率比較低，在數據規模變大時，這種演算法就顯得力不從心了。[8]關於深度優先搜索的效率問題，有多種解決方法。最具有通用性的是剪枝，也就是去除沒有用的搜索分支。有可行性剪枝和最優性剪枝兩種。
BFS:對於解決最短或最少問題特別有效，而且尋找深度小，但缺點是內存耗費量大（需要開大量的數組單元用來存儲狀態）。
DFS：對於解決遍歷和求所有問題有效，對於問題搜索深度小的時候處理速度迅速，然而在深度很大的情況下效率不高。
3、A*演算法
1968年的一篇論文，「P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths in graphs. IEEE Trans. Syst. Sci. and Cybernetics, SSC-4(2):100-107, 1968」。[9]從此，一種精巧、高效的演算法——A*演算法問世了，並在相關領域得到了廣泛的應用。A* 演算法其實是在寬度優先搜索的基礎上引入了一個估價函數,每次並不是把所有可擴展的結點展開,而是利用估價函數對所有未展開的結點進行估價, 從而找出最應該被展開的結點,將其展開,直到找到目標節點為止。
A*演算法主要搜索過程偽代碼如下：[10]
創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
算起點的估價值;
將起點放入OPEN表;
while(OPEN!=NULL) //從OPEN表中取估價值f最小的節點n;
if(n節點==目標節點) break;
endif
for(當前節點n 的每個子節點X)
算X的估價值;
if(X in OPEN)
if(X的估價值小於OPEN表的估價值)
把n設置為X的父親;
更新OPEN表中的估價值; //取最小路徑的估價值;
endif
endif
if(X inCLOSE)
if( X的估價值小於CLOSE表的估價值)
把n設置為X的父親;
更新CLOSE表中的估價值;
把X節點放入OPEN //取最小路徑的估價值
endif
endif
if(X not inboth)
把n設置為X的父親;
求X的估價值;
並將X插入OPEN表中; //還沒有排序
endif
end for
將n節點插入CLOSE表中;
按照估價值將OPEN表中的節點排序; //實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。
end while(OPEN!=NULL)
保存路徑，即 從終點開始，每個節點沿著父節點移動直至起點，這就是你的路徑；
A *演算法分析：
DFS和BFS在展開子結點時均屬於盲目型搜索，也就是說，它不會選擇哪個結點在下一次搜索中更優而去跳轉到該結點進行下一步的搜索。在運氣不好的情形中，均需要試探完整個解集空間, 顯然，只能適用於問題規模不大的搜索問題中。而A*演算法與DFS和BFS這類盲目型搜索最大的不同，就在於當前搜索結點往下選擇下一步結點時，可以通過一個啟發函數來進行選擇，選擇代價最少的結點作為下一步搜索結點而跳轉其上。[11]A *演算法就是利用對問題的了解和對問題求解過程的了解, 尋求某種有利於問題求解的啟發信息, 從而利用這些啟發信息去搜索最優路徑.它不用遍歷整個地圖, 而是每一步搜索都根據啟發函數朝著某個方向搜索.當地圖很大很復雜時, 它的計算復雜度大大優於D ijks tr a演算法, 是一種搜索速度非常快、效率非常高的演算法.但是, 相應的A*演算法也有它的缺點.啟發性信息是人為加入的, 有很大的主觀性, 直接取決於操作者的經驗, 對於不同的情形要用不同的啟發信息和啟發函數, 且他們的選取難度比較大,很大程度上找不到最優路徑。
總結：
本文描述了最短路徑演算法的一些步驟，總結了每個演算法的一些優缺點，以及演算法之間的一些關系。對於BFS還是DFS，它們雖然好用，但由於時間和空間的局限性，以至於它們只能解決規模不大的問題，而最短或最少問題應該選用BFS,遍歷和求所有問題時候則應該選用DFS。至於A*演算法，它是一種啟發式搜索演算法，也是一種最好優先的演算法，它適合於小規模、大規模以及超大規模的問題，但啟發式搜索演算法具有很大的主觀性，它的優劣取決於編程者的經驗，以及選用的啟發式函數，所以用A*演算法編寫一個優秀的程序，難度相應是比較大的。每種演算法都有自己的優缺點，對於不同的問題選擇合理的演算法，才是最好的方法。
參考文獻：
[1]陳聖群,滕忠堅,洪親,陳清華.四種最短路徑演算法實例分析[J].電腦知識與技術(學術交流),2007(16):1030-1032
[2]劉樹林,尹玉妹.圖的最短路徑演算法及其在網路中的應用[J].軟體導刊,2011(07):51-53
[3]劉文海,徐榮聰.幾種最短路徑的演算法及比較[J].福建電腦，2008(02）:9-12
[4]鄧春燕.兩種最短路徑演算法的比較[J].電腦知識與技術，2008（12）：511-513
[5]王蘇男,宋偉,姜文生.最短路徑演算法的比較[J].系統工程與電子技術,1994(05)：43-49
[6]徐鳳生,李天志.所有最短路徑的求解演算法[J].計算機工程與科學,2006(12)：83-84
[7]李臣波,劉潤濤.一種基於Dijkstra的最短路徑演算法[J].哈爾濱理工大學學報,2008(03)：35-37
[8]徐鳳生.求最短路徑的新演算法[J].計算機工程與科學,2006(02).
[9] YanchunShen . An improved Graph-based Depth-First algorithm and Dijkstra algorithm program of police patrol [J] . 2010 International Conference on Electrical Engineering and Automatic Control , 2010(3) : 73-77
[10]部亞松.VC++實現基於Dijkstra演算法的最短路徑[J].科技信息(科學教研),2008(18)：36-37
[11] 楊長保,王開義,馬生忠.一種最短路徑分析優化演算法的實現[J]. 吉林大學學報(信息科學版),2002(02)：70-74

㈧ 搜索引擎技術

搜索引擎技術 概述
隨著互聯網的迅猛發展、WEB信息的增加，用戶要在信息海洋里查找自己所需的信息，就象大海撈針一樣，搜索引擎技術恰好解決了這一難題（它可以為用戶提供信息檢索服務）。搜索引擎是指互聯網上專門提供檢索服務的一類網站，這些站點的伺服器通過網路搜索軟體(例如網路搜索機器人)或網路登錄等方式，將Intemet上大量網站的頁面信息收集到本地，經過加工處理建立信息資料庫和索引資料庫，從而對用戶提出的各種檢索作出響應，提供用戶所需的信息或相關指針。用戶的檢索途徑主要包括自由詞全文檢索、關鍵詞檢索、分類檢索及其他特殊信息的檢索(如企業、人名、電話黃頁等)。下面以網路搜索機器人為例來說明搜索引擎技術。
[編輯本段]1．網路機器人技術
網路機器人(Robot)又被稱作Spider、Worm或Random，核心目的是為獲取Internet上的信息。一般定義為「一個在網路上檢索文件且自動跟蹤該文件的超文本結構並循環檢索被參照的所有文件的軟體」。機器人利用主頁中的超文本鏈接遍歷WWW，通過U趾引用從一個HT2LIL文檔爬行到另一個HTML文檔。網上機器人收集到的信息可有多種用途，如建立索引、HIML文件合法性的驗證、uRL鏈接點驗證與確認、監控與獲取更新信息、站點鏡像等。 機器人安在網上爬行，因此需要建立一個URL列表來記錄訪問的軌跡。它使用超文本，指向其他文檔的URL是隱藏在文檔中，需要從中分析提取URL，機器人一般都用於生成索引資料庫。所有WWW的搜索程序都有如下的工作步驟： (1)機器人從起始URL列表中取出URL並從網上讀取其指向的內容； (2)從每一個文檔中提取某些信息(如關鍵字)並放入索引資料庫中； (3)從文檔中提取指向其他文檔的URL，並加入到URL列表中； (4)重復上述3個步驟，直到再沒有新的URL出現或超出了某些限制(時間或磁碟空間)； (5)給索引資料庫加上檢索介面，向網上用戶發布或提供給用戶檢索。 搜索演算法一般有深度優先和廣度優先兩種基本的搜索策略。機器人以URL列表存取的方式決定搜索策略：先進先出，則形成廣度優先搜索，當起始列表包含有大量的WWW伺服器地址時，廣度優先搜索將產生一個很好的初始結果，但很難深入到伺服器中去；先進後出，則形成深度優先搜索，這樣能產生較好的文檔分布，更容易發現文檔的結構，即找到最大數目的交叉引用。也可以採用遍歷搜索的方法，就是直接將32位的IP地址變化，逐個搜索整個Intemet。 搜索引擎是一個技術含量很高的網路應用系統。它包括網路技術、資料庫技術動標引技術、檢索技術、自動分類技術，機器學習等人工智慧技術。
[編輯本段]2．索引技術
索引技術是搜索引擎的核心技術之一。搜索引擎要對所收集到的信息進行整理、分類、索引以產生索引庫，而中文搜索引擎的核心是分詞技術。分詞技術是利用一定的規則和詞庫，切分出一個句子中的詞，為自動索引做好准備。目前的索引多採用Non—clustered方法，該技術和語言文字的學問有很大的關系，具體有如下幾點： (1)存儲語法庫，和詞彙庫配合分出句子中的詞彙； (2)存儲詞彙庫，要同時存儲詞彙的使用頻率和常見搭配方式； (3)詞彙寬，應可劃分為不同的專業庫，以便於處理專業文獻； (4)對無法分詞的句子，把每個字當作詞來處理。 索引器生成從關鍵詞到URL的關系索引表。索引表一般使用某種形式的倒排表(1nversionUst)，即由索引項查找相應的URL。索引表也要記錄索引項在文檔中出現的位置，以便檢索器計算索引項之間的相鄰關系或接近關系，並以特定的數據結構存儲在硬碟上。 不同的搜索引擎系統可能採用不盡相同的標引方法。例如Webcrawler利用全文檢索技術，對網頁中每一個單詞進行索引；Lycos只對頁名、標題以及最重要的100個注釋詞等選擇性詞語進行索引；Infoseek則提供概念檢索和片語檢索，支持and、or、near、not等布爾運算。檢索引擎的索引方法大致可分為自動索引、手工索引和用戶登錄三類。
[編輯本段]3. 檢索器與結果處理技術
檢索器的主要功能是根據用戶輸入的關鍵詞在索引器形成的倒排表中進行檢索，同時完成頁面與檢索之間的相關度評價，對將要輸出的結果進行排序，並實現某種用戶相關性反饋機制。 通過搜索引擎獲得的檢索結果往往成百上千，為了得到有用的信息，常用的方法是按網頁的重要性或相關性給網頁評級，進行相關性排序。這里的相關度是指搜索關鍵字在文檔中出現的額度。當額度越高時，則認為該文檔的相關程度越高。能見度也是常用的衡量標准之一。一個網頁的能見度是指該網頁入口超級鏈接的數目。能見度方法是基於這樣的觀點：一個網頁被其他網頁引用得越多，則該網頁就越有價值。特別地，一個網頁被越重要的網頁所引用，則該網頁的重要程度也就越高。結果處理技術可歸納為： (1)按頻次排定次序 通常，如果一個頁麵包含了越多的關鍵詞，其搜索目標的相關性應該越好，這是非常合平常理的解決方案。 (2)按頁面被訪問度排序 在這種方法中，搜索引擎會記錄它所搜索到的頁面被訪問的頻率。人們訪問較多的頁面通常應該包含比較多的信息，或者有其他吸引入的長處。這種解決方案適合一般的搜索用戶，而因為大部分的搜索引擎都不是專業性用戶，所以這種方案也比較適合一般搜索引擎使用。 (3)二次檢索 進一步凈化(比flne)結果，按照一定的條件對搜索結果進行優化，可以再選擇類別、相關詞進行二次搜索等。 由於目前的搜索引擎還不具備智能，除非知道要查找的文檔的標題，否則排列第一的結果未必是「最好」的結果。所以有些文檔盡管相關程度高，但並不一定是用戶最需要的文檔。
[編輯本段]搜索引擎技術的行業應用
搜索引擎的行業應用一般指類似於千瓦通信提供的多種搜索引擎行業與產品應用模式，大體上分為如下幾種形式：
1、 政府機關行業應用
n 實時跟蹤、採集與業務工作相關的信息來源。 n 全面滿足內部工作人員對互聯網信息的全局觀測需求。 n 及時解決政務外網、政務內網的信息源問題，實現動態發布。 n 快速解決政府主網站對各地級子網站的信息獲取需求。 n 全面整合信息，實現政府內部跨地區、跨部門的信息資源共享與有效溝通。 n 節約信息採集的人力、物力、時間，提高辦公效率。
2、企業行業應用
n 實時准確地監控、追蹤競爭對手動態，是企業獲取競爭情報的利器。 n 及時獲取競爭對手的公開信息以便研究同行業的發展與市場需求。 n 為企業決策部門和管理層提供便捷、多途徑的企業戰略決策工具。 n 大幅度地提高企業獲取、利用情報的效率，節省情報信息收集、存儲、挖掘的相關費用，是提高企業核心競爭力的關鍵。 n 提高企業整體分析研究能力、市場快速反應能力，建立起以知識管理為核心的競爭情報數據倉庫，是提高企業核心競爭力的神經中樞。
3、新聞媒體行業應用
n 快速准確地自動跟蹤、採集數千家網路媒體信息，擴大新聞線索，提高採集速度。 n 支持每天對數萬條新聞進行有效抓取。監控范圍的深度、廣度可以自行設定。 n 支持對所需內容智能提取、審核。 n 實現互聯網信息內容採集、瀏覽、編輯、管理、發布的一體化。
4、 行業網站應用
n 實時跟蹤、採集與網站相關的信息來源。 n 及時跟蹤行業的信息來源網站，自動，快速更新網站信息。動態更新信息。 n 實現互聯網信息內容採集、瀏覽、編輯、管理、發布的一體化。 n 針對商務網站提出商務管理模式，大大提高行業網站的商務應用需求。 n 針對資訊網站分類目錄生成，提出用戶生成網站分類結構。並可以實時增加與更新分類結構。不受級數限制。從而大大利高行業的應用性。 n 提供搜索引擎SEO優化專業服務，快速提高行業網站的推廣。 n 提供與CCDC呼叫搜索引擎的廣告合作。建立行業網站聯盟，提高行業網站知名度。
5) 網路信息監察與監控
n 網路輿情系統。如「千瓦通信-網路輿情雷達監測系統」 n 網站信息與內容監察與監控系統，如「千瓦通信-網站信息與內容監測與監察系統（站內神探）」

㈨ 什麼是搜索引擎、它是在什麼背景下產生的、搜索引擎的發展歷史、最早的搜索引擎是哪一個、出現的時間

搜索引擎(search engine)是指根據一定的策略、運用特定的計算機程序搜集互聯網上的信息，在對信息進行組織和處理後，並將處理後的信息顯示給用戶，是為用戶提供檢索服務的系統。

互聯網發展早期，以雅虎為代表的網站分類目錄查詢非常流行。網站分類目錄由人工整理維護，精選互聯網上的優秀網站，並簡要描述，分類放置到不同目錄下。用戶查詢時，通過一層層的點擊來查找自己想找的網站。也有人把這種基於目錄的檢索服務網站稱為搜索引擎，但從嚴格意義上講，它並不是搜索引擎。 1990年，加拿大麥吉爾大學（University of McGill）計算機學院的師生開發出Archie。當時，萬維網（World Wide Web）還沒有出現，人們通過FTP來共享交流資源。Archie能定期搜集並分析FTP伺服器上的文件名信息，提供查找分別在各個FTP主機中的文件。用戶必須輸入精確的文件名進行搜索，Archie告訴用戶哪個FTP伺服器能下載該文件。雖然Archie搜集的信息資源不是網頁（HTML文件），但和搜索引擎的基本工作方式是一樣的：自動搜集信息資源、建立索引、提供檢索服務。所以，Archie被公認為現代搜索引擎的鼻祖。
所有搜索引擎的祖先，是1990年由Montreal的McGill University三名學生（Alan Emtage、Peter Deutsch、Bill Wheelan）發明的Archie（Archie FAQ）。Alan Emtage等想到了開發一個可以用文件名查找文件的系統，於是便有了Archie。Archie是第一個自動索引互聯網上匿名FTP網站文件的程序，但它還不是真正的搜索引擎。Archie是一個可搜索的FTP文件名列表，用戶必須輸入精確的文件名搜索，然後Archie會告訴用戶哪一個FTP地址可以下載該文件。 由於Archie深受歡迎，受其啟發，Nevada System Computing Services大學於1993年開發了一個Gopher（Gopher FAQ）搜索工具Veronica（Veronica FAQ）。Jughead是後來另一個Gopher搜索工具。

㈩ 三分搜索演算法的時間復雜度分析

首先第一點 時間復雜度在用大O表示時常數是沒有意義的,所以復雜度比較標準的寫法是O(log n)

得到這個復雜度 由以下遞推公式 設T(n)為演算法在長度為n的數組中的運行時間
T(n) = T(n/3) + O(1)
由主定理得
T(n) = O(log n)