本文翻譯自 JavaScript AI For An HTML Sliding Tiles Puzzle By Arnaldo Perez Castano 苔悦。
Sam Loud (1841 - 1911) 美國國際象棋手枫疆，智力游戲設(shè)計(jì)師，在1870年代發(fā)明了數(shù)字推盤游戲送膳。這個(gè)游戲由 m 行 n 列的網(wǎng)格組成揖膜，每個(gè)格子可以是任何有規(guī)律的事物疮蹦，比如數(shù)字惰瓜，字母搪缨，圖片等。
游戲的解答過程是將一個(gè)排布變成另一個(gè)排布鸵熟，即從初始狀態(tài)到目標(biāo)狀態(tài)。重新排序的方式是將空的格子和它邊上的格子通過上下左右四個(gè)方向的交換來完成的负甸。
空的格子不能被移除出邊框流强，因此如果它在第一列的話，空格不能往左移動；如果它在最右邊的一列的話，它就不能再往右移動了。行的規(guī)定也是類似的。解的過程是這樣的：
這是開局夕吻。
這樣就算解出了。
只要驗(yàn)證左邊的排布和右邊的目標(biāo)排布是一樣的就可以判斷是否完成了默勾。
本文將分兩個(gè)部分习霹。第一部分會簡要解釋怎么編寫一個(gè)推盤游戲煞檩，用 html, css 實(shí)現(xiàn)顯示部分，然后用 javascript 來移動盤上的滑塊陶衅。這部分同時(shí)也用在下一部分的文章中。
文章的第二部分，我們會用 A* 算法來開發(fā)一個(gè)人工智能慨丐，用來解決推盤游戲，計(jì)算解答游戲的最小步數(shù)瞪讼。A* 算法的多種啟發(fā)式會給尋找解法帶來很多幫助，啟發(fā)式越智能嫡霞，那么就能越快找到最優(yōu)解法。啟發(fā)式會按照智能程度由低到高，因此最后的啟發(fā)式將是最強(qiáng)大的。
布局
首先我們創(chuàng)建一個(gè)空項(xiàng)目抡蛙，包含一個(gè) html 文件和一個(gè) css 文件。分別是： index.html 和 index.css 极祸。
引入 jquery.js 為了讓生活更美好慈格，寫出更加簡潔優(yōu)雅的代碼。（譯者注：此處的文件名按照本人習(xí)慣稍作改動）
html 文件的頭部如下：
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=0">
<link type="image/png" rel="shortcut icon" href="/vivaxy.icon.png">
<link type="text/css" rel="stylesheet" href="index.css">
<title>Sliding Tiles Puzzle</title>
</head>
為了頁面的性能遥金，我們把 js 都放在頁面底端浴捆。這是常見的做法，因?yàn)轫撁驿秩臼怯缮现料碌母逍担覀兿Ｍ撁嫔系脑叵蕊@示选泻，因此把用來交互的 js 文件放在頁面最下方。
<body>
<script type="text/javascript" src="js/jquery.js"></script>
<script type="text/javascript" src="js/priority-queue.js"></script>
<script type="text/javascript" src="js/hash-table.js"></script>
<script type="text/javascript" src="js/hash-set.js"></script>
<script type="text/javascript" src="js/index.js"></script>
</body>
priority-queue.js, hash-table.js, hash-set.js 是用來編寫人工智能的美莫，分別是用來存放隊(duì)列页眯，哈希表和哈希對的。
現(xiàn)在我們開始寫 html 上的布局厢呵。首先窝撵，布局的框架是這樣的。
<div class="container"></div>
<div class="panel"></div>
container 容器這個(gè)類選擇器在 index.css 文件中是這樣的
/*
Developed by Arnaldo Perez Castano
arnaldo.skywalker@gmail.com
*/
.container {
width: 1024px;
margin-left: auto;
margin-right: auto;
min-height: 380px;
}
面板是在頁面上打印顯示人工智能的日志和結(jié)果的襟铭。
.panel {
width: 100%;
background-color: rgb(180, 180, 180);
min-height: 1000px;
color: white;
font-weight: bold;
padding: 5px;
font-family: Arial;
}
我們希望容器在頁面中間碌奉，所以需要給它設(shè)置寬度短曾，并且把它的 margin-left 和 margin-right 設(shè)置為 auto。
現(xiàn)在我們在 container 中加入 grid-container 赐劣，用來顯示推盤的網(wǎng)格嫉拐。
<div class="container">
<div class="grid-container">
<h2> Initial Config </h2>
</div>
</div>
grid-container 和它下面的元素的樣式如下所示。
.grid-container {
float: left;
height: 250px;
text-align: center;
width: 50%;
}
.grid-container h2 {
font-family: Tahoma;
}
我們把推盤容器左浮動魁兼，因?yàn)閮蓚€(gè)同樣的容器要顯示在一行婉徘，一個(gè)是用來顯示初始布局的，另一個(gè)是用來顯示目標(biāo)布局的咐汞。
最后盖呼，我們的推盤是這個(gè)樣子的。
<div class="grid-container">
<h2> Initial Config </h2>
<div class="grid start">
<div class="row">
<div class="cell" data-pos="0,0"><span>6</span></div>
<div class="cell" data-pos="0,1"><span>4</span></div>
<div class="cell" data-pos="0,2"><span>7</span></div>
</div>
<div class="row">
<div class="cell" data-pos="1,0"><span>8</span></div>
<div class="cell" data-pos="1,1"><span>5</span></div>
<div class="cell" id="empty" data-pos="1,2"></div>
</div>
<div class="row">
<div class="cell" data-pos="2,0"><span>3</span></div>
<div class="cell" data-pos="2,1"><span>2</span></div>
<div class="cell" data-pos="2,2"><span>1</span></div>
</div>
</div>
</div>
推盤游戲有三行碉考，每行有三個(gè)滑塊塌计，這就組成了整個(gè)推盤網(wǎng)格。于是我們使用了以上布局侯谁，三個(gè)行容器锌仅，每個(gè)行容器有三個(gè)子元素，每個(gè)子元素是一個(gè)滑塊墙贱。
為了編程方便热芹，我們在每個(gè)子元素上添加了 data-pos 這個(gè)屬性，為了記錄每個(gè)滑塊在推盤中的位置惨撇。 start 這個(gè)類名是為了區(qū)分初始布局的推盤和目標(biāo)布局的推盤伊脓，后者不會綁定用戶操作。以上幾個(gè)類的樣式如下魁衙。
.grid {
background-color: rgb(248, 248, 248);
border: solid 5px rgb(249, 90, 0);
width: 210px;
height: 210px;
margin-left: auto;
margin-right: auto;
border-radius: 3px;
box-shadow: 5px 5px #d8d8d8, 5px 5px #d8d8d8;
overflow: auto;
}
.row {
height: 33.3%;
}
.cell {
width: 33.3%;
height: 100%;
float: left;
text-align: center;
font-size: 150%;
font-family: Arial;
font-weight: bold;
position: relative;
}
.cell:hover {
background-color: rgb(221, 221, 221);
}
.cell span {
display: block;
transform: translateY(70%);
}
最后結(jié)果如下
接下來我們把目標(biāo)布局放上去报腔，我們復(fù)制一下起始布局，把上面的 start 改成 goal 就行了剖淀。
<div class="grid-container">
<h2> Goal Config </h2>
<div class="grid goal">
<div class="row">
<div class="cell"><span>1</span></div>
<div class="cell"><span>2</span></div>
<div class="cell"><span>3</span></div>
</div>
<div class="row">
<div class="cell"><span>4</span></div>
<div class="cell"><span>5</span></div>
<div class="cell"><span>6</span></div>
</div>
<div class="row">
<div class="cell"><span>7</span></div>
<div class="cell"><span>8</span></div>
<div class="cell"></div>
</div>
</div>
</div>
最后纯蛾，我們把 Solve 和 Show Step 這兩個(gè)按鈕加到第一個(gè)布局的容器中。
<button onclick="start()"> Solve </button>
<button onclick="showSolution()"> Show Step </button>
第一個(gè)按鈕會執(zhí)行自動計(jì)算纵隔，也就是 A* 算法翻诉。第二個(gè)按鈕會顯示自動計(jì)算的一步。所以捌刮，按第二個(gè)按鈕多次之后我們就得到這個(gè)推盤游戲的最優(yōu)解法了碰煌。
我們已經(jīng)把所有界面展示部分完成了，那么我們開始寫一些功能模塊的部分绅作。我們現(xiàn)在要讓這個(gè)游戲能動起來嫡丙，其實(shí)就是要讓空白的滑塊能夠在整個(gè)推盤中移動摔刁。我們用 javascript 來實(shí)現(xiàn)這個(gè)功能愚隧。 index.js 文件的前幾行如下：
/*
Developed by Arnaldo Perez Castano
arnaldo.skywalker@gmail.com
*/
var emptytilePosRow = 1;
var emptytilePosCol = 2;
var cellDisplacement = '69px';
emptytilePosRow 和 emptytilePosCol 這兩個(gè)變量會保存空白滑塊所處的位置。每次移動的時(shí)候碍脏，都會改變。
cellDisplacement 這個(gè)變量用來記錄這個(gè)滑塊在動畫執(zhí)行過程中所移動的距離稍算。cell 這個(gè)類所在的 div 的 position 是 relative 。所以我們用 top 和 right 這兩個(gè)屬性來實(shí)現(xiàn)動畫效果役拴。 cellDisplacement 變量會記錄下 top 和 right 的最新的值糊探，來實(shí)現(xiàn)滑塊的移動。
用來實(shí)現(xiàn)移動的方法如下：
var moveTile = function (e) {
// Gets the position of the current element
var pos = $(this).attr('data-pos');
var posRow = parseInt(pos.split(',')[0]);
var posCol = parseInt(pos.split(',')[1]);
// ...
};
請看河闰，我們已經(jīng)用上 jquery 來選擇元素了科平。還要注意我們要用 start 這個(gè)類來讓我們選擇的都是初始布局中的元素，來保證目標(biāo)布局不變姜性。然后瞪慧，我們拿到選中的滑塊的位置。位置是用 x,y 這種形式存的部念。然后我們拿到了行和列的值弃酌，存在 posRow 和 posCol 這兩個(gè)變量中。
接下來的代碼是用來執(zhí)行移動的儡炼。
// Move Up
if (posRow + 1 == emptytilePosRow && posCol == emptytilePosCol) {
$(this).animate({
'top': "+=" + cellDisplacement //moves up
});
$('#empty').animate({
'top': "-=" + cellDisplacement //moves down
});
emptytilePosRow -= 1;
$(this).attr('data-pos', (posRow + 1) + "," + posCol);
}
// Move Down
if (posRow - 1 == emptytilePosRow && posCol == emptytilePosCol) {
$(this).animate({
'top': "-=" + cellDisplacement //moves down
});
$('#empty').animate({
'top': "+=" + cellDisplacement //moves up
});
emptytilePosRow += 1;
$(this).attr('data-pos', (posRow - 1) + "," + posCol);
}
// Move Left
if (posRow == emptytilePosRow && posCol + 1 == emptytilePosCol) {
$(this).animate({
'right': "-=" + cellDisplacement //moves right
});
$('#empty').animate({
'right': "+=" + cellDisplacement //moves left
});
emptytilePosCol -= 1;
$(this).attr('data-pos', posRow + "," + (posCol + 1));
}
// Move Right
if (posRow == emptytilePosRow && posCol - 1 == emptytilePosCol) {
$(this).animate({
'right': "+=" + cellDisplacement //moves left
});
$('#empty').animate({
'right': "-=" + cellDisplacement //moves right
});
emptytilePosCol += 1;
$(this).attr('data-pos', posRow + "," + (posCol - 1));
}
// Update empty position
$('#empty').attr('data-pos', emptytilePosRow + "," + emptytilePosCol);
每個(gè) if 語句表示不同的移動方向妓湘。他們開起來差不多，只是條件乌询，移動方向和更新的變量不同而已榜贴。比如向右移動，要看空的滑塊是不是在當(dāng)前移動的滑塊的左邊：posRow === emptytilePosRow 表示在一行妹田，posCol - 1 === emptytileCol 表示空白的滑塊在當(dāng)前移動的滑塊的左邊一列唬党。
如果條件滿足，則執(zhí)行 jquery 的動畫鬼佣，我們改變 right 屬性的值驶拱，來移動當(dāng)前選中的滑塊。if 的條件語句的最后沮趣，我們修改 emptytilePosCol 的值屯烦，在其原來的值上加 1 ，因?yàn)榭瞻椎幕瑝K向右移動了一格房铭。同時(shí)我們修改當(dāng)前移動的滑塊的位置的值驻龟，列數(shù)減1。最后我們改變空白滑塊的位置缸匪。
人工智能
A* 搜尋算法（ Hart 等人在 1968 年提出）是用來計(jì)算多節(jié)點(diǎn)路徑中兩點(diǎn)之間最短距離的算法翁狐。我們用它來開發(fā)解答滑塊游戲的功能。一個(gè)人工智能是能夠在某種環(huán)境下按照特定的規(guī)則完成特定的任務(wù)的一種工具凌蔬。最終的解法將有人工執(zhí)行這個(gè)工具通過正確的決策來尋找露懒。
人類在大部分情況下是理性的闯冷。一個(gè)人會根據(jù)所處環(huán)境的不同，從環(huán)境中得到信息懈词，來對特定的情況采取理性的行為蛇耀。比如在寒冷的冬天，我們會感到寒冷坎弯，于是我們會穿上厚厚的外套纺涤。
在滑塊游戲這個(gè)場景下，環(huán)境是由整個(gè)板子決定的抠忘×么叮滑塊游戲的規(guī)則決定某個(gè)滑塊能夠向某個(gè)方向移動。如果該搜尋算法是有效的話崎脉，那么在一定的移動步數(shù)后拧咳，滑塊的布局會變成目標(biāo)布局。
A* 搜尋算法能做什么
A* 搜尋算法能夠找到從一種空間布局到另一種空間布局轉(zhuǎn)換方法囚灼。搜尋是否智能是根據(jù)轉(zhuǎn)換過程中操作的步數(shù)來判斷的骆膝，步數(shù)越少，算法越智能啦撮。為了能方便描述布局狀態(tài)谭网，我們把問題轉(zhuǎn)換成圖形。我們認(rèn)為狀態(tài) B 是狀態(tài) A 的下一種狀態(tài)赃春，也就是說要到狀態(tài) B 就要先到狀態(tài) A 愉择，由狀態(tài) A 通過移動一個(gè)滑塊就能夠到達(dá)狀態(tài) B 了。所以一個(gè)狀態(tài)節(jié)點(diǎn)會有如下的四中子狀態(tài)節(jié)點(diǎn)织中。
A* 算法下節(jié)點(diǎn)示意圖
A* 搜尋算法基本思路是根據(jù)外界環(huán)境來選擇下一步的行為锥涕。外界環(huán)境是由數(shù)字組成的。假設(shè)狀態(tài)為 s 狭吼，那么
f(s) = g(s) + h(s)
其中 g(s) 是從初始狀態(tài)到狀態(tài) s 的總步數(shù)层坠，h(s) 是從狀態(tài) s 到目標(biāo)狀態(tài)的總步數(shù)，所以總步數(shù)是 f(s) 刁笙。
從其實(shí)狀態(tài)到目標(biāo)狀態(tài)的總步數(shù)
我們使用啟發(fā)式來尋找這巨大可能中的情況破花。啟發(fā)式是一種載體，我們可以通過它將我們的經(jīng)驗(yàn)和特定環(huán)境傳遞到人工智能算法中去疲吸，也就是傳遞到 A* 算法中去座每。通過啟發(fā)式，我們就能找到解答問題的最短的途徑了摘悴。
既然我們已經(jīng)把問題轉(zhuǎn)換成圖像了峭梳，那么 A* 算法的大概框架就變得和 BFS 算法（廣度優(yōu)先算法）差不多了。BFS 算法是一種經(jīng)典的圖形節(jié)點(diǎn)算法蹂喻。 A* 算法和 BFS 算法的區(qū)別在于葱椭， A* 算法中下一環(huán)節(jié)開始計(jì)算的節(jié)點(diǎn)的選擇是和 f(s) 的值關(guān)聯(lián)的捂寿，會優(yōu)先選擇最短的 f(s) 來優(yōu)先計(jì)算 ，但是在 BFS 算法中孵运，所有節(jié)點(diǎn)的選擇權(quán)重都是 1 秦陋，所以哪個(gè)路徑更短并沒有任何影響，在 BFS 算法中治笨，下一環(huán)節(jié)的計(jì)算會從先記錄的節(jié)點(diǎn)開始踱侣，也就是先進(jìn)先出（FIFO）的隊(duì)列原則。
我們建立啟發(fā)式的時(shí)候大磺，一定要保證其中包含了所有關(guān)鍵信息。不知道這段是什么意思探膊。不過大概說了要有個(gè)條件讓 A* 算法能找到最優(yōu)解杠愧，類似于函數(shù)收斂則能找到極值。
前面說到我們要用 javascript 來寫人工智能逞壁，有些人大概會認(rèn)為這是不明智的流济，不過后面我會證明 javascript 擁有足夠的能力。我們先寫一個(gè) Node 對象腌闯。
var Node = function (value, state, emptyRow, emptyCol, depth) {
this.value = value;
this.state = state;
this.emptyCol = emptyCol;
this.emptyRow = emptyRow;
this.depth = depth;
this.strRepresentation = '';
this.path = '';
// String representation of the state in CSV format
for (var i = 0; i < state.length; i++) {
// We assume the state is a square
if (state[i].length !== state.length) {
alert('Number of rows differs from number of columns');
return;
}
for (var j = 0; j < state[i].length; j++) {
this.strRepresentation += state[i][j] + ',';
}
}
this.size = this.state.length;
};
每個(gè)變量的說明如下：
valuef(s) 的值state用二維數(shù)組保存滑塊排布的狀態(tài)emptyCol記錄空滑塊所在的列emptyRow記錄空滑塊所在的行depth記錄從起始狀態(tài)到現(xiàn)在的步數(shù)strRepresentationCSV 字符串的形式保存滑塊布局的狀態(tài)绳瘟。比如目標(biāo)布局的值是 1,2,3,4,5,6,7,8 ∽丝ィ滑塊游戲布局是一個(gè)可以循環(huán)的游戲糖声，也就是說從狀態(tài) s 經(jīng)過一定的移動可以回到狀態(tài) s 。因此我們需要記錄下每步的布局來避免走重復(fù)的路分瘦。這里我們會用 HashSet 蘸泻。path記錄每步的移動，用 DLRU 嘲玫。這個(gè)字符串保存的是從其實(shí)布局到當(dāng)前布局走過的路悦施。size滑塊游戲推盤的大小，我們假設(shè)推盤是 n 乘以 m 的去团，n 等于 m 抡诞。
現(xiàn)在我們有了 Node 這個(gè)對象，我們來用個(gè)例子演示一下使用 A* 算法解題的過程土陪。我們用最簡單的啟發(fā)式昼汗，根據(jù)放錯(cuò)位置的滑塊的個(gè)數(shù)來。錯(cuò)位啟發(fā)式返回的值就是不在自己應(yīng)該在的位置的滑塊的個(gè)數(shù)旺坠。這里說明了這個(gè)啟發(fā)式是可接受的乔遮。
A* 搜尋算法
下面我們來實(shí)現(xiàn) A* 算法：
var AStar = function (initial, goal, empty) {
this.initial = initial;
this.goal = goal;
this.empty = empty;
this.queue = new PriorityQueue({
comparator: function (a, b) {
if (a.value > b.value) {
return 1;
}
if (a.value < b.value) {
return -1;
}
return 0;
}
});
this.queue.queue(initial);
this.visited = new HashSet();
};
上面我們以及功能使用了之前定義的數(shù)據(jù)結(jié)構(gòu)。優(yōu)先隊(duì)列中我們定義了一種排序方法取刃，我們會把 f(s) 較小的狀態(tài)放在前面蹋肮。哈希對中存放 strRepresentation 記錄所有到達(dá)過的狀態(tài)，來避免重復(fù)坯辩。
現(xiàn)在我們用原型鏈給 A* 算法添加方法馁龟。 原型鏈 prototype 是一種方法或者屬性，在創(chuàng)建新對象實(shí)例時(shí)漆魔，這個(gè)方法或者屬性會成為新實(shí)例的一部分坷檩。比如， execute 這個(gè)方法會在所有 AStar 對象中存在改抡。
AStar.prototype.execute = function () {
// Add current state to visited list
this.visited.add(this.initial.strRepresentation);
while (this.queue.length > 0) {
var current = this.queue.dequeue();
if (current.strRepresentation === this.goal.strRepresentation) {
return current;
}
this.expandNode(current);
}
};
execute 方法在以下幾點(diǎn)上像 BFS ：
有循環(huán)矢炼，循環(huán)結(jié)束于優(yōu)先隊(duì)列結(jié)束后。
當(dāng)前的變量存放的是隊(duì)列中的最小值阿纤。
如果節(jié)點(diǎn)的狀態(tài)與目標(biāo)狀態(tài)匹配的話句灌，那么我們認(rèn)為整個(gè)搜尋任務(wù)結(jié)束。
如果搜尋任務(wù)沒有結(jié)束欠拾，那么我們會對當(dāng)前的節(jié)點(diǎn)進(jìn)行展開胰锌。也就是在當(dāng)點(diǎn)狀態(tài)下執(zhí)行每個(gè)方向的移動，然后把新的節(jié)點(diǎn)添加到隊(duì)列中藐窄。
對節(jié)點(diǎn)展開的方法如下：
AStar.prototype.expandNode = function (node) {
var temp = '';
var newState = '';
var col = node.emptyCol;
var row = node.emptyRow;
var newNode = '';
// Up
if (row > 0) {
newState = node.state.clone();
temp = newState[row - 1][col];
newState[row - 1][col] = this.empty;
newState[row][col] = temp;
newNode = new Node(0, newState, row - 1, col, node.depth + 1);
if (!this.visited.contains(newNode.strRepresentation)) {
newNode.value = newNode.depth + this.heuristic(newNode);
newNode.path = node.path + 'U';
this.queue.queue(newNode);
this.visited.add(newNode.strRepresentation);
}
}
// Down
if (row < node.size - 1) {
newState = node.state.clone();
temp = newState[row + 1][col];
newState[row + 1][col] = this.empty;
newState[row][col] = temp;
newNode = new Node(0, newState, row + 1, col, node.depth + 1);
if (!this.visited.contains(newNode.strRepresentation)) {
newNode.value = newNode.depth + this.heuristic(newNode);
newNode.path = node.path + 'D';
this.queue.queue(newNode);
this.visited.add(newNode.strRepresentation);
}
}
// Left
if (col > 0) {
newState = node.state.clone();
temp = newState[row][col - 1];
newState[row][col - 1] = this.empty;
newState[row][col] = temp;
newNode = new Node(0, newState, row, col - 1, node.depth + 1);
if (!this.visited.contains(newNode.strRepresentation)) {
newNode.value = newNode.depth + this.heuristic(newNode);
newNode.path = node.path + 'L';
this.queue.queue(newNode);
this.visited.add(newNode.strRepresentation);
}
}
// Right
if (col < node.size - 1) {
newState = node.state.clone();
temp = newState[row][col + 1];
newState[row][col + 1] = this.empty;
newState[row][col] = temp;
newNode = new Node(0, newState, row, col + 1, node.depth + 1);
if (!this.visited.contains(newNode.strRepresentation)) {
newNode.value = newNode.depth + this.heuristic(newNode);
newNode.path = node.path + 'R';
this.queue.queue(newNode);
this.visited.add(newNode.strRepresentation);
}
}
};
這里的 if 條件語句都很像资昧，差別只是他們針對的移動方向不同。首先荆忍，我們判斷一下這步是否能夠正常進(jìn)行格带。比如向右移動，只有空滑塊的列數(shù)小于推盤的行數(shù)才行刹枉。如果這步能夠正常移動践惑，那么我們建立一個(gè)新的狀態(tài) newState ，這個(gè)狀態(tài)是從當(dāng)前狀態(tài)復(fù)制出來的嘶卧。然后我們交換空白滑塊和對應(yīng)元素尔觉，同時(shí)修改 newState ，最后我們判斷一下這個(gè)狀態(tài)是不是已經(jīng)存在了芥吟，如果沒有存在的話侦铜，把這個(gè)狀態(tài)記錄到隊(duì)列中去。我們還要計(jì)算一下節(jié)點(diǎn)的值钟鸵，按照之間提到過的 f = g + h 钉稍，然后在 path 變量中記錄下移動的方向。
Array.prototype.clone = function () {
return JSON.parse(JSON.stringify(this));
};
最后別忘了啟發(fā)式方法
AStar.prototype.heuristic = function (node) {
return this.manhattanDistance(node);
};
這里開始棺耍，我們就能比較不用啟發(fā)式下的 A* 算法的效率了贡未。我們會慢慢發(fā)現(xiàn)一個(gè)啟發(fā)式對于算法來說是至關(guān)重要的，其智能程度極大地影響了算法的耗時(shí)。
錯(cuò)位滑塊
在我們進(jìn)入有趣的啟發(fā)式之前俊卤，先記得在計(jì)算啟發(fā)式的時(shí)候嫩挤，我們絕對不會考慮空白滑塊。否則我們就會過高估路徑的步數(shù)了消恍，那么啟發(fā)式可能不能被接受了岂昭。比如下面這個(gè)情況：
如果們我考慮空白滑塊，那么 h 就是 2 了狠怨，而事實(shí)上约啊，我們只要把空白滑塊向下移動一步就行了。因此實(shí)際的最短步數(shù)是 1 佣赖，而不是二恰矩，我們高估路徑的步數(shù)了。
為了測試我們的啟發(fā)式憎蛤，我們用一個(gè)最差情況來試一試枢里，這個(gè)情況下需要 31 步才能完成解答。
A* 算法在點(diǎn)擊 Solve 按鈕后會執(zhí)行蹂午。onclick 觸發(fā)的事件是執(zhí)行 start 方法，方法的內(nèi)容如下：
var start = function () {
var init = new Node(0, [[6, 4, 7], [8, 5, 0], [3, 2, 1]], 1, 2, 0);
var goal = new Node(0, [[1, 2, 3], [4, 5, 6], [7, 8, 0]], 2, 2, 0);
var aStar = new AStar(init, goal, 0);
// To measure time taken by the algorithm
var startTime = new Date();
// Execute AStar
var result = aStar.execute();
// To measure time taken by the algorithm
var endTime = new Date();
alert('Completed in: ' + (endTime - startTime) + ' milliseconds');
var panel = document.getElementById('panel');
panel.innerHTML = 'Solution: ' + result.path + ' Total steps: ' + result.path.length + '';
solution = result.path;
};
我們用毫秒來記錄算法的耗時(shí)彬碱。用這種方式來評估不同啟發(fā)式之間的優(yōu)劣豆胸。錯(cuò)位滑塊啟發(fā)式的代碼如下：
AStar.prototype.misplacedTiles = function (node) {
var result = 0;
for (var i = 0; i < node.state.length; i++) {
for (var j = 0; j < node.state[i].length; j++) {
if (node.state[i][j] != this.goal.state[i][j] && node.state[i][j] != this.empty) {
result++;
}
}
}
return result;
};
執(zhí)行結(jié)果如下：
算法花了將近 4 秒來解答，誒喲巷疼，不錯(cuò)喲晚胡。但是我們可以用一個(gè)更加棒的啟發(fā)式來讓計(jì)算更快。
曼哈頓距離
曼哈頓距離或者塊距離是用來計(jì)算兩點(diǎn)間距離的絕對值的嚼沿。
MD = | x1 - x2 | + | y1 - y2 |
A 點(diǎn) (x1, y1) 和 B 點(diǎn) (x2, y2) 之間的距離
這個(gè)結(jié)果是可接受的估盘，因?yàn)樗肋h(yuǎn)給出的是兩點(diǎn)之間最短的路徑。
AStar.prototype.manhattanDistance = function (node) {
var result = 0;
for (var i = 0; i < node.state.length; i++) {
for (var j = 0; j < node.state[i].length; j++) {
var elem = node.state[i][j];
var found = false;
for (var h = 0; h < this.goal.state.length; h++) {
for (var k = 0; k < this.goal.state[h].length; k++) {
if (this.goal.state[h][k] == elem) {
result += Math.abs(h - i) + Math.abs(j - k);
found = true;
break;
}
}
if (found) {
break;
}
}
}
}
return result;
};
使用了這個(gè)啟發(fā)式的結(jié)果如下：
我們已經(jīng)大大減少了計(jì)算時(shí)間骡尽，現(xiàn)在只要 1 秒不到遣妥。曼哈頓距離這個(gè)啟發(fā)式更加精確地估算了離目標(biāo)布局的步數(shù)，因此我們可以更快地到達(dá)目的地攀细。
結(jié)合曼哈頓距離和線性沖突
盡管嗎哈頓距離大大縮小了算法的耗時(shí)箫踩，但是依然有很多優(yōu)化可以做。線性沖突啟發(fā)式提供了這個(gè)關(guān)鍵點(diǎn)谭贪。如果 tj 和 tk 這兩個(gè)是在用一條線上境钟，并且他們兩個(gè)的目的地都是在這條線上，并且 tj 要去 tk 那個(gè)方向俭识，tk 要去 tj 那個(gè)方向慨削，那么我們說 tj 和 tk 是線性沖突的。
左邊的布局，滑塊 3 和滑塊 1 在一行中缚态，但是不在正確的位置磁椒。為了讓他們能夠到正確的位置上去，我們必須把其中一塊向下移動猿规，再把它移上來衷快，這個(gè)移動的行為在曼哈頓距離啟發(fā)式中沒有考慮進(jìn)去。要注意姨俩，一個(gè)滑塊不可能和很多個(gè)滑塊產(chǎn)生線性沖突蘸拔，因?yàn)榻鉀Q了一個(gè)線性沖突后，也就解決了這一行的所有線性沖突了环葵。因此，如果滑塊 1 和滑塊 3 是線性沖突的菊卷，那么滑塊 1 和滑塊 2 就不是線性沖突的了洁闰，否則啟發(fā)式就變得不可接受，我們會高估解答的步數(shù)聘裁。線性沖突啟發(fā)式的代碼如下：
AStar.prototype.linearConflicts = function (node) {
var result = 0;
var state = node.state;
// Row Conflicts
for (var i = 0; i < state.length; i++) {
result += this.findConflicts(state, i, 1)
}
// Column Conflicts
for (var i = 0; i < state[0].length; i++) {
result += this.findConflicts(state, i, 0)
}
return result;
};
AStar.prototype.findConflicts = function (state, i, dimension) {
var result = 0;
var tilesRelated = [];
// Loop foreach pair of elements in the row/column
for (var h = 0; h < state.length - 1 && tilesRelated.indexOf(h) === -1; h++) {
for (var k = h + 1; k < state.length && tilesRelated.indexOf(h) === -1; k++) {
var moves = dimension == 1
? this.inConflict(i, state[i][h], state[i][k], h, k, dimension)
: this.inConflict(i, state[h][i], state[k][i], h, k, dimension);
if (moves == 0) {
continue;
}
result += 2;
tilesRelated.push([h, k]);
break;
}
}
return result;
};
AStar.prototype.inConflict = function (index, a, b, indexA, indexB, dimension) {
var indexGoalA = -1;
var indexGoalB = -1;
for (var c = 0; c < this.goal.state.length; c++) {
if (dimension == 1 && this.goal.state[index][c] == a) {
indexGoalA = c;
} else if (dimension == 1 && this.goal.state[index][c] == b) {
indexGoalB = c;
} else if (dimension == 0 && this.goal.state[c][index] == a) {
indexGoalA = c;
} else if (dimension == 0 && this.goal.state[c][index] == b) {
indexGoalB = c;
}
}
return (indexGoalA >= 0 && indexGoalB >= 0) &&
((indexA < indexB && indexGoalA > indexGoalB) ||
(indexA > indexB && indexGoalA < indexGoalB))
? 2
: 0;
};
既然線性沖突啟發(fā)式和曼哈頓距離啟發(fā)式之間不會發(fā)生沖突捌显，那么我們可以把他們兩個(gè)結(jié)合起來摄闸，來獲得一個(gè)更加棒的算法乎完。
AStar.prototype.heuristic = function (node) {
return this.manhattanDistance(node) + this.linearConflicts(node);
};
加入了線性沖突啟發(fā)式后，結(jié)果如下：
加入了線性沖突啟發(fā)式后转晰，我們在計(jì)算速度上又提高了很大一截。如果想看結(jié)果的話，我們可以看灰色的面板上顯示的內(nèi)容番官。
按了 Show Step 按鈕之后讶凉，我們可以看到解法的一步懂讯。按了 31 步之后台颠，我們就能看到解答的整個(gè)過程了实蔽。
這篇文章我們介紹了用人工智能 A* 算法解推盤游戲的方法。我們驗(yàn)證了不同啟發(fā)式下結(jié)果的正確性填具，并且成功地找到了一種非常有效的啟發(fā)式∮颍現(xiàn)在你可以用它來打敗你的朋友們了。我們體會了人工智能的神奇，我們用它來解決了生活中的問題筋量。人工智能的最終的目的是給我們帶來更加輕松而高效的生活。
