關(guān)鍵詞：尋路
** 1.深度優(yōu)先搜索（Depth-First-Search）：**
沿著樹的深度遍歷樹的節(jié)點(diǎn)，盡可能深的搜索樹的分支顽染。當(dāng)節(jié)點(diǎn)v的所有邊都己被探尋過睦刃，搜索將回溯到發(fā)現(xiàn)節(jié)點(diǎn)v的那條邊的起始節(jié)點(diǎn)辣卒。這一過程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止。如果還存在未被發(fā)現(xiàn)的節(jié)點(diǎn)隙姿，則選擇其中一個(gè)作為源節(jié)點(diǎn)并重復(fù)以上過程，整個(gè)進(jìn)程反復(fù)進(jìn)行直到所有節(jié)點(diǎn)都被訪問為止厂捞。DFS屬于盲目搜索输玷。
利用深度優(yōu)先搜索算法可以產(chǎn)生目標(biāo)圖的相應(yīng)拓?fù)渑判虮恚猛負(fù)渑判虮砜梢苑奖愕慕鉀Q很多相關(guān)的圖論問題靡馁，如最大路徑問題等等欲鹏。一般用堆數(shù)據(jù)結(jié)構(gòu)來輔助實(shí)現(xiàn)DFS算法。
步驟
- 訪問頂點(diǎn)v臭墨；
- 依次從v的未被訪問的鄰接點(diǎn)出發(fā)赔嚎，對(duì)圖進(jìn)行深度優(yōu)先遍歷；直至圖中和v有路徑相通的頂點(diǎn)都被訪問胧弛；
- 若此時(shí)圖中尚有頂點(diǎn)未被訪問尤误，則從一個(gè)未被訪問的頂點(diǎn)出發(fā)，重新進(jìn)行深度優(yōu)先遍歷叶圃，直到圖中所有頂點(diǎn)均被訪問過為止袄膏。
對(duì)上面的圖G1進(jìn)行深度優(yōu)先遍歷，從頂點(diǎn)A開始掺冠。
第1步：訪問A沉馆。
第2步：訪問(A的鄰接點(diǎn))C码党。
在第1步訪問A之后，接下來應(yīng)該訪問的是A的鄰接點(diǎn)斥黑，即"C,D,F"中的一個(gè)揖盘。但在本文的實(shí)現(xiàn)中，頂點(diǎn)ABCDEFG是按照順序存儲(chǔ)锌奴，C在"D和F"的前面兽狭，因此，先訪問C鹿蜀。
第3步：訪問(C的鄰接點(diǎn))B箕慧。
在第2步訪問C之后，接下來應(yīng)該訪問C的鄰接點(diǎn)茴恰，即"B和D"中一個(gè)(A已經(jīng)被訪問過颠焦，就不算在內(nèi))。而由于B在D之前往枣，先訪問B伐庭。
第4步：訪問(C的鄰接點(diǎn))D。
在第3步訪問了C的鄰接點(diǎn)B之后分冈，B沒有未被訪問的鄰接點(diǎn)圾另；因此，返回到訪問C的另一個(gè)鄰接點(diǎn)D雕沉。
第5步：訪問(A的鄰接點(diǎn))F集乔。
前面已經(jīng)訪問了A，并且訪問完了"A的鄰接點(diǎn)B的所有鄰接點(diǎn)(包括遞歸的鄰接點(diǎn)在內(nèi))"蘑秽；因此饺著，此時(shí)返回到訪問A的另一個(gè)鄰接點(diǎn)F。
第6步：訪問(F的鄰接點(diǎn))G肠牲。
第7步：訪問(G的鄰接點(diǎn))E幼衰。
因此訪問順序是：A -> C -> B -> D -> F -> G -> E
下面以"有向圖"為例，來對(duì)深度優(yōu)先搜索進(jìn)行演示缀雳。
對(duì)上面的圖G2進(jìn)行深度優(yōu)先遍歷渡嚣，從頂點(diǎn)A開始。
第2步：訪問B肥印。
在訪問了A之后识椰，接下來應(yīng)該訪問的是A的出邊的另一個(gè)頂點(diǎn)，即頂點(diǎn)B深碱。
第3步：訪問C腹鹉。
在訪問了B之后，接下來應(yīng)該訪問的是B的出邊的另一個(gè)頂點(diǎn)敷硅，即頂點(diǎn)C,E,F功咒。在本文實(shí)現(xiàn)的圖中愉阎，頂點(diǎn)ABCDEFG按照順序存儲(chǔ)，因此先訪問C力奋。
第4步：訪問E榜旦。
接下來訪問C的出邊的另一個(gè)頂點(diǎn)，即頂點(diǎn)E景殷。
第5步：訪問D溅呢。
接下來訪問E的出邊的另一個(gè)頂點(diǎn)，即頂點(diǎn)B,D猿挚。頂點(diǎn)B已經(jīng)被訪問過咐旧，因此訪問頂點(diǎn)D。
第6步：訪問F绩蜻。
接下應(yīng)該回溯"訪問A的出邊的另一個(gè)頂點(diǎn)F"休偶。
第7步：訪問G。
因此訪問順序是：A -> B -> C -> E -> D -> F -> G
廣度優(yōu)先搜索（Breadth-First-Search）：
一種圖形搜索算法辜羊。簡(jiǎn)單的說，BFS是從根節(jié)點(diǎn)開始词顾，沿著樹(圖)的寬度遍歷樹(圖)的節(jié)點(diǎn)八秃。如果所有節(jié)點(diǎn)均被訪問，則算法中止肉盹。BFS同樣屬于盲目搜索昔驱。一般用隊(duì)列數(shù)據(jù)結(jié)構(gòu)來輔助實(shí)現(xiàn)BFS算法。
步驟：
- 首先將根節(jié)點(diǎn)放入隊(duì)列中上忍。
- 從隊(duì)列中取出第一個(gè)節(jié)點(diǎn)骤肛，并檢驗(yàn)它是否為目標(biāo)。
如果找到目標(biāo)窍蓝，則結(jié)束搜尋并回傳結(jié)果腋颠。
否則將它所有尚未檢驗(yàn)過的直接子節(jié)點(diǎn)加入隊(duì)列中。 - 若隊(duì)列為空吓笙，表示整張圖都檢查過了——亦即圖中沒有欲搜尋的目標(biāo)淑玫。結(jié)束搜尋并回傳“找不到目標(biāo)”。
- 重復(fù)步驟2面睛。
下面以"無向圖"為例絮蒿，來對(duì)廣度優(yōu)先搜索進(jìn)行演示。還是以上面的圖G1為例進(jìn)行說明叁鉴。
第1步：訪問A土涝。
第2步：依次訪問C,D,F。
在訪問了A之后幌墓，接下來訪問A的鄰接點(diǎn)但壮。前面已經(jīng)說過冀泻，在本文實(shí)現(xiàn)中，頂點(diǎn)ABCDEFG按照順序存儲(chǔ)的茵肃，C在"D和F"的前面腔长，因此，先訪問C验残。再訪問完C之后捞附，再依次訪問D,F。
第3步：依次訪問B,G您没。
在第2步訪問完C,D,F之后鸟召，再依次訪問它們的鄰接點(diǎn)。首先訪問C的鄰接點(diǎn)B氨鹏，再訪問F的鄰接點(diǎn)G欧募。
第4步：訪問E。
在第3步訪問完B,G之后仆抵，再依次訪問它們的鄰接點(diǎn)跟继。只有G有鄰接點(diǎn)E，因此訪問G的鄰接點(diǎn)E镣丑。
因此訪問順序是：A -> C -> D -> F -> B -> G -> E
下面以"有向圖"為例舔糖，來對(duì)廣度優(yōu)先搜索進(jìn)行演示。還是以上面的圖G2為例進(jìn)行說明莺匠。
第1步：訪問A金吗。
第2步：訪問B。
第3步：依次訪問C,E,F趣竣。
在訪問了B之后摇庙，接下來訪問B的出邊的另一個(gè)頂點(diǎn)，即C,E,F遥缕。前面已經(jīng)說過卫袒，在本文實(shí)現(xiàn)中，頂點(diǎn)ABCDEFG按照順序存儲(chǔ)的单匣，因此會(huì)先訪問C玛臂，再依次訪問E,F。
第4步：依次訪問D,G封孙。
在訪問完C,E,F之后迹冤，再依次訪問它們的出邊的另一個(gè)頂點(diǎn)。還是按照C,E,F的順序訪問虎忌，C的已經(jīng)全部訪問過了泡徙，那么就只剩下E,F；先訪問E的鄰接點(diǎn)D膜蠢，再訪問F的鄰接點(diǎn)G堪藐。
因此訪問順序是：A -> B -> C -> E -> F -> D -> G
啟發(fā)式搜索(Heuristically Search)：
又稱為有信息搜索(Informed Search)莉兰，它是利用問題擁有的啟發(fā)信息來引導(dǎo)搜索，達(dá)到減少搜索范圍礁竞、降低問題復(fù)雜度的目的糖荒，這種利用啟發(fā)信息的搜索過程稱為啟發(fā)式搜索。
就是在狀態(tài)空間中的搜索對(duì)每一個(gè)搜索的位置進(jìn)行評(píng)估模捂，得到最好的位置捶朵，再從這個(gè)位置進(jìn)行搜索直到目標(biāo)。
這樣可以省略大量無謂的搜索路徑狂男，提高了效率综看。在啟發(fā)式搜索中，對(duì)位置的估價(jià)（估價(jià)函數(shù)）是十分重要的
利用啟發(fā)式搜索自動(dòng)尋路實(shí)例
<style type="text/css">
*{ margin:0; padding:0;}
li{ list-style:none;}
#map{
height:auto;
overflow:hidden;
margin:20px auto;
border:1px #ccc solid;
border-bottom:none;
border-right:none;
}
#map li{
box-sizing: border-box;
border:1px #ccc solid;
border-top:none;
border-left:none;
float:left;
}
#map li.sty1{ background:#e22841;}
#map li.sty2{ background:orange;}
#map li.sty3{ background:#00bcda;}
#btn{
width:160px;
height: 40px;
color: #fff;
text-align: center;
line-height: 40px;
font-size: 16px;
background-color: #00bcda;
border: none;
border-radius: 5px;
position:absolute;
left:0;
right: 0;
margin: auto;
cursor: pointer;
}
</style>
<body>
<ul id="map"></ul>
<span id="btn">快去解救公主!</span>
</body>
<script type="text/javascript">
var map = [
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,3,3,3,3,3,3,3,3,3,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
0,0,0,0,1,0,0,0,0,0,3,0,0,0,0,2,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,3,3,3,0,3,3,3,0,3,0,
0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,3,3,0,3,3,3,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
];
var sizeGird = 24; // 設(shè)定網(wǎng)格尺寸
var speed = 100; // 設(shè)定移動(dòng)速度
(function road(){
var oUl = document.getElementById('map');
var aLi = oUl.getElementsByTagName('li');
var oBtn = document.getElementById('btn');
var beginLi = oUl.getElementsByClassName('sty1');
var endLi = oUl.getElementsByClassName('sty2');
var cols = Math.sqrt(map.length);
var openArr = []; // 存放可能要走的路線
var closeArr = []; // 存放不允許走的路線
// 點(diǎn)擊按鈕初始化
init();
function init(){
createMap();
oBtn.onclick = function(){
openFn();
};
}
// 創(chuàng)建網(wǎng)格
function createMap(){
oUl.style.width = cols * (sizeGird) + 'px';
for(var i=0;i<map.length;i++){
var oLi = document.createElement('li');
oLi.style.width = sizeGird + 'px';
oLi.style.height = sizeGird + 'px';
oUl.appendChild(oLi);
if( map[i] == 1 ){
oLi.className = 'sty1';
openArr.push(oLi);
}
else if(map[i] == 2){
oLi.className = 'sty2';
}
else if(map[i] == 3){
oLi.className = 'sty3';
closeArr.push(oLi);
}
}
}
function openFn(){
var nowLi = openArr.shift();
if( nowLi == endLi[0] ){
showLine();
return;
}
closeFn(nowLi);
findLi(nowLi);
//console.log( openArr );
openArr.sort(function(li1,li2){
return li1.num - li2.num;
});
//console.log( openArr );
openFn(); // 遞歸操作岖食，重復(fù)執(zhí)行函數(shù)
}
// 過濾走過的路線
function closeFn(nowLi){
closeArr.push( nowLi );
}
// 找尋所有可能走的網(wǎng)格
function findLi(nowLi){
var result = [];
for(var i=0;i<aLi.length;i++){
if( filter(aLi[i]) ){
result.push( aLi[i] );
}
}
function filter(li){
for(var i=0;i<closeArr.length;i++){
if( closeArr[i] == li ){
return false;
}
}
for(var i=0;i<openArr.length;i++){
if( openArr[i] == li ){
return false;
}
}
return true;
}
// 找到當(dāng)前網(wǎng)格周圍的八個(gè)網(wǎng)格
for(var i=0;i<result.length;i++){
if( (Math.abs(nowLi.offsetLeft - result[i].offsetLeft)<= sizeGird) && (Math. abs(nowLi.offsetTop - result[i].offsetTop)<= sizeGird) ){
result[i].num = f(result[i]);
result[i].parent = nowLi;
openArr.push( result[i] );
}
}
}
// 顯示路線
function showLine(){
var result = [];
var lastLi = closeArr.pop();
var iNow = 0;
findParent(lastLi);
function findParent(li){
result.unshift(li);
if( li.parent == beginLi[0] ){
return;
}
findParent(li.parent);
}
var timer = setInterval(function(){
result[iNow].style.background = '#e22841';
iNow++;
if(iNow == result.length){
clearInterval(timer);
}
},speed);
}
// 估價(jià)函數(shù)
function f(nodeLi){
return g(nodeLi) + h(nodeLi);
}
function g(nodeLi){
var a = beginLi[0].offsetLeft - nodeLi.offsetLeft;
var b = beginLi[0].offsetTop - nodeLi.offsetTop;
return Math.sqrt(a*a + b*b); // 利用了勾股定理
}
function h(nodeLi){
var a = endLi[0].offsetLeft - nodeLi.offsetLeft;
var b = endLi[0].offsetTop - nodeLi.offsetTop;
return Math.sqrt(a*a + b*b);
}
})(map,sizeGird,speed)
在線預(yù)覽實(shí)例 ?[請(qǐng)點(diǎn)這里!!!][]
[請(qǐng)點(diǎn)這里!!!]:http://htmlpreview.github.io/?https://github.com/ferrinte/algorithm/blob/master/road.html
