最優搜索演算法

『壹』 Matlab神經網路原理中可以用於尋找最優解的演算法有哪些

若果對你有幫助，請點贊。
神經網路的結構（例如2輸入3隱節點1輸出）建好後，一般就要求神經網路里的權值和閾值。現在一般求解權值和閾值，都是採用梯度下降之類的搜索演算法（梯度下降法、牛頓法、列文伯格-馬跨特法、狗腿法等等），這些演算法會先初始化一個解，在這個解的基礎上，確定一個搜索方向和一個移動步長（各種法算確定方向和步長的方法不同，也就使各種演算法適用於解決不同的問題），使初始解根據這個方向和步長移動後，能使目標函數的輸出（在神經網路中就是預測誤差）下降。 然後將它更新為新的解，再繼續尋找下一步的移動方向的步長，這樣不斷的迭代下去，目標函數（神經網路中的預測誤差）也不斷下降，最終就能找到一個解，使得目標函數（預測誤差）比較小。
而在尋解過程中，步長太大，就會搜索得不仔細，可能跨過了優秀的解，而步長太小，又會使尋解過程進行得太慢。因此，步長設置適當非常重要。
學習率對原步長（在梯度下降法中就是梯度的長度）作調整，如果學習率lr = 0.1,那麼梯度下降法中每次調整的步長就是0.1*梯度，
而在matlab神經網路工具箱里的lr,代表的是初始學習率。因為matlab工具箱為了在尋解不同階段更智能的選擇合適的步長，使用的是可變學習率，它會根據上一次解的調整對目標函數帶來的效果來對學習率作調整，再根據學習率決定步長。
機制如下：
if newE2/E2 > maxE_inc %若果誤差上升大於閾值
lr = lr * lr_dec; %則降低學習率
else
if newE2 < E2 %若果誤差減少
lr = lr * lr_inc;%則增加學習率
end
詳細的可以看《神經網路之家》nnetinfo里的《[重要]寫自己的BP神經網路(traingd)》一文，裡面是matlab神經網路工具箱梯度下降法的簡化代碼

『貳』 A*演算法 和 最佳優先搜索演算法（Best-First-Search）

最佳優先搜索演算法是一種啟發式搜索演算法（Heuristic Algorithm），其基於廣度優先搜索演算法，不同點是其依賴於估價函數對將要遍歷的節點進行估價，選擇代價小的節點進行遍歷，直到找到目標點為止。 BFS演算法不能保證找到的路徑是一條最短路徑，但是其計算過程相對於Dijkstra
演算法會快很多 。

最佳優先搜索是一種啟發式搜索演算法。廣度優先搜索和深度優先搜索都屬於窮舉類型的搜索，需要依次遍歷所有的節點，當空間非常大的時候，這種方式的效率就會非常差。而啟發式的搜索是對狀態控制項中的每個點進行評估，然後選出最好的位置。

啟發估價函數公式為：

n表示當前的點，g(n)為從起始點到點n的實際代價，h(n)為從點n到目標點的估價。

（圖片來源於網路）

A*演算法將BFS演算法和Dijkstra演算法結合在一起，結合兩演算法的優點，既可以查找最短路徑的，有擁有和BFS差不多的效率。

（圖片來源於網路）

A*演算法詳解

模擬尋路的地址

『叄』 數據結構中，查找演算法最優的是哪一種

折半查找法的平均查找長度隨n增大而呈現對數增長趨勢，因此折半查找法為最優查找演算法

『肆』 dfs演算法是什麼

DFS是深度優先搜索演算法。

深度優先搜索演算法，又稱DFS(Depth First Search)。DFS演算法是一種搜索演算法，而搜索演算法實質上是一種枚舉，即藉助計算機的高性能來有目的地枚舉一個問題的部分情況或這個問題的所有情況，進而求出問題的解的一種方法。

分類：

1. 順序性剪枝

若一些題的搜索順序對答案無影響，那麼搜索順序的不同會導致搜索樹形態的改變，優先搜索分支較少的階段，此時能減少搜索的規模。

2. 重復性剪枝

在搜索的時候如果有多種方式可以到達一個狀態，那麼只需要搜索一個分支就可以了。

3. 可行性剪枝

可行性剪枝是對搜索正確性的一個保證，當分支在遞歸邊界的時候回溯。

4. 最優性剪枝

在搜索過程中，如果當前階段的代價已經超過我們已知的最小代價，那麼此時繼續搜索下去就失去了意義。

5. 記憶化剪枝

記錄搜索狀態的結果，當重復遍歷一個狀態的時候就可以直接返回這個狀態的答案，避免重復的搜索。

