圖查詢演算法

⑴ 圖搜索演算法-A*演算法及其變種詳解

尋找圖中從一個位置到另一個位置的路徑是一個常見問題。我們需要找到的路徑滿足以下兩個條件：

1）路徑上經過的距離最短；

2）路徑上花費的旅行時間最少。

從起始點到達終點，找到最短路徑。

可以使用圖搜索演算法找到這個路徑。

廣度優先搜索（BFS）是最簡單的圖搜索演算法。A* 圖搜索演算法由它發展而來。

輸入：圖搜索演算法的輸入是一個圖，圖是一個位置（頂點）與將位置相連接的線（邊）的集合。

輸出：圖搜索演算法找到的路徑由圖的節點和邊組成。

圖搜索演算法可以分為三類：

1）廣度優先搜索。廣度優先搜索在所有方向上都進行平等地探索。

2）Dijkstra演算法（統一代價搜索）。Dijkstra演算法優先考慮探索哪些路徑。

3）A*演算法。A*演算法是對Dijkstra演算法的修改，該演算法針對單個目標進行優化。

廣度優先搜索的關鍵思想是：跟蹤一個稱為邊界的擴展環。

邊境如何擴張：

實現：

重復這些步驟，直到邊界為空：

1.從邊界中拾取並刪除一個位置。

2.通過觀察該位置的鄰居來擴展邊界。跳過牆壁（障礙）。將任何未到達的鄰居添加到邊界和到達集。

這個循環是圖形搜索演算法的精髓，包括A*。

但是如何找到最短的路徑呢？循環實際上並沒有構建路徑；它只是告訴我們如何參觀地圖上的一切。

每個位置的came_from都指向我們來自的地方。這些就像「麵包屑」。它們足以重建整個路徑。

重建路徑的代碼很簡單：沿著came_from的指向從目標向後移動到起點。

早退

利用廣度優先搜索，我們找到了從一個位置到所有其他位置的路徑。

廣度優先搜索種，路徑中的每一步具有相同的「成本」。

在某些尋路場景中，不同類型的移動會產生不同的成本。

在Dijkstra的演算法中，我們使用與起始點的實際距離將優先順序隊列排序。

相反，在貪婪最佳優先搜索（Greedy Best First Search）中，我們使用到目標的估計距離將優先順序隊列排序。

因此，當沒有太多障礙物，且路徑沒有那麼好時，這種演算法運行得比Dijkstra更快。

對復雜的圖，找到又快又短的路徑，可以使用A*演算法。

Dijkstra的演算法可以很好地找到最短路徑，但它浪費時間去探索那些沒有前景的方向。

A*演算法使用當前位置下與起點的實際距離和以及到目標的估計距離。

比較演算法：

Dijkstra的演算法計算與起點的距離。

Greedy Best First Search估計到目標點的距離。

A*使用這兩個距離的總和。

當Greedy Best First Search找到正確答案時，A*也會找到，探索同一領域。

A*是兩全其美。

應該使用哪種演算法在圖上查找路徑？

1.如果要查找從所有位置起始或到所有位置的路徑，使用廣度優先搜索或Dijkstra演算法。

2.如果想找到通往一個位置或幾個目標中最接近的位置的路徑，使用Greedy Best First Search或A*。

關於最佳路徑：

廣度優先搜索和Dijkstra演算法保證在給定輸入圖的情況下找到最短路徑。

如果啟發式距離從不大於真實距離，則保證A*找到最短路徑。

性能：

最好的做法是消除圖中不必要的位置。

減小圖的大小有助於所有的圖搜索演算法。

之後，盡可能使用最簡單的演算法，更簡單的隊列運行得更快。

貪婪最佳優先搜索通常比Dijkstra的演算法運行得更快，但不會產生最佳路徑。

A*是滿足大多數尋路需求的好選擇。

圖形搜索演算法可以用於任何類型的圖。

圖上的移動成本變成在圖邊上的權重。

啟發式距離不容易轉化到不同的圖中，必須為每種類型的圖設計一個啟發式距離。

⑵ 常見演算法5、廣度優先搜索 Breadth-First Search

1、定義

廣度優先搜索 （Breadth-First Search）是最簡便的圖的搜索演算法之一，又稱 寬度優先搜索 ，這一演算法也是很多重要的圖演算法的原型。廣度優先搜索屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。

2、應用

廣度優先搜索被用於解決 最短路徑問題（shortest-path problem） 。

廣度優先搜索讓你能夠找出兩樣東西之間的最短距離，不過最短距離的含義有很多！使用廣度優先搜索可以：

3、圖簡介

既然廣度優先搜索是作用於圖的一種演算法，這里對圖作一個簡單的介紹，先不深入了解。

圖由 節點 和 邊 組成。一個節點可能與多個節點相連，這些節點被稱為鄰居。

