摘要：寫在最前本次分享一下通過廣度優(yōu)先搜索解決八數(shù)碼問題并展示其最短路徑的動(dòng)畫效果。一個(gè)排列中逆序的總數(shù)就稱為這個(gè)排列的逆序數(shù)。如果起始狀態(tài)與結(jié)束狀態(tài)的逆序數(shù)的奇偶性相同，則說明狀態(tài)可達(dá)，反之亦然。

本次分享一下通過廣度優(yōu)先搜索解決八數(shù)碼問題并展示其最短路徑的動(dòng)畫效果。

歡迎關(guān)注我的博客，不定期更新中——

該效果為從[[2, 6, 3],[4, 8, 0],[7, 1, 5]] ==> [[[1, 2, 3],[4, 5, 6],[7, 8, 0]]]的效果展示

源碼地址

配置方式如下：

var option = {
    startNode: [
        [2, 6, 3],
        [4, 8, 0],
        [7, 1, 5]
    ],
    endNode: [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 0]
    ],
    animateTime: "300" //每次交換數(shù)字所需要的動(dòng)畫時(shí)間
}
var eightPuzzles = new EightPuzzles(option)

百度一下可以百度出來很多介紹，在此簡單說明一下八數(shù)碼問題所要解決的東西是什么，即將一幅圖分成3*3的格子其中八個(gè)是圖一個(gè)空白，俗稱拼圖游戲=。=，我們需要求解的就是從一個(gè)散亂的狀態(tài)到恢復(fù)原狀最少需要多少步，以及每步怎么走。

我們可以抽象為現(xiàn)有數(shù)字0-8在九宮格中，0可以和其他數(shù)字交換。同時(shí)有一個(gè)開始狀態(tài)和結(jié)束狀態(tài)，現(xiàn)在需要求解出從初始到結(jié)束所需要的步數(shù)與過程。

網(wǎng)上有很多算法可以解決八數(shù)碼問題，本次我們采用最容易理解也是最簡單的廣度優(yōu)先搜索（BFS），雖然是無序搜索并且浪費(fèi)效率，不過我們還是先解決問題要緊，優(yōu)化的方式大家可以接著百（谷）度（歌）一下。比如A*之類的，因?yàn)樽髡咭膊惶珪?huì)（逃。

現(xiàn)在我們已知廣搜的相關(guān)概念，那么如何結(jié)合到八數(shù)碼問題中呢？

首先我們需要將八數(shù)碼中即0-8這九個(gè)數(shù)的每一種組合當(dāng)做一種狀態(tài)，那么按照排列組合定理我們可以求出八數(shù)碼可能存在的狀態(tài)數(shù)：9！即362880種排列組合。

對(duì)八數(shù)碼的每種狀態(tài)轉(zhuǎn)換為代碼中的表達(dá)方式，在此作者使用的是通過二維數(shù)組的形式，在文章的開頭的配置方式中就可以看到初始與最終狀態(tài)的二維數(shù)組表示。

為什么選擇二維數(shù)組？因?yàn)閷?duì)于0的移動(dòng)限定是有一定空間邊界的，比如0如果在第二行的最右邊，那么0只能進(jìn)行左上下三種移動(dòng)方式。通過二維數(shù)組的兩種下標(biāo)可以很方便的來判斷下一個(gè)狀態(tài)的可選方向。

將每種狀態(tài)轉(zhuǎn)化為二維數(shù)組后，就可以配合廣搜來進(jìn)行遍歷。初始狀態(tài)可以設(shè)定為廣搜中圖的第一層，由初始狀態(tài)通過判斷0的移動(dòng)方向可以得到不大于4中狀態(tài)的子節(jié)點(diǎn)，同時(shí)需要維護(hù)一個(gè)對(duì)象來記錄每個(gè)子節(jié)點(diǎn)的父節(jié)點(diǎn)是誰以此來反推出動(dòng)畫的運(yùn)動(dòng)軌跡及一個(gè)對(duì)象來負(fù)責(zé)判斷當(dāng)前子節(jié)點(diǎn)先前是否已出現(xiàn)過，出現(xiàn)過則無需再壓入隊(duì)。至此反復(fù)求出節(jié)點(diǎn)的子節(jié)點(diǎn)并無重復(fù)的壓入隊(duì)。