『伍』 寬度優先搜索演算法(pascal)

寬度優先搜索（BFS，BreadthFirstSearch）是一種搜索演算法，其主要用來解決最優解問題。原型是圖的寬度優先遍歷問題，即從源頂點s出發，遍歷每一個節點，它的基本思路是：先擴展當前節點所有鄰接的節點，然後再從這些頂點出發，遍歷所有頂點，即分層處理，將遍歷路徑表示成樹，就是按層次遍歷。

寬度優先搜索實現要依賴隊列，即先進先出表（FIFO），這樣保證了搜索的順序正確。下面以圖的遍歷為例，寫出標准演算法（偽代碼）

BFS(G,s)

foreachvertexuexceptsdo//對除源頂點外的所有節點進行初始化

begin

visited[u]:=false;//是否訪問過

distance[u]:=infinite;//距源頂點距離

parent[u]:=NIL;//父節點

end;

visited[s]:=true;//對源頂點進行初始化

distance[s]:=0;

parent[s]:=NIL;

ENQUEUE(Q,s);//入隊；Q為隊列

whilenot(empty(Q))do //隊列不空

begin

u:=DEQUEUE(Q);//隊首元素出隊

foreachvertexVbelongstoAdj[u]do//擴展每個鄰接節點

ifvisited[v]=falsethen//如果未訪問

begin

visited[v]:=true;//標記已訪問

distance[v]:=distance[u]+1;//距離更新

parent[v]:=u;//父節點記錄

ENQUEUE(Q,v);//入隊

end;

end;

實際運用時要注意在達到結果後就要加一個break退出並輸出。為什麼寬度優先搜索能解決最優問題呢？因為根據寬搜的策略，被搜索到的頂點被戳上的distance標記就是到源頂點的最短路徑的距離，因此可以解決無權圖的最短路徑問題以及由其抽象而來的最優問題。

題目要求並不一樣，有的要求最優解大小，就可以直接輸出distance；有的要輸出最優解路徑、方法，可以用循環將parent層層取出，入棧調整順序輸出，這也算一個技巧。

也許你還看不懂演算法，可以找本演算法導論好好讀讀，上面的圖示對於理解很有幫助。

PS：敲完之後看了看網路，發現上面的內容完全改成了演算法導論，可以去看看。尤其圖示，很有幫助的。

『陸』 九宮格標注法中的A是什麼意思

A*演算法是尋找最優路徑的搜索演算法之一。常見的最優路徑搜索演算法有大英博物館過程、分支界限搜索等。與其它搜索演算法相比，A*演算法具有較高的搜索效率。本質上，A*搜索過程是帶低估值的分支限界搜索過程與動態規劃搜索過程的結合。
A*演算法的核心是一個估價函數:f(x)=g(x)+h(x)，它是對從初始狀態So經過當前狀態x到達目標狀態S的整個路徑的估計長度。其中 gx)是對已走距離的估計函數，h(x)是對當前狀態到目標狀態距離的估計。在A*搜索過程中，用整個路徑的估計長度對部分路徑進行排序，每次選擇具有最短估計長度的部分路徑進行擴展。

『柒』 廣度優先搜索怎麼保證最優解啊（新手不懂，求指導）

盡可能廣的遍歷圖的結點，類似於樹的層序遍歷。遍歷順序不唯一，但確定的遍歷順序，對應確定的生成樹。

『捌』 搜索演算法的運算原理

搜索演算法實際上是根據初始條件和擴展規則構造一棵「解答樹」並尋找符合目標狀態的節點的過程。所有的搜索演算法從最終的演算法實現上來看，都可以劃分成兩個部分——控制結構（擴展節點的方式）和產生系統（擴展節點），而所有的演算法優化和改進主要都是通過修改其控制結構來完成的。其實，在這樣的思考過程中，我們已經不知不覺地將一個具體的問題抽象成了一個圖論的模型——樹，即搜索演算法的使用第一步在於搜索樹的建立。
由圖一可以知道，這樣形成的一棵樹叫搜索樹。初始狀態對應著根結點，目標狀態對應著目標結點。排在前的結點叫父結點，其後的結點叫子結點，同一層中的結點是兄弟結點，由父結點產生子結點叫擴展。完成搜索的過程就是找到一條從根結點到目標結點的路徑，找出一個最優的解。這種搜索演算法的實現類似於圖或樹的遍歷，通常可以有兩種不同的實現方法，即深度優先搜索（DFS——Depth First search）和廣度優先搜索（BFS——Breadth First Search）。

『玖』 常見演算法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