廣度優先演算法的核心思想是：從初始節點開始，應用算符生成第一層節點，檢查目標節點是否在這些後繼節點中，若沒有，再用產生式規則將所有第一層的節點逐一擴展，得到第二層節點，並逐一檢查第二層節點中是否包含目標節點。若沒有，再用算符逐一擴展第二層的所有節點……，如此依次擴展，檢查下去，直到發現目標節點為止。即

廣度優先搜索使用隊列（queue）來實現，整個過程也可以看做一個倒立的樹形。

例：假如你需要在你的人際關系網中尋找是否有職業為醫生的人，圖如下：

而使用廣度優先搜索工作原理大概如下 ：

1、python 3 ：

2、php ：

1、《演算法圖解》 https://www.manning.com/books/grokking-algorithms
2、SplQueue類： https://www.php.net/manual/zh/class.splqueue.php

⑶ 小圖或者搜局部圖搜完整圖或者大圖的圖像識別演算法

在一幅大圖中查找一幅它完全包含的小圖（這個小圖是大圖中包含的一個區域）

1.如果兩圖的明暗度相同只是數學上的問題
2.如果明暗不同怎樣把它們的明暗調整成一樣的
3.顏色不同時怎麼辦
兩個圖的大小相差太多時速度會很慢，2和3是可以轉成灰階圖後可以解決
明暗和顏色不同的圖灰階的結果完全不一樣，公司做具體比較詳細，江蘇視圖科技專業圖片識別搜索。

⑷ 百度圖片搜索引擎原理是如何實現的

圖片搜索的原理有三個步驟
1. 將目標圖片進行特徵提取，描述圖像的演算法很多，用的比較多的是：SIFT描述子，指紋演算法函數，bundling features演算法，hash function（散列函數）等。也可以根據不同的圖像，設計不同的演算法，比如圖像局部N階矩的方法提取圖像特徵。
2. 將圖像特徵信息進行編碼，並將海量圖像編碼做查找表。對於目標圖像，可以對解析度較大的圖像進行降采樣，減少運算量後在進行圖像特徵提取和編碼處理。
3. 相似度匹配運算：利用目標圖像的編碼值，在圖像搜索引擎中的圖像資料庫進行全局或是局部的相似度計算；根據所需要的魯棒性，設定閾值，然後將相似度高的圖片預保留下來；最後應該還有一步篩選最佳匹配圖片，這個應該還是用到特徵檢測演算法。
其中每個步驟都有很多演算法研究，圍繞數學，統計學，圖像編碼，信號處理等理論進行研究。

根據Neal Krawetz博士的解釋，原理非常簡單易懂。我們可以用一個快速演算法，就達到基本的效果。
這里的關鍵技術叫做"感知哈希演算法"（Perceptual hash algorithm），它的作用是對每張圖片生成一個"指紋"（fingerprint）字元串，然後比較不同圖片的指紋。結果越接近，就說明圖片越相似。下面是一個最簡單的實現：
第一步，縮小尺寸。
將圖片縮小到8x8的尺寸，總共64個像素。這一步的作用是去除圖片的細節，只保留結構、明暗等基本信息，摒棄不同尺寸、比例帶來的圖片差異。
第二步，簡化色彩。
將縮小後的圖片，轉為64級灰度。也就是說，所有像素點總共只有64種顏色。
第三步，計算平均值。
計算所有64個像素的灰度平均值。
第四步，比較像素的灰度。
將每個像素的灰度，與平均值進行比較。大於或等於平均值，記為1；小於平均值，記為0。
第五步，計算哈希值。
將上一步的比較結果，組合在一起，就構成了一個64位的整數，這就是這張圖片的指紋。組合的次序並不重要，只要保證所有圖片都採用同樣次序就行了。
得到指紋以後，就可以對比不同的圖片，看看64位中有多少位是不一樣的。在理論上，這等同於計算"漢明距離"（Hammingdistance）。如果不相同的數據位不超過5，就說明兩張圖片很相似；如果大於10，就說明這是兩張不同的圖片。
具體的代碼實現，可以參見Wote用python語言寫的imgHash.py。代碼很短，只有53行。使用的時候，第一個參數是基準圖片，第二個參數是用來比較的其他圖片所在的目錄，返回結果是兩張圖片之間不相同的數據位數量（漢明距離）。
這種演算法的優點是簡單快速，不受圖片大小縮放的影響，缺點是圖片的內容不能變更。如果在圖片上加幾個文字，它就認不出來了。所以，它的最佳用途是根據縮略圖，找出原圖。
實際應用中，往往採用更強大的pHash演算法和SIFT演算法，它們能夠識別圖片的變形。只要變形程度不超過25%，它們就能匹配原圖。這些演算法雖然更復雜，但是原理與上面的簡便演算法是一樣的，就是先將圖片轉化成Hash字元串，然後再進行比較。

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

這個還是要問程序猿，現在比較流行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