在遍歷狀態(tài)的過程中，可以將二維數(shù)組轉(zhuǎn)化為數(shù)字或字符串，如123456780。在變?yōu)橐痪S數(shù)組后便可以直接判斷該狀態(tài)是否等于最終狀態(tài)，因?yàn)閺臄?shù)組變?yōu)榱俗址驍?shù)字的基本類型就可以直接比較是否相等。如果相等那么從該節(jié)點(diǎn)一步步反推父節(jié)點(diǎn)至起始節(jié)點(diǎn)，得到動(dòng)畫路徑。

在頁面中通過動(dòng)畫路徑生成動(dòng)畫。

當(dāng)你明白了思想之后，我們將其轉(zhuǎn)化為代碼思路既可以表示為如下步驟：

初始節(jié)點(diǎn)壓入隊(duì)。

初始節(jié)點(diǎn)狀態(tài)計(jì)入哈希表中。

出隊(duì)，訪問節(jié)點(diǎn)。

創(chuàng)建節(jié)點(diǎn)的子結(jié)點(diǎn)，檢查是否與結(jié)束狀態(tài)相同。若是，搜索結(jié)束，若否，檢查哈希表是否存在此狀態(tài)。若已有此狀態(tài)，跳過，若無，把此結(jié)點(diǎn)壓入隊(duì)。

重復(fù)3，4步驟，即可得解。

根據(jù)目標(biāo)狀態(tài)結(jié)點(diǎn)回溯其父節(jié)點(diǎn)，可以得到完整的路徑。

通過路徑生成動(dòng)畫

看起來一切都很美好是不是？但是我們?nèi)匀缓雎粤艘粋€(gè)問題，很關(guān)鍵。

如果真的像拼圖一樣，從一個(gè)已知狀態(tài)打散到另一個(gè)狀態(tài)，那么肯定是可以復(fù)原的。但是我們現(xiàn)在的配置策略是任意的，從而我們需要判斷起始狀態(tài)是否可以達(dá)到結(jié)束狀態(tài)。判斷方式是通過起始狀態(tài)和結(jié)束狀態(tài)的逆序數(shù)是否同奇偶來判斷。

逆序數(shù)：在一個(gè)排列中，如果一對(duì)數(shù)的前后位置與大小順序相反，即前面的數(shù)大于后面的數(shù)，那么它們就稱為一個(gè)逆序。一個(gè)排列中逆序的總數(shù)就稱為這個(gè)排列的逆序數(shù)。一個(gè)排列中所有逆序總數(shù)叫做這個(gè)排列的逆序數(shù)。

如果起始狀態(tài)與結(jié)束狀態(tài)的逆序數(shù)的奇偶性相同，則說明狀態(tài)可達(dá)，反之亦然。至于為什么，作者嘗試通過簡單的例子來試圖說明并推廣到整個(gè)結(jié)論：

//起始狀態(tài)為[[1,2,3],[4,5,6],[7,8,0]]
//可以看做字符串123456780
//結(jié)束狀態(tài)為[[1,2,3],[4,5,6],[7,0,8]]
//可以看做字符串123456708

這個(gè)變換只需要一步，即0向左與8進(jìn)行交換。那么對(duì)于逆序數(shù)而言，0所在的位置是無關(guān)緊要的，因?yàn)樗日l都小，不會(huì)導(dǎo)致位置變化逆序數(shù)改變。所以0的橫向移動(dòng)不會(huì)改變逆序數(shù)的奇偶性。

//起始狀態(tài)為[[1,2,3],[4,5,6],[7,8,0]]
//可以看做字符串123456780
//結(jié)束狀態(tài)為[[1,2,3],[4,5,0],[7,8,6]]
//可以看做字符串123450786

