Ⅰ 搜索技術
問題求解過程是 搜索答案（目標） 的過程，所以問題求解技術也叫做搜索技術——通過對 狀態空間 的搜索而求解問題的技術。
問題可形式化地定義成四個組成部分
在解題過程中 達到過的所有狀態 的集合。不同於狀態空間，搜索空間是其中一部分。狀態空間和搜索空間都屬於 過程性知識表示 。
八數碼問題詳解
兩種搜索技術
無信息搜索策略也稱 盲目搜索 ：沒有任何附加信息，只有生成後繼和區分目標和非目標狀態。
五種盲目搜索策略有：廣度優先搜索，代價一直搜索，深度優先搜索，深度有限搜索，迭代深入深度優先搜索。
從四種度量來評價廣度優先搜索
性能：通常使用遞歸函數實現，一次對當前節點的子節點調用該函數。相比廣度優先，內存需求少(分支因子 * 最大深度+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集合賦值 ）
Ⅱ 什麼是寬度優先搜索
是數據結構中的問題，涉及到圖的遍歷，應該是深度優先搜索，和廣度優先搜索吧？
追問，在線。。。
你說的寬度優先，應該就是廣度優先，不一樣的叫法而已。
【廣度（寬度）優先搜索】
類似於樹的層次遍歷，先從一個頂點出發，依次遍歷與之相鄰的未訪問過的，也就是先搜索與頂點路徑為1的，全部寫出；在搜索與頂點路徑為2的，全部寫出……以此類推，通俗地講，是採用了一種擴散的方法來搜索整張圖
【深度優先搜索】這是與廣度優先相對立的一種搜索方式
從一個頂點出發，找一條路徑（注意，只是一條），依次寫出一直相鄰的的未被訪問過的結點，直到這條路都被訪問過，通俗地講，就是一條路徑走到頭，之後在返回上一個結點看有沒有未訪問的，再返回上一個，再返回上一個……以此類推
都是自己的話說的，更容易理解些，希望對你有幫助o(∩_∩)o
Ⅲ 圖的矩陣深度和廣度遍歷演算法
圖的遍歷是指從圖中任一給定頂點出發，依次訪問圖中的其餘頂點。如果給定的圖是連通圖，則從圖中的任意一點出發，按照一個指定的順序就可以訪問到圖中的所有頂點，且每個頂點只訪問一次。這個過程稱為圖的遍歷。
圖的遍歷比樹的遍歷復雜的多。樹是一種特殊類型的圖，即無圈（無迴路）連通圖。樹中的任意兩個頂點間都有唯一的路徑相通。在一個頂點被訪問過之後，不可能又沿著另外一條路徑訪問到已被訪問過的結點。而圖中的頂點可能有邊與其他任意頂點相連
。因此在訪問了某個頂點之後，可能沿著另一條邊訪問已被訪問過的頂點。例如圖（a）中的G1，在訪問了V1，V2和V3之後，有可能沿著邊（V3，V1）訪問到V1。為了避免一頂點被多次訪問，可以設立一個集合Visited，用來記錄已被訪問過的頂點。它的初值為空
集。一旦V1被訪問過，即把V1加到集合Visited中。圖的遍厲通常有兩種:圖的深度優先
搜索和圖的廣度優先搜索。
1）圖的深度優先搜索
從圖G=（V，E）的一個頂點V0出發，在訪問了任意一個與V0相鄰且未被訪問過的頂點W1之後，再從W1出發，訪問和W1相鄰且未被訪問過的頂點W2，然後再從W2出發進行如上所述訪問，直到找到一個它相鄰的結點，都被訪問過的結點為止。然後退回到尚有相
鄰結點未被訪問過的頂點，再從該頂點出發，重復上述搜索過程，直到所有被訪問過的頂點的鄰接點都被訪問過為止。圖的這種遍歷過程就稱為圖的深度優先搜索。例如從頂點V1出發對圖3.3.5進行深度優先搜索，遍歷的順序為 V1,V2,V5,V10,V6,V7,V3,V12,V1
1,V8,V4,V9。（與鄰接表中的鄰接點排列順序有關，即p->next.vertex=v2 or v3對遍歷
順序有影響 ）
例25.(p194.c)圖的深度優先搜索。從圖G的頂點V0
發進行深度優先搜索，列印出各個頂點的遍歷順序。
解：圖的深度優先搜索法為：
（1）首先訪問V0並把V0加到集合visited中；
（2）找到與V0相鄰的頂點W，若W未進入
visited中，則以深度優先方法從W開始搜索。
（3）重復過程（2）直到所有於V0相鄰的頂點
都被訪問過為止。
下面是對用鄰接表表示的圖G進行深度優先搜索的程序
int rear=0; /*Visit和rear都為全局變數*/
int visit[500];
depth_first_search(g,v0) /*從V0開始對圖G進行深度
優先搜索*/
graphptr g[ ]; /*指針數組,為鄰接表表頭頂點指針
g[vi]...g[vn]*/
int v0; /*這里V0和W都是頂點標號,如V0=0或1*/
{ /*g[v0]是頂點V0的表頭指針*/
int w;
graphptr p; /*鏈表的結點指針*/
visit [++rear]=v0;
printf("%d\n",v0);
p=g[v0];/*指定一個頂點，通過鄰接表表頭指針
，訪問v0的鄰接頂點*/
while (p!=NULL)
{
w=p->vertex ;/*這里W是與V0相鄰的一個頂點*/
if (!visited(w))/*當V0的相鄰結點，W未被訪問時，從W開始遍厲*/
depth_first_search(g,w);
p=p->next;/*接著訪問另一個相鄰頂點*/
}
}
int visited(w) /*檢查頂點w是否進入visited(w)*/
int w ;
{
int i;
for (i=1;i<=rear;i++)
if (visit [ i ] == w) return(1);/*W在visit[]中，說明被訪問過*/
return(0); /*W不在visit[]中，說明未被訪問過，返回0*/
}
2）圖的廣度優先搜索
從圖G的一個頂點V0出發，依次訪問V0的鄰接點K1,K2...Kn。然後再順序訪問K1,K2...Kn的所有尚未被訪問過的鄰接點。如此重復，直到圖中的頂點都被訪問過為止。圖的這種搜索稱為圖的廣度優先搜索。例如：從V1出發按廣度優先搜索方法遍歷圖3.3.5,頂
點的訪問順序為V1,V2,V3,V4,V5,V6,V7,V8,V9,V10,V11,V12。
圖的廣度優先搜索類似樹的按層次遍歷，需要有一個隊列來存放還沒
有來得及處理的頂點。圖的廣度優先搜索演算法為：
（1）首先把V0放入隊列；
（2）若隊列為空則結束，否則取出隊列的頭V；
（3）訪問V並把所有與V相鄰且未被訪問的頂點插入隊列；
（4）重復（2）-（3）直到隊列為空。
上述演算法中所有已被訪問過的頂點都放在隊列中，因此只要檢查某個頂點是否在隊列中就可以判斷出該頂點是否已被訪問過。
廣度搜索法的程序如下：
broad_first_search(g,v0) /*從V0開始對圖g進行廣度優先搜索*/
graphptr g[ ]; /*為鄰接表，表頭頂點指針*/
int v0;
{
int queue[500],front =1, tail=1,v;
graphptr p;
queue [tail]=v0; /*把V0插入隊列queue*/
while (front <=tail)/*當隊列不為空*/
{
v=queue[front++]; /*取出隊列中的頂點*/
printf("%d\n",v); /*訪問該頂點*/
p=g[v]; /*從頂點V的鏈表來考慮與V相鄰的頂點*/
while (p!=NULL)
{
v=p->vertex; /*從第一個結點（即邊）中找出相鄰的頂點*/
if (!visited(queue,tail,v))/*判斷頂點是否進入隊列，如進入隊列
說明已被訪問或將要訪問*/
queue[++tail]=v;/*如果該頂點未被訪問過，將此相鄰頂點插入隊列*/
p=p-->next;/*再考慮該結點的下一個相鄰頂點*/
}
}
}
visited (q,tail,v)/*判斷頂點是否被訪問過，訪問過時，返回1，否則返回0*/
int q[ ],tail,v;/*進入隊列的頂點，在front之前的頂點已被訪問過列印輸出，
在front和tail之間的頂點是即將要訪問頂點*/
{
int i;
for(i=1;i<=tail;i++)/*掃描隊列，確定v是否在隊列中，在隊列中返回1，否則返回0*
/
if (q[i]==v)return(1);/*隊列中的頂點都認為已被訪問過*/
return(0);
}
深度優先的非遞歸演算法
/*設當前圖(或圖的某個連通分枝)的起始訪問點為p*/
NodeType stackMain,stackSec
visit(p)
p->mark=true;
do
{
for(all v isTheConnectNode of (G,p))//將當前點的鄰接點中的所有結點壓入副棧中
if(v.marked==false)
statckSec.push(v)
//將副棧中的點依次彈出，壓入主棧中，這與非遞歸演算法中使用隊列的意圖類似
while(!stackSec.isEmpty())
stackMain.push(statckSec.pop());
do//找出下一個未訪問的結點或者沒找到，直到棧為空
{
if(!stackMain.isEmpty())
{
p=stackMain.pop();
}
}while(p.marked==true&&!stackMain.isEmpty())
if(p.marked==false)//訪問未訪問結點.
{
visit(p);
p.marked=true;
}
}while(!stackMain.isEmpty())
Ⅳ 廣度優先搜索是什麼
寬度優先搜索演算法（又稱廣度優先搜索）是最簡便的圖的搜索演算法之一，這一演算法也是很多重要的圖的
演算法的原型。Dijkstra單源最短路徑演算法和Prim最小生成樹演算法都採用了和寬度優先搜索類似的思想。其別名又叫BFS，屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位址，徹底地搜索整張圖，直到找到結果為止。BFS並不使用經驗法則演算法。從演算法的觀點，所有因為展開節點而得到的子節點都會被加進一個先進先出的佇列中。一般的實作里，其鄰居節點尚未被檢驗過的節點會被放置在一個被稱為 open 的容器中（例如佇列或是鏈表），而被檢驗過的節點則被放置在被稱為 closed 的容器中。（open-closed表）
Ⅳ 深度優先搜索和廣度優先搜索的區別。 請講的詳細點，最好能用例子，謝謝啦
深度優先搜索所遵循的搜索策略是盡可能「深」地搜索圖。在深度優先搜索中，對於最新發現的結點，如果它還有以此為起點而未搜過的邊，就沿著邊繼續搜索下去。當結點v的所有邊都已被探尋過，搜索將回溯到發現結點v有那條邊的始結點。這一過程一直進行到已發現從源結點可達的所有結點為止。如果還存在未被發現的結點，則選擇其中一個作為源結點並重復以上過程，整個過程反復進行直到所有結點都被發現為止。
深度優先搜索基本演算法如下{遞歸演算法}：
PROCEDURE dfs_try(i);
FOR i:=1 to maxr DO
BEGIN
IF 子結點 mr 符合條件 THEN
BEGIN
產生的子結點mr入棧；
IF 子結點mr是目標結點
THEN 輸出
ELSE dfs_try(i+1);
棧頂元素出棧;
END;
END; 寬度優先搜索演算法（又稱廣度優先搜索演算法）是最簡單的圖的搜索演算法之一，這一演算法也是很多重要的圖的演算法的原型。Dijksta單源最短路徑演算法和Prim最小生成樹演算法都採用了與寬度優先搜索類似的思想。
寬度優先搜索的核心思想是：從初始結點開始，應用算符生成第一層結點，檢查目標結點是否在這些後繼結點中，若沒有，再用產生式規則將所有第一層的結點逐一擴展，得到第二層結點，並逐一檢查第二層結點中是否包含目標結點。若沒有，再用算符逐一擴展第二層所有結點……，如此依次擴展，直到發現目標結點為止。
寬度優先搜索基本演算法如下：
list[1]:=source; {加入初始結點，list為待擴展結點的表}
head:=0; {隊首指針}
foot:=1; {隊尾指針}
REPEAT
head:=head+1;
FOR x:=1 to 規則數 DO
BEGIN
根據規則產生新結點nw;
IF not_appear(nw,list) THEN {若新結點隊列中不存在，則加到隊尾}
BEGIN
foot:=foot+1;
list[foot]:=nw;
list[foot].father:=head;
IF list[foot]=目標結點 THEN 輸出；
END；
END；
UNTIL head>foot; {隊列為空表明再無結點可擴展}
望採納
Ⅵ 廣度優先搜索有什麼難點
廣度優先搜索難點在於每一種演算法的不同，樹的遍歷。
擴展知識：
廣度優先搜索演算法又譯作寬度優先搜索，或橫向優先搜索，是一種圖形搜索演算法。簡單的說，BFS是從根節點開始，沿著樹的寬度遍歷樹的節點。如果所有節點均被訪問，則演算法中止。廣度優先搜索的實現一般採用open-closed表。
廣度優先搜索演算法主要有四個特性：
空間復雜度：由於對空間的大量需求，因此BFS並不適合解非常大的問題，對於類似的問題，應用IDDFS已達節省空間的效果。
時間復雜度：最差情形下，BFS必須查找所有到可能節點的所有路徑。
完全性：廣度優先搜索演算法具有完全性。這意指無論圖形的種類如何，只要目標存在，則BFS一定會找到。然而，若目標不存在，且圖為無限大，則BFS將不收斂（不會結束）。
最佳解：若所有邊的長度相等，廣度優先搜索演算法是最佳解——亦即它找到的第一個解，距離根節點的邊數目一定最少；但對一般的圖來說，BFS並不一定回傳最佳解。