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

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

歡迎關(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ù)字所需要的動畫時間
}
var eightPuzzles = new EightPuzzles(option)

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

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

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

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

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

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

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

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

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

在頁面中通過動畫路徑生成動畫。

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

初始節(jié)點壓入隊。

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

出隊，訪問節(jié)點。

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

重復3，4步驟，即可得解。

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

通過路徑生成動畫

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

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

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

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

這個變換只需要一步，即0向左與8進行交換。那么對于逆序數(shù)而言，0所在的位置是無關(guān)緊要的，因為它比誰都小，不會導致位置變化逆序數(shù)改變。所以0的橫向移動不會改變逆序數(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

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

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]) // 頂點添加進路徑
                }
                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é)點子節(jié)點
            result.forEach(function (item, i) {
                var itemStr = item.toString().split(",").join("")
                if (!_.hash[itemStr]) { //判斷是否已存在該節(jié)點
                    _.queue.push(item)
                    _.hash[itemStr] = item
                    _.prevVertx[itemStr] = currentNodeStr //記錄節(jié)點的父節(jié)點
                }
                
            })
        }
    } else {
        console.log("無法進行變換得到結(jié)果")
    }
    
}

EightPuzzles.prototype.calDom = function(node) { //根據(jù)當前狀態(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作者的博客，不定時更新中——

有問題歡迎在issues下交流。