??A*算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法对粪,注意——是最有效的直接搜索算法,之后涌現(xiàn)了很多預(yù)處理算法(如ALT箱靴,CH腺逛,HL等等),在線查詢效率是A*算法的數(shù)千甚至上萬倍衡怀。
核心思想
??公式: f(n) = g(n) + h(n)
??其中棍矛, f(n) 是從初始狀態(tài)經(jīng)由狀態(tài)n到目標狀態(tài)的代價估計安疗,g(n) 是在狀態(tài)空間中從初始狀態(tài)到狀態(tài)n的實際代價,h(n) 是從狀態(tài)n到目標狀態(tài)的最佳路徑的估計代價够委,保證找到最短路徑(最優(yōu)解的)條件荐类,關(guān)鍵在于估價函數(shù)f(n)的選取(或者說h(n)的選茸旅薄)玉罐。
距離估計與實際值越接近,估價函數(shù)取得就越好
??例如對于幾何路網(wǎng)來說脐雪,可以取兩節(jié)點間曼哈頓距離做為距離估計厌小,即f=g(n) + (abs(dx - nx) + abs(dy - ny));這樣估價函數(shù)f(n)在g(n)一定的情況下战秋,會或多或少的受距離估計值h(n)的制約璧亚,節(jié)點距目標點近,h值小脂信,f值相對就小癣蟋,能保證最短路的搜索向終點的方向進行。
算法實現(xiàn)(路徑搜索)
??接下來狰闪,我們用上面的方法寫一個簡單的應(yīng)用例子疯搅,實現(xiàn)下圖的搜索功能。
??先建立網(wǎng)格的css
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Title</title>
</head>
<style>
* {
margin: 0;
padding: 0;
}
li {
list-style: none;
}
#ul {
height: auto;
overflow: hidden;
margin: 20px auto;
border: 1px #000 solid;
border-bottom: none;
border-right: none;
}
#ul li {
border: 1px #000 solid;
border-top: none;
border-left: none;
float: left;
}
#ul li.sty1 {
background-color: red;
}
#ul li.sty2 {
background-color: green;
}
#ul li.sty3 {
background-color: blue;
}
#input {
width: 100px;
position: absolute;
left: 50%;
margin-left: -50px;
}
</style>
<body>
<ul id="ul"></ul>
<input type="button" value="開始尋路" id="input">
</body>
</html>
??在script中寫入map埋泵,然后繪制網(wǎng)格
let map = [
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,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,0,0,0,0,0,0,0,0,
0,0,0,1,0,0,0,0,3,3,3,3,3,3,3,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,3,3,3,3,3,0,0,0,0,0,
0,0,0,0,0,0,0,0,3,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,0,0,0,0,0,0,2,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,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
]
let oUl = document.getElementById('ul')
let aLi = oUl.getElementsByTagName('li')
let oInput = document.getElementById('input')
let beginLi = oUl.getElementsByClassName('sty1') // 開始點
let endLi = oUl.getElementsByClassName('sty2') // 結(jié)束點
let cols = Math.sqrt(map.length) // 行數(shù)
let sizeGird = 20 // 表格寬度
function createMap() {
oUl.style.width = cols * (sizeGird + 1) + 1 + 'px'
for (let i = 0; i < map.length; i++) {
let oLi = document.createElement('li')
oLi.style.width = sizeGird + 'px'
oLi.style.height = sizeGird + 'px'
oUl.appendChild(oLi)
if (map[i] === 1) {
oLi.className = 'sty1'
} else if (map[i] ===2) {
oLi.className = 'sty2'
} else if (map[i] ===3) {
oLi.className = 'sty3'
}
}
}
createMap()
??編寫估價算法
function f(nodeLi) {
return g(nodeLi) + h(nodeLi)
}
function g(nodeLi) {
let a = beginLi[0].offsetLeft - nodeLi.offsetLeft
let b = beginLi[0].offsetTop - nodeLi.offsetTop
return Math.sqrt(a*a + b*b)
}
function h(nodeLi) {
let a = endLi[0].offsetLeft - nodeLi.offsetLeft
let b = endLi[0].offsetTop - nodeLi.offsetTop
return Math.sqrt(a*a + b*b)
}
??做兩個數(shù)組幔欧,openArr儲存已選擇的路徑(下一步將不會走這些路徑)、closeArr 儲存不可選的路徑
let openArr = []
let closeArr = []
??初始的openArr就是圖上的紅方塊丽声,初始的closeArr是藍方塊礁蔗。可選擇的路徑result是當前路徑元素周邊的8個黃色的方塊雁社,查找過程用findLi函數(shù)實現(xiàn)浴井。
function findLi(nowLi) {
let result = []
for (let i = 0; i < aLi.length; i++) {
if (filter(aLi[i])) {
result.push(aLi[i])
}
}
function filter(li) {
for (let i = 0; i < closeArr.length; i++) {
if (closeArr[i] == li) {
return false
}
}
for (let i = 0; i < openArr.length; i++) {
if (openArr[i] == li) {
return false
}
}
return true
}
for (let i = 0; i < result.length; i++) {
if ((Math.abs(nowLi.offsetLeft - result[i].offsetLeft) <= (sizeGird + 1)) && (Math.abs(nowLi.offsetTop - result[i].offsetTop) <= sizeGird + 1)) {
openArr.push(result[i])
}
}
}
??通過上面的方法,我們已經(jīng)可以找到當前路徑元素的下一步可選路徑霉撵,共有8種選擇磺浙,接下來就是如何從這8種選擇選下步?這里我們選擇估價最小為下一路徑元素徒坡。
function openFn() {
let nowLi = openArr.shift()
if (nowLi == endLi[0]) {
return ;
}
closeFn(nowLi)
findLi(nowLi)
openArr.sort(function(li1, li2) {
return li1.num - li2.num
})
openFn()
}
??這里我們用排序的方式找到估價最小的路徑元素撕氧,需要把計算的估價掛載到該路徑元素上,對findLi方法進行改造喇完,
if ((Math.abs(nowLi.offsetLeft - result[i].offsetLeft) <= (sizeGird + 1)) && (Math.abs(nowLi.offsetTop - result[i].offsetTop) <= sizeGird + 1)) {
result[i].num = f(result[i])
openArr.push(result[i])
}
??上面的方法呵曹,已經(jīng)實現(xiàn)了路徑的搜索,接下來我們再做一些操作,把搜索過程展示出來奄喂。
??該搜索過程的全部信息就存儲在closeArr數(shù)組铐殃,就是上圖中標出的不可選路徑的第二部分。但由于障礙物藍色方塊的存在跨新,closeArr的路徑可能會很長富腊,想要清晰的展示出搜索過程,展示closeArr不是好方法域帐。
??我們可以利用回溯赘被,closeArr的最后一位是目標點,由目標點回溯到上一步路徑元素肖揣,然后由該路徑元素回溯到它的上一步路徑元素民假,直到回溯到起始點,該回溯過程就可以表示搜索過程龙优。
??我們再次對findLi方法進行改造羊异,掛載回溯用的的上一步路徑元素。
if ((Math.abs(nowLi.offsetLeft - result[i].offsetLeft) <= (sizeGird + 1)) && (Math.abs(nowLi.offsetTop - result[i].offsetTop) <= sizeGird + 1)) {
result[i].num = f(result[i])
result[i].parent = nowLi
openArr.push(result[i])
}
??最后寫一個showLine方法彤断,用于展示該回溯過程野舶。
function showLine() {
let result = []
let lastLi = closeArr.pop()
let isNow = 0
findParent(lastLi)
function findParent(li) {
result.unshift(li)
if (li.parent == beginLi[0]) {
return ;
}
findParent(li.parent)
}
let timer = setInterval(function() {
result[isNow].style.background = 'red'
isNow++
if(isNow == result.length) {
clearInterval(timer)
}
}, 500)
}
??好的,這樣我們就完成整個搜索過程宰衙。
完整代碼如下:
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Title</title>
</head>
<style>
* {
margin: 0;
padding: 0;
}
li {
list-style: none;
}
#ul {
height: auto;
overflow: hidden;
margin: 20px auto;
border: 1px #000 solid;
border-bottom: none;
border-right: none;
}
#ul li {
border: 1px #000 solid;
border-top: none;
border-left: none;
float: left;
}
#ul li.sty1 {
background-color: red;
}
#ul li.sty2 {
background-color: green;
}
#ul li.sty3 {
background-color: blue;
}
#input {
width: 100px;
position: absolute;
left: 50%;
margin-left: -50px;
}
</style>
<body>
<ul id="ul"></ul>
<input type="button" value="開始尋路" id="input">
</body>
<script >
let oUl = document.getElementById('ul')
let aLi = oUl.getElementsByTagName('li')
let oInput = document.getElementById('input')
let beginLi = oUl.getElementsByClassName('sty1')
let endLi = oUl.getElementsByClassName('sty2')
let map = [
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,3,3,3,3,3,3,3,3,0,0,0,0,0,
0,0,0,0,0,0,0,3,3,3,3,3,3,3,3,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,1,0,0,0,0,3,3,3,3,3,3,3,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,3,3,3,3,3,0,0,0,0,0,
0,0,0,0,0,0,0,0,3,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,0,0,0,0,0,0,2,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,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
]
let cols = Math.sqrt(map.length)
let sizeGird = 20
let openArr = []
let closeArr = []
init ()
function init() {
createMap()
oInput.onclick = function() {
openFn()
}
}
function createMap() {
oUl.style.width = cols * ( sizeGird + 1 ) + 1 + 'px'
for (let i = 0; i < map.length; i++) {
let 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 f(nodeLi) {
return g(nodeLi) + h(nodeLi)
}
function g(nodeLi) {
let a = beginLi[0].offsetLeft - nodeLi.offsetLeft
let b = beginLi[0].offsetTop - nodeLi.offsetTop
return Math.sqrt(a*a + b*b)
}
function h(nodeLi) {
let a = endLi[0].offsetLeft - nodeLi.offsetLeft
let b = endLi[0].offsetTop - nodeLi.offsetTop
return Math.sqrt(a*a + b*b)
}
function openFn() {
let nowLi = openArr.shift()
if (nowLi == endLi[0]) {
showLine()
return ;
}
closeFn(nowLi)
findLi(nowLi)
openArr.sort(function(li1, li2) {
return li1.num - li2.num
})
openFn()
}
function closeFn(nowLi) {
closeArr.push(nowLi)
}
function findLi(nowLi) {
let result = []
for (let i = 0; i < aLi.length; i++) {
if (filter(aLi[i])) {
result.push(aLi[i])
}
}
function filter(li) {
for (let i = 0; i < closeArr.length; i++) {
if (closeArr[i] == li) {
return false
}
}
for (let i = 0; i < openArr.length; i++) {
if (openArr[i] == li) {
return false
}
}
return true
}
for (let i = 0; i < result.length; i++) {
if ((Math.abs(nowLi.offsetLeft - result[i].offsetLeft) <= (sizeGird + 1)) && (Math.abs(nowLi.offsetTop - result[i].offsetTop) <= sizeGird + 1)) {
result[i].num = f(result[i])
result[i].parent = nowLi
openArr.push(result[i])
}
}
}
function showLine() {
let result = []
let lastLi = closeArr.pop()
console.log(lastLi)
let isNow = 0
findParent(lastLi)
function findParent(li) {
result.unshift(li)
if (li.parent == beginLi[0]) {
return ;
}
findParent(li.parent)
}
let timer = setInterval(function() {
result[isNow].style.background = 'red'
isNow++
if(isNow == result.length) {
clearInterval(timer)
}
}, 500)
}
</script>
</html>