一、深度優(yōu)先搜索
深度優(yōu)先搜索就是在搜索樹的每一層始終先只擴展一個子節(jié)點，不斷地向縱深前進直到不能再前進（到達葉子節(jié)點或受到深度限制）時，才從當前節(jié)點返回到上一級節(jié)點，沿另一方向又繼續(xù)前進。這種方法的搜索樹是從樹根開始一枝一枝逐漸形成的。
深度優(yōu)先搜索亦稱為縱向搜索。由于一個有解的問題樹可能含有無窮分枝，深度優(yōu)先搜索如果誤入無窮分枝（即深度無限），則不可能找到目標節(jié)點。所以，深度優(yōu)先搜索策略是不完備的。另外，應用此策略得到的解不一定是最佳解（最短路徑）。
二、 重排九宮問題游戲
在一個3乘3的九宮中有1-8的8個數(shù)及一個空格隨機擺放在其中的格子里。如下面左圖所示。現(xiàn)在要求實現(xiàn)這樣的問題：將該九宮調(diào)整為如下圖右圖所示的形式。調(diào)整規(guī)則是：每次只能將與空格（上，下或左，右）相臨的一個數(shù)字平移到空格中。試編程實現(xiàn)。
| 2 | 8 | 3 | | 1 | 2 | 3 |
-
| 1 | | 4 | | 8 | | 4 |
| 7 |6 | 5 | | 7 | 6 | 5 |
深度優(yōu)先搜索的路徑示意圖：
三、廣度優(yōu)先搜索
在深度優(yōu)先搜索算法中，是深度越大的結(jié)點越先得到擴展。如果在搜索中把算法改為按結(jié)點的層次進行搜索， 本層的結(jié)點沒有搜索處理完時，不能對下層結(jié)點進行處理，即深度越小的結(jié)點越先得到擴展，也就是說先產(chǎn)生 的結(jié)點先得以擴展處理，這種搜索算法稱為廣度優(yōu)先搜索法。
廣度優(yōu)先搜索路徑示意圖：
四、航班問題（來自《The Art of Java》)
一位顧客要預定一張從New York到Los Angeles的航班機票，下面是航班線路，請你為顧客找一種購票方案。
|
航班
|
距離
|
| New York到Chicago |
900英里
|
| Chicago到Denver |
1000英里
|
| New York到Toronto |
500英里
|
| New York到Denver |
1800英里
|
| Toronto到Calgary |
1700英里
|
| Toronto到Los Angeles |
2500英里
|
| Toronto到Chicago |
500英里
|
| Denver到Urbana |
1000英里
|
| Denver到Houston |
1000英里
|
| Houston到Los Angeles |
1500英里
|
| Denver到Los Angeles |
1000英里
|
下面是用深度優(yōu)先搜索求解的程序:
import java.util. * ;
import java.io. * ;
// Flightinformation.
class FlightInfo{
Stringfrom;
Stringto;
int distance;
boolean skip; // usedinbacktracking
FlightInfo(Stringf,Stringt, int d){
from = f;
to = t;
distance = d;
skip = false ;
}
}
class Depth{
final int MAX = 100 ;
// Thisarrayholdstheflightinformation.
FlightInfoflights[] = new FlightInfo[MAX];
int numFlights = 0 ; // numberofentriesinflightarray
StackbtStack = new Stack(); // backtrackstack
public static void main(Stringargs[])
{
Stringto,from;
Depthob = new Depth();
BufferedReaderbr = new
BufferedReader( new InputStreamReader(System.in));
ob.setup();
try {
System.out.print( " From? " );
from = br.readLine();
System.out.print( " To? " );
to = br.readLine();
ob.isflight(from,to);
if (ob.btStack.size() != 0 )
ob.route(to);
} catch (IOExceptionexc){
System.out.println( " Erroroninput. " );
}
}
// Initializetheflightdatabase.
void setup()
{
addFlight( " NewYork " , " Chicago " , 900 );
addFlight( " Chicago " , " Denver " , 1000 );
addFlight( " NewYork " , " Toronto " , 500 );
addFlight( " NewYork " , " Denver " , 1800 );
addFlight( " Toronto " , " Calgary " , 1700 );
addFlight( " Toronto " , " LosAngeles " , 2500 );
addFlight( " Toronto " , " Chicago " , 500 );
addFlight( " Denver " , " Urbana " , 1000 );
addFlight( " Denver " , " Houston " , 1000 );
addFlight( " Houston " , " LosAngeles " , 1500 );
addFlight( " Denver " , " LosAngeles " , 1000 );
}
// Putflightsintothedatabase.
void addFlight(Stringfrom,Stringto, int dist)
{
if (numFlights < MAX){
flights[numFlights] =
new FlightInfo(from,to,dist);
numFlights ++ ;
}
else System.out.println( " Flightdatabasefull. " );
}
// Showtherouteandtotaldistance.
void route(Stringto)
{
Stackrev = new Stack();
int dist = 0 ;
FlightInfof;
int num = btStack.size();
// Reversethestacktodisplayroute.
for ( int i = 0 ;i < num;i ++ )
rev.push(btStack.pop());
for ( int i = 0 ;i < num;i ++ ){
f = (FlightInfo)rev.pop();
System.out.print(f.from + " to " );
dist += f.distance;
}
System.out.println(to);
System.out.println( " Distanceis " + dist);
}
/* Ifthereisaflightbetweenfromandto,
returnthedistanceofflight;
otherwise,return0. */
int match(Stringfrom,Stringto)
{
for ( int i = numFlights - 1 ;i > - 1 ;i -- ){
if (flights[i].from.equals(from) &&
flights[i].to.equals(to) &&
! flights[i].skip)
{
flights[i].skip = true ; // preventreuse
return flights[i].distance;
}
}
return 0 ; // notfound
}
// Givenfrom,findanyconnection.
FlightInfofind(Stringfrom)
{
for ( int i = 0 ;i < numFlights;i ++ ){
if (flights[i].from.equals(from) &&
! flights[i].skip)
{
FlightInfof = new FlightInfo(flights[i].from,
flights[i].to,
flights[i].distance);
flights[i].skip = true ; // preventreuse
return f;
}
}
return null ;
}
// Determineifthereisaroutebetweenfromandto.
void isflight(Stringfrom,Stringto)
{
int dist;
FlightInfof;
// Seeifatdestination.
dist = match(from,to);
if (dist != 0 ){
btStack.push( new FlightInfo(from,to,dist));
return ;
}
// Tryanotherconnection.
f = find(from);
if (f != null ){
btStack.push( new FlightInfo(from,to,f.distance));
isflight(f.to,to);
}
else if (btStack.size() > 0 ){
// Backtrackandtryanotherconnection.
f = (FlightInfo)btStack.pop();
isflight(f.from,f.to);
}
}
}
解釋：isflight()方法用遞歸方法進行深度優(yōu)先搜索，它先調(diào)用match()方法檢查航班的數(shù)據(jù)庫，判斷在from和to之間有沒有航班可達。如果有，則獲取目標信息，并將該線路壓入棧中，然后返回（找到一個方案）。否則，就調(diào)用find()方法查找from與任意其它城市之間的線路，如果找到一條就返回描述該線路的FlightInfo對象，否則返回null。如果存在這樣的一條線路，那么就把該線路保存在f中，并將當前航班信息壓到棧的頂部，然后遞歸調(diào)用isflight()方法 ,此時保存在f.to中的城市成為新的出發(fā)城市.否則就進行回退,彈出棧頂?shù)牡谝粋€節(jié)點,然后遞歸調(diào)用isflight()方法。該過程將一直持續(xù)到找到目標為止。
程序運行結(jié)果：
C:\java>java Depth
From? New York
To? Los Angeles
New York to Chicago to Denver to Los Angeles
Distance is 2900
C:\java>
深度優(yōu)先搜索能夠找到一個解，同時，對于上面這個特定問題，深度優(yōu)先搜索沒有經(jīng)過回退，一次就找到了一個解；但如果數(shù)據(jù)的組織方式不同，尋找解時就有可能進行多次回退。因此這個例子的輸出并不具有普遍性。而且，在搜索一個很長，但是其中并沒有解的分支的時候，深度優(yōu)先搜索的性能將會很差，在這種情況下，深度優(yōu)先搜索不僅在搜索這條路徑時浪費時間，而且還在向目標的回退中浪費時間。
再看對這個例子使用廣度優(yōu)先搜索的程序：
程序運行結(jié)果：
C:\java>java Breadth
From? New York
To? Los Angeles
New York to Toronto to Los Angeles
Distance is 3000
import java.util. * ;
import java.io. * ;
// Flightinformation.
class FlightInfo{
Stringfrom;
Stringto;
int distance;
boolean skip; // usedinbacktracking
FlightInfo(Stringf,Stringt, int d){
from = f;
to = t;
distance = d;
skip = false ;
}
}
class Breadth{
final int MAX = 100 ;
// Thisarrayholdstheflightinformation.
FlightInfoflights[] = new FlightInfo[MAX];
int numFlights = 0 ; // numberofentriesinflightarray
StackbtStack = new Stack(); // backtrackstack
public static void main(Stringargs[])
{
Stringto,from;
Breadthob = new Breadth();
BufferedReaderbr = new
BufferedReader( new InputStreamReader(System.in));
ob.setup();
try {
System.out.print( " From? " );
from = br.readLine();
System.out.print( " To? " );
to = br.readLine();
ob.isflight(from,to);
if (ob.btStack.size() != 0 )
ob.route(to);
} catch (IOExceptionexc){
System.out.println( " Erroroninput. " );
}
}
// Initializetheflightdatabase.
void setup()
{
addFlight( " NewYork " , " Chicago " , 900 );
addFlight( " Chicago " , " Denver " , 1000 );
addFlight( " NewYork " , " Toronto " , 500 );
addFlight( " NewYork " , " Denver " , 1800 );
addFlight( " Toronto " , " Calgary " , 1700 );
addFlight( " Toronto " , " LosAngeles " , 2500 );
addFlight( " Toronto " , " Chicago " , 500 );
addFlight( " Denver " , " Urbana " , 1000 );
addFlight( " Denver " , " Houston " , 1000 );
addFlight( " Houston " , " LosAngeles " , 1500 );
addFlight( " Denver " , " LosAngeles " , 1000 );
}
// Putflightsintothedatabase.
void addFlight(Stringfrom,Stringto, int dist)
{
if (numFlights < MAX){
flights[numFlights] =
new FlightInfo(from,to,dist);
numFlights ++ ;
}
else System.out.println( " Flightdatabasefull. " );
}
// Showtherouteandtotaldistance.
void route(Stringto)
{
Stackrev = new Stack();
int dist = 0 ;
FlightInfof;
int num = btStack.size();
// Reversethestacktodisplayroute.
for ( int i = 0 ;i < num;i ++ )
rev.push(btStack.pop());
for ( int i = 0 ;i < num;i ++ ){
f = (FlightInfo)rev.pop();
System.out.print(f.from + " to " );
dist += f.distance;
}
System.out.println(to);
System.out.println( " Distanceis " + dist);
}
/* Ifthereisaflightbetweenfromandto,
returnthedistanceofflight;
otherwise,return0. */
int match(Stringfrom,Stringto)
{
for ( int i = numFlights - 1 ;i > - 1 ;i -- ){
if (flights[i].from.equals(from) &&
flights[i].to.equals(to) &&
! flights[i].skip)
{
flights[i].skip = true ; // preventreuse
return flights[i].distance;
}
}
return 0 ; // notfound
}
// Givenfrom,findanyconnection.
FlightInfofind(Stringfrom)
{
for ( int i = 0 ;i < numFlights;i ++ ){
if (flights[i].from.equals(from) &&
! flights[i].skip)
{
FlightInfof = new FlightInfo(flights[i].from,
flights[i].to,
flights[i].distance);
flights[i].skip = true ; // preventreuse
return f;
}
}
return null ;
}
/* Determineifthereisaroutebetweenfromandto
usingbreadth-firstsearch. */
void isflight(Stringfrom,Stringto)
{
int dist,dist2;
FlightInfof;
// Thisstackisneededbythebreadth-firstsearch.
StackresetStck = new Stack();
// Seeifatdestination.
dist = match(from,to);
if (dist != 0 ){
btStack.push( new FlightInfo(from,to,dist));
return ;
}
/* Followingisthefirstpartofthebreadth-first
modification.Itchecksallconnectingflights
fromaspecifiednode. */
while ((f = find(from)) != null ){
resetStck.push(f);
if ((dist = match(f.to,to)) != 0 ){
resetStck.push(f.to);
btStack.push( new FlightInfo(from,f.to,f.distance));
btStack.push( new FlightInfo(f.to,to,dist));
return ;
}
}
/* Thefollowingcoderesetstheskipfieldssetby
precedingwhileloop.Thisisalsopartofthe
breadth-firstmodifiction. */
int i = resetStck.size();
for (;i != 0 ;i -- )
resetSkip((FlightInfo)resetStck.pop());
// Tryanotherconnection.
f = find(from);
if (f != null ){
btStack.push( new FlightInfo(from,to,f.distance));
isflight(f.to,to);
}
else if (btStack.size() > 0 ){
// Backtrackandtryanotherconnection.
f = (FlightInfo)btStack.pop();
isflight(f.from,f.to);
}
}
// Resetskipfieldofspecifiedflight.
void resetSkip(FlightInfof){
for ( int i = 0 ;i < numFlights;i ++ )
if (flights[i].from.equals(f.from) &&
flights[i].to.equals(f.to))
flights[i].skip = false ;
}
}
C:\java>
它找到了一個合理的解，但這不具有一般性。因為找到的第一條路徑取決于信息的物理組織形式。
如果目標在搜索空間中隱藏得不是太深，那么廣度優(yōu)先搜索的性能會很好。
更多文章、技術(shù)交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