這個(gè)變換同樣只需要一步，即0向上與6進(jìn)行交換。我們已知0的位置不會(huì)影響逆序數(shù)的值。那么現(xiàn)在我們只需要關(guān)注6的變化。6從第6位置變?yōu)榈?位置，導(dǎo)致7與8所在位置之前的逆序數(shù)量出現(xiàn)了變化。7、8都比6大，則整體逆序數(shù)量會(huì)減少2，但是逆序數(shù)-2仍然保持了奇偶性。與此同時(shí)我們可以知道，當(dāng)0縱向移動(dòng)的時(shí)候，中間的兩個(gè)數(shù)（當(dāng)前例子7、8的位置）只會(huì)有三種情況。要不都比被交換數(shù)大（比如7、8比6大）要不一個(gè)大一個(gè)小，要不都小。如果一大一小，則逆序數(shù)仍會(huì)保持不變，因?yàn)榭偭可蠒?huì)是+1-1；都小的話則逆序數(shù)會(huì)+2，奇偶性同樣不受到影響。故我們可以認(rèn)為，0的橫向與縱向移動(dòng)并不會(huì)改變逆序數(shù)的奇偶性。從而我們可以在一開始通過兩個(gè)狀態(tài)的逆序數(shù)的奇偶性來判斷是否可達(dá)。

EightPuzzles.prototype.isCanMoveToEnd = function(startNode, endNode) {
    startNode = startNode.toString().split(",")
    endNode = endNode.toString().split(",")
    if(this.calParity(startNode) === this.calParity(endNode)) {
        return true 
    } else {
        return false
    }
}
EightPuzzles.prototype.calParity = function(node) {
    var num = 0
    console.log(node)
    node.forEach(function(item, index) {
        for(var i = 0; i < index; i++) {
            if(node[i] != 0) {
                if (node[i] < item) {
                    num++
                } 
            }
        }
    })
    if(num % 2) {
        return 1
    } else {
        return 0
    }
}

EightPuzzles.prototype.solveEightPuzzles = function() {
    if(this.isCanMoveToEnd(this.startNode, this.endNode)) {
        var _ = this
        this.queue.push(this.startNode)
        this.hash[this.startNodeStr] = this.startNode
        while(!this.isFind) { 
            var currentNode = this.queue.shift(),
                currentNodeStr = currentNode.toString().split(",").join("") //二維數(shù)組變?yōu)樽址?            if(_.endNodeStr === currentNodeStr) { //找到結(jié)束狀態(tài)
                var path = []; // 用于保存路徑
                var pathLength = 0
                var resultPath = []
                for (var v = _.endNodeStr; v != _.startNodeStr; v = _.prevVertx[v]) {
                    path.push(_.hash[v]) // 頂點(diǎn)添加進(jìn)路徑
                }
                path.push(_.hash[_.startNodeStr])
                pathLength = path.length
                for(var i = 0; i < pathLength; i++) {
                    resultPath.push(path.pop())
                }
                setTimeout(function(){
                    _.showDomMove(resultPath)
                }, 500)
                _.isFind = true
                return
            }
            result = this.getChildNodes(currentNode) //獲得節(jié)點(diǎn)子節(jié)點(diǎn)
            result.forEach(function (item, i) {
                var itemStr = item.toString().split(",").join("")
                if (!_.hash[itemStr]) { //判斷是否已存在該節(jié)點(diǎn)
                    _.queue.push(item)
                    _.hash[itemStr] = item
                    _.prevVertx[itemStr] = currentNodeStr //記錄節(jié)點(diǎn)的父節(jié)點(diǎn)
                }
                
            })
        }
    } else {
        console.log("無法進(jìn)行變換得到結(jié)果")
    }
    
}

EightPuzzles.prototype.calDom = function(node) { //根據(jù)當(dāng)前狀態(tài)渲染各數(shù)字位置
    node.forEach(function(item, index) {
        item.forEach(function(obj, i) {
            $("#" + obj).css({left: i * (100+2), top: index* (100 + 2)})
        })
    })
}
EightPuzzles.prototype.showDomMove = function(path) {
    var _ = this
    path.forEach(function(item, index) { //每次狀態(tài)改變調(diào)用一次渲染函數(shù)
        setTimeout(function(node) {
            this.calDom(node)
        }.bind(_, item), index * _.timer)
    })
}

JS 中的廣度與深度優(yōu)先遍歷

八數(shù)碼問題判定是否解的證明

慣例po作者的博客，不定時(shí)更新中——

有問題歡迎在issues下交流。