張娜，王家民，陳小軍 , 竇忠發(fā)

(1.西安理工大學(xué) 機械與精密儀器工程學(xué)院，陜西 西安 710048; 2.陜西省地方電力(集團)有限公司，陜西 西安 710061; 3.中航工業(yè)618所，陜西 西安 710065)

很多場景都涉及晶體在立方體晶格中的移動問題。例如，現(xiàn)代物流業(yè)的立體倉庫，立體倉庫可以看成是一個立方體晶格，其中存放貨物的貨架相當于晶格中的晶體[1]。當滿載貨物的立體倉庫中的各個貨架上的物品需要調(diào)整時，通過貨位移動，完成位置調(diào)整，這個過程可以抽象為晶體在立方體晶格中的移動。為了降低成本并提高工作效率，晶體在立方體晶格中的移動往往通過最短路徑來實現(xiàn)[2]。

很多空間最小值問題經(jīng)過數(shù)學(xué)模型轉(zhuǎn)換，都可以轉(zhuǎn)化成一個最短路徑問題[3-7]。最短路徑問題最初是為解決交通運輸而提出的。隨著我國國民經(jīng)濟的快速發(fā)展，除交通運輸領(lǐng)域，物流倉儲、工業(yè)生產(chǎn)等基礎(chǔ)領(lǐng)域也出現(xiàn)了最短路徑問題。最短路徑問題與社會經(jīng)濟生活的聯(lián)系越來越緊密。求解最短路徑的算法主要有Dijkstra算法、A*算法、D*算法、Floyd-Warshall算法、Bellman-Ford算法、SPFA算法等[8-16]。

晶體在晶格中移動的最短路徑求解實際上是一個多源多路徑的動態(tài)環(huán)境問題，改進型的D*算法和Floyd-Warshall算法可以求解，但這兩種算法設(shè)計較為復(fù)雜，且效率不高[17-19]。本文在求解晶體在晶格中移動時，將晶格抽象成魔方結(jié)構(gòu)，通過模型轉(zhuǎn)換，將魔方結(jié)構(gòu)變成一個包含多個移動體的拓撲結(jié)構(gòu)圖，該最短路徑問題可轉(zhuǎn)化為典型最短路徑算法來解決，算法在單路徑尋找時以Dijkstra算法為基礎(chǔ)，加入當前最佳移動晶體的選擇功能及晶格結(jié)構(gòu)變化調(diào)整的操作，來完成最短多源多路徑選擇。該算法的貢獻在于通過對每次移動步數(shù)最小的晶體挑選和對晶格狀態(tài)的動態(tài)更新，使全體晶體從初始狀態(tài)逼向最終狀態(tài)為總體步數(shù)最小。

1 晶體在晶格中移動圖模型的構(gòu)建

1.1 晶體移動的規(guī)則

晶體在晶格中移動模型可以用圖1所示的魔方結(jié)構(gòu)來描述，利用各類顏色代表不同元素方位的類別，晶體在晶格中移動的過程就是使不同顏色的單元都歸在魔方的6個方向的過程。

圖1 基于魔方結(jié)構(gòu)的晶格

與魔方結(jié)構(gòu)單元的運動方式不同的是，魔方結(jié)構(gòu)的單元只能在單面將所有單元整體移動，而在晶格模型中，只要所有路經(jīng)的晶格不存在障礙晶格，每個晶體都可以在晶格中向其他相鄰晶格自由移動。由于障礙晶格直接影響了路徑選擇，而晶格中的每個晶體在移動過程中又會對其他晶體的移動產(chǎn)生影響，故每個移動晶體的起點和終點均互相交叉，晶格所走的路徑將是動態(tài)變化的，而不是固定存在的路徑。由此可見，求晶體在晶格中移動的最短路徑問題必須進行模型轉(zhuǎn)換，將動態(tài)的路徑選擇轉(zhuǎn)化為相對靜止的路徑選擇，將多源晶體的移動轉(zhuǎn)為多個單一晶體的相對移動。

1.2 晶體移動的圖模型

從圖拓撲結(jié)構(gòu)的角度看，晶格的信息可以轉(zhuǎn)化為頂點的信息和描述頂點之間關(guān)系的信息。將晶格中的每個晶體所在的位置理解為拓撲圖結(jié)構(gòu)中的一個頂點，晶體所在的位置與周圍晶體所在位置的移動關(guān)系理解為頂點之間連接關(guān)系的信息。當相鄰晶體位置不存在障礙晶格時，每個晶體與周圍的晶體存在連接關(guān)系，而當存在障礙晶格時，則不存在連接關(guān)系。由此，在多個晶格都處于運動時，每個晶體與周圍的晶體的連接關(guān)系是動態(tài)的。當晶體在圖結(jié)構(gòu)上運動后，需要立即更新頂點之間關(guān)系的信息。

典型的最短路徑算法，主要用于計算一個節(jié)點到其他所有節(jié)點的最短路徑，以起始點為中心向外層層擴展，直到擴展到終點為止。與單一物體在圖結(jié)構(gòu)上從起點經(jīng)過連續(xù)路徑到終點的移動軌跡不同，晶格中所有的晶體都需要經(jīng)過從起點到終點的路徑，每次移動的可以是當前任何一個不存在任何障礙的晶體。由此可知，最短路徑算法不僅僅要考慮選擇當前晶體走哪條路徑，而且要考慮先走哪個晶體的問題。構(gòu)造的模型如圖2所示。

圖2 晶格的網(wǎng)絡(luò)拓撲圖

圖2的模型用不同的顏色代表不同的晶體類型，所有晶體最終要運動到顏色一致的頂點，例如，“”晶體最終要到達“”頂點，其它顏色的晶體類似。

2 算法設(shè)計

2.1 數(shù)據(jù)結(jié)構(gòu)

對于一個有M個晶體、N個位置的晶格，對其數(shù)據(jù)結(jié)構(gòu)描述如下。

1) 晶格六面體的方向描述?？蓪⒘骟w的元素方位分為Us[6]={U1，U2，U3，U4，U5，U6}。每個方位都可以用圖2模型中的不同顏色來表示。

2) 頂點的描述。頂點是一個數(shù)組Vs[N]={V1，V2,…,VN}，其中的元素Vi具有屬性U，代表所屬方位，Vi·U∈{U1，U2，U3，U4，U5，U6},即頂點數(shù)組中的元素都可以歸類到其中一個方位。

3) 邊之間關(guān)系描述。任意兩個頂點之間存在路徑即為邊，邊之間的關(guān)系實際上是一個N×(N-1)的二維矩陣的計算機存儲表示問題，邊是一個二維數(shù)組Cs[N][N-1]={{V1,V2}，{V1,V3},… ,{VN,VN-1}}。二維數(shù)組Cs[N][N-1]的取值分二種情況：①由于每個頂點只可能和周圍的最多6個頂點成為鄰接頂點，當某頂點與另一頂點不是鄰接頂點時，Cs[N][N-1]的取值為0；②當某頂點與另一頂點是鄰接頂點，且二者當前的連接關(guān)系為“—”時，Cs[N][N-1]的取值為1；二者當前的連接關(guān)系為“- -”時，Cs[N][N-1]的取值為0。

4) 晶體描述。晶體集合是一個數(shù)組S[M]={S1，S2,…,SM}，其中的元素Si具有屬性U，代表所屬方位，取值為Si·U∈{U1，U2，U3，U4，U5，U6}，即晶體集合數(shù)組中的元素都可以歸類到其中一個方位。

5) 晶體位置狀態(tài)描述。令晶體位置是一個二維數(shù)組L[M][M]，其元素為，v代表頂點的信息，s代表頂點上的晶體信息。例如，某一個晶體位置狀態(tài)可以描述為L[M][M]= {{V1,S1}, {V2，S2},…,{VM，SM}}，代表M個晶體所在的位置。當對所有的晶體元素，都滿足Si·U=Vi·U條件時，該狀態(tài)就是晶體的終止位置狀態(tài)，記為E。晶體的終止位置狀態(tài)是最短路徑算法終止的條件。晶體的起始位置狀態(tài)記為B，在該狀態(tài)至少有一個晶體不滿足Si·U=Vi·U。

6) 當前位置到源點路徑的描述。晶格中每個晶體都要完成從起始頂點到終止頂點的運動路徑，對于一個具有M個晶體(M

7) 晶體在晶格中的移動路徑描述：晶體在晶格中移動的路徑集合是一個數(shù)組pathNodes[]，數(shù)組中的元素為，s代表每一步所移動的晶體信息，v代表晶體所移動到的頂點信息。

2.2 算法描述

在此提出一種晶體在晶格中移動的最短路徑算法(CMCLA)，其偽代碼描述如圖3所示。

圖3 CMCLA算法描述

CMCLA算法的基本思想為: 設(shè)置頂點集合prev[M][maxnum]并不斷地作貪心選擇來擴充這個集合，最終求出最短路徑。其中，當前晶體集合S[M]的每一個晶體都要完成從起始位置狀態(tài)到晶體終止位置狀態(tài)的路徑移動。

例如在晶體S[1]的路徑移動中，一個頂點屬于集合prev[1][j]，當且僅當從源到該頂點的最短路徑長度已知。初始時，prev[1][j]中僅含有S[1]所在的起始位置狀態(tài)。設(shè)v是晶格中的某一個頂點，把從起始頂點到v且中間只經(jīng)過prev[1][j]中頂點的路徑稱為從源到d的特殊路徑，并用數(shù)組dist[i][j]記錄當前每個頂點所對應(yīng)的最短特殊路徑長度。每次從V-prev[1][j]中取出具有最短特殊路徑長度的頂點v，將v添加到prev[1][j]中，同時對數(shù)組dist[1][j]作必要的修改。該過程持續(xù)進行直到滿足全局條件：當且僅當所有的晶體元素都有Si·U=Vi·U。其他晶體的移動與S[1]的移動的處理完全一致。

CMCLA算法通過每次移動步數(shù)最小的晶體挑選和晶格狀態(tài)的動態(tài)更新，使全體晶體從初始狀態(tài)逼向最終狀態(tài)。對于一個M個晶體、N個位置的晶格,令d為采用d路堆實現(xiàn)優(yōu)先隊列ADT，函數(shù)SelectCurrentCrystal的復(fù)雜度為(M*N)2，searchPath的時間復(fù)雜度為M*lgN，computeShortestPath的時間復(fù)雜度為M*N，主函數(shù)的時間復(fù)雜度為N*M，在最壞的條件下CMCLA算法的時間復(fù)雜度是O(N3M4*lgN* lgd(M))。CMCLA算法中變量prev[M][maxnum]、dist[M][maxnum]、Cs[N][N-1]使用的空間最大為O(N*N)，其他局部變量使用的空間O(M*N)，由此CMCLA算法的空間復(fù)雜度是O(N2)。

CMCLA算法通過每次對移動步數(shù)最小的晶體的挑選和對晶格狀態(tài)的動態(tài)更新，使全體晶體從初始狀態(tài)逼向最終狀態(tài)。算法中有以下兩點與典型的最短路徑算法不一樣。

1)M個晶體的同時移動，每個時刻只能選擇一個晶體移動，處理時首先挑選S[M]中可移動的晶體進入集合s[m]，然后從prev[M] [maxnum]中選擇s[m]中移動步數(shù)最少的晶體命名為currentCrystal，作為當前移動的晶體。

2) 每次從V-prev[i][j]中取出具有最短路徑長度的頂點u后，將u添加到prev[i][j]中，在對數(shù)組dist[i][j]作必要修改的同時，更新晶體位置狀態(tài)L[M][M]和邊之間的關(guān)系Cs[N][N-1](即當相關(guān)頂點當前的連接關(guān)系為“—”時，Cs[N][N-1]的取值為1；相關(guān)頂點當前的連接關(guān)系為“- -”時，Cs[N][N-1]的取值為0)。

3 實驗研究

通過仿真實驗驗證晶體在晶格中移動的最短路徑算法(CMCLA)?；趫D1所示魔方結(jié)構(gòu)，在進行模型轉(zhuǎn)換后，利用C語言實現(xiàn)上述算法。實驗數(shù)據(jù)分成兩組。

1) 第一組：采用立方體晶格邊分別為4(頂點數(shù)為64)、5(頂點數(shù)為125)、6(頂點數(shù)為216)和7(頂點數(shù)為343)的四種晶格為基礎(chǔ)，晶體的數(shù)量為18(最終狀態(tài)是六面體的每個方位都有3個晶體)，起始狀態(tài)為晶體在其晶格六面體每個方位的反面。

2) 第二組：以邊為7(頂點數(shù)為343)的晶格為基礎(chǔ)，晶體的數(shù)量分別為18(最終狀態(tài)是六面體的每個方位都有3個晶體)、24(最終狀態(tài)是六面體的每個方位都有4個晶體)、30(最終狀態(tài)是六面體的每個方位都有5個晶體)、36(最終狀態(tài)是六面體的每個方位都有6個晶體)四種情況，起始狀態(tài)為晶體在其晶格六面體每個方位的反面。

算法在2.8 GHZ Intel core2 CPU、帶有PAE的2G內(nèi)存和160G硬盤的PC機上運行，經(jīng)過運行，所有設(shè)定的晶格都從初始狀態(tài)到達了最終狀態(tài)，算法的運行結(jié)果如圖4和圖5所示。

圖4 最短路徑與立方體晶格頂點數(shù)量之間的關(guān)系

圖5 最短路徑與晶體數(shù)量之間的關(guān)系

圖4是晶體數(shù)量為18時，四組輸入數(shù)據(jù)狀態(tài)下的最短路徑與立方體晶格頂點數(shù)量之間的關(guān)系。圖5是立方體晶格頂點數(shù)量是343時，四組輸入數(shù)據(jù)狀態(tài)下的最短路徑與晶體數(shù)量之間的關(guān)系。從圖4可以看出，隨著立方體晶格頂點數(shù)量的增加，最短路徑的長度也增加，二者增長幅度大致相同。從圖5可以看出，隨著晶體數(shù)量的增加，最短路徑的長度也是增加的，但二者的增長幅度不一致，晶體數(shù)量增加的曲線較為平緩，但最短路徑的長度呈快速增長的趨勢。

對第二組運行數(shù)據(jù)，進一步分析晶格頂點數(shù)量是343時的四組數(shù)據(jù)中的晶體運行軌跡。四組數(shù)據(jù)從起點到終點的變化中，已完成晶體數(shù)量與移動步數(shù)之間的關(guān)系如圖6所示。

圖6 完成晶體數(shù)量與移動步數(shù)之間的關(guān)系

由圖6可以看出，對于四組輸入，算法總的趨勢是隨著時間進度的推移，完成晶體數(shù)量從0逐漸逼近了最終狀態(tài)，分別是312步完成18個晶體移動，456步完成24個晶體移動，634步完成30個晶體移動，789步完成36個晶體移動。但該過程不成線性關(guān)系，而是接近負指數(shù)函數(shù)關(guān)系，即前述少量時間完成了大部分晶體的移動，而后續(xù)大部分時間均用在少數(shù)晶體的移動。這是因為算法在后續(xù)存在路徑迂回現(xiàn)象。算法未加入啟發(fā)式規(guī)則，使得位置查找過程存在重復(fù)。這也說明了算法還有很大的改進余地。

CMCLA是一個在動態(tài)環(huán)境中解決多源多路徑問題的最短路徑算法，在本文相關(guān)工作中列出的最短路徑算法中D-Star和Floyd-Warshall算法也可以解決此類多源多路徑問題。采用C語言實現(xiàn)D-Star和Floyd-Warshall算法，并將這兩種算法及CMCLA算法以下列輸入數(shù)據(jù)在同樣的硬件機器上分別運行4次后，記錄每次的運行時間，然后取平均值，其運行完成時間的如圖7和8所示。

圖7表明，在晶體相同的條件下，對于CMCLA、D-Star和Floyd-Warshall三種算法，隨著晶格數(shù)據(jù)的增加，運行時間均呈現(xiàn)增加的趨勢，而且晶格越多，增長的幅度越大。在晶體數(shù)量相同條件下，三種算法除了在晶格頂點數(shù)量為64時，D-Star運行時間最短(這是因為D-Star算法在晶格數(shù)量比較少時，啟發(fā)式搜索使得收斂速度快)，在其他狀態(tài)下，CMCLA算法的運行時間均比D-Star和Floyd-Warshall短。這說明晶格數(shù)量較少時，CMCLA算法與D-Star算法相比無優(yōu)勢，而當晶格數(shù)量較多時，CMCLA算法具有明顯的優(yōu)勢。

圖7 晶體相同、晶格不同條件下的運行時間比較

圖8 晶體不同、晶格相同條件下的運行時間比較

從圖8可看出，在晶格相同的條件下，對于CMCLA、D-Star和Floyd-Warshall三種算法，隨著晶體數(shù)據(jù)的增加，運行時間均呈現(xiàn)增加的趨勢。三種算法中，在四種狀態(tài)下，CMCLA運行時間均比D-Star和Floyd-Warshall短。

從上述實驗可以看出，當晶體和晶格數(shù)量較少時，CMCLA無法體現(xiàn)出在運行時間上的優(yōu)勢，而當晶格的規(guī)模達到較大數(shù)量時，特別是晶體數(shù)量也較多時，CMCLA的運行效率將充分體現(xiàn)出來。這證明，在大規(guī)模晶體晶格結(jié)構(gòu)中，CMCLA算法能實現(xiàn)利用最低成本完成移動，提高工作效率、節(jié)約時間，具有重要的應(yīng)用意義。

從空間復(fù)雜度方面分析，CMCLA算法由于是在立方體模型的基礎(chǔ)上實現(xiàn)的，并且算法設(shè)計思路是尋求立方體中多源多路徑的最短路徑，而D-Star和Floyd-Warshall算法主要針對平面圖查找最短路徑，因此，CMCLA算法空間復(fù)雜度要大于D-Star和Floyd-Warshall算法空間復(fù)雜度。

從時間復(fù)雜度方面分析，由于在魔方結(jié)構(gòu)的立方體晶格中需要進行多源多路徑的最短路徑查找，使得D-Star和Floyd-Warshall實現(xiàn)時，算法設(shè)計較為復(fù)雜，運行次數(shù)和運行時間受到多源多路徑因素和算法設(shè)計自身的影響，造成算法時間復(fù)雜度的增加。而CMCLA算法自身考慮到晶體結(jié)構(gòu)，將魔方結(jié)構(gòu)變成一個包含多個移動體的拓撲結(jié)構(gòu)圖，通過對每次移動步數(shù)最小的晶體的挑選和路徑晶格狀態(tài)的動態(tài)更新，使全體晶體以總體步數(shù)最小從初始狀態(tài)逼向最終狀態(tài)，從而節(jié)約了算法的執(zhí)行時間。因此，當立方體晶格數(shù)量較少時，多源多路因素對三種算法的影響較小，三者的執(zhí)行時間較為接近。而當立方體晶格數(shù)量較大時，CMCLA算法的時間復(fù)雜度相對于D-Star和Floyd-Warshall算法的時間復(fù)雜度越來越小。

4 結(jié) 語

尋找立方體晶格中晶體移動的最短路徑與典型的最短路徑有重要區(qū)別，但通過模型轉(zhuǎn)換，它就變成了一個包括多個約束條件的典型最短路徑問題。本文在模型構(gòu)建的基礎(chǔ)上，分析并提出了基于魔方的立方體晶格中晶體移動的最短路徑算法CMCLA，算法的創(chuàng)新在于通過對每次移動步數(shù)最小的晶體挑選和對晶格狀態(tài)的動態(tài)更新，使全體晶體以總體步數(shù)最小從初始狀態(tài)逼向最終狀態(tài)。實驗結(jié)果表明，算法能有效解決晶體在立方體晶格中的移動問題，能以最低成本完成移動，提高工作效率、節(jié)約時間。

在未來的工作中，筆者將致力于以下三個方面的工作：①優(yōu)化現(xiàn)有算法，減少算法的空間復(fù)雜度；②引入智能計算思想和啟發(fā)式規(guī)則，使算法在挑選當前需移動的晶體和查找當前要移動到的位置時依據(jù)規(guī)則，有目標地縮小挑選和查找范圍，提高算法的效率；③將現(xiàn)有算法進行擴展和延伸，以解決多維數(shù)據(jù)的最短路徑查找問題。

參考文獻:

[1] 盧香清，李洪安，康寶生，等．圖最短路徑并行化及其應(yīng)用研究[J].計算機工程與應(yīng)用，2012，48(14)：38-43.

Lu Xiangqing，Li Hongan，Kang Baosheng，et al. Research on parallelization of shortest path for graph and its application[J].Computer Engineering and Applications，2012，48(14)：38-43.

[2] 楊帆，楊曉光，云美萍．考慮信號交叉口等待時間的最短路徑算法[J]．同濟大學(xué)學(xué)報:自然科學(xué)版,2013，41(5)：680-686.

Yang Fan，Yang Xiaoguang，Yun Meiping．Shortest path algorithm with a consideration of waiting time at signalized intersections[J]. Journal of Tongji University(Natural Science)，2013，41(5)：680-686.

[3] 王紅梅，胡明．基于直接/間接鄰邊概念的最短路徑算法[J]．計算機應(yīng)用，2010，30(5)：1297-1299，1303.

Wang Hongmei，Hu Ming. Shortest-path algorithm based on direct/indirect adjacent edge concept[J]．Journal of Computer Applications，2010，30(5)：1297-1299，1303.

[4] 王樹西，吳政學(xué)．改進的Dijkstra最短路徑算法及其應(yīng)用研究[J]．計算機科學(xué)，2012，39(5)：223-228.

Wang Shuxi，Wu Zhengxue. Improved dijkstra shortest path algorithm and its application[J]．Computer Science,2012,39(5)：223-228.

[5] Thouti, Krishnahari, Sathe S R．Performance analysis of single source shortest path algorithm over multiple GPUs in a network of workstations using open CL and MPI[J]．International Journal of Computer Applications, 2013, 9(77): 31-36．

[6] Jasika N, Alspahic N, Elma A, et al．Dijkstra’s shortest path algorithm serial and parallel execution performance analysis[C]//Proceedings of the 35th International Convention, MIPRO, 2012:1811-1815．

[7] Huang Yizhen, Yi Qingming, Shi Min．An improved dijkstra shortest path algorithm[C]//Proceedings of the 2nd International Conference on Computer Science and Electronics Engineering(ICCSEE 2013), 2013:26-29．

[8] 劉明周，趙志彪，凌先姣，等．基于最短路徑的復(fù)雜機械產(chǎn)品裝配過程質(zhì)量控制點公差帶在線優(yōu)化方法[J]. 機械工程學(xué)報,2012，48(10)：173-177.

Liu Mingzhou，Zhao Zhibiao，Ling Xianjiao，et al. Research on online tolerance optimization for complex mechanical products assembly process based on shortest path[J]．Chinese Journal of Mechanical Engineering, 2012，48(10)：173-177．

[9] 徐濤，鄭英，周念．物流最短路徑規(guī)劃最優(yōu)化計算方法研究[J]．物流技術(shù)，2013，32(7)：236-238，262.

Xu Tao，Zheng Ying，Zhou Nian. Study on optimal computation method of shortest logistics route[J]. Logistics Technology，2013，32(7)：236-238，262.

[10] Guerrero W J，Velasco N，Prodhon C，et al. On the generalized elementary shortest path problem: a heuristic approach[J]. Electronic Notes in Discrete Mathematics，2013,41(5):503-510.

[11] Alireza Nazemi，F(xiàn)arahnaz Omidi. An efficient dynamic model for solving the shortest path problem[J]. Transportation Research Part C：Emerging Technologies,2013，26:1-19.

[12] Keyur Rana, Mukesh Zaveri．A-star algorithm for energy efficient rounting in wireless sensor network[J]．Trends in Network and Communications, 2011, 197: 232-241．

[13] Fangfang T, Shiying Y, Xiaofeng Z, et al. Research on two-tiered A-star algorithm in game path-finding [J]. Microcomputer Applications, 2010, 1: 011.

[14] Yao Junfeng, Lin Chao, Xie Xiaobiao, et al．Path planning for virtual human motion using improved A* star algorithm[C]//2010 Seventh International Conference on Information Technology: New Generations (ITNG), 2010:12-14.

[15] Deng Yong，Chen Yuxin，Zhang Yajuan, et al. Fuzzy dijkstra algorithm for shortest path problem under uncertain environment[J]. Applied Soft Computing，2012,12(3): 1231-1237.

[16] 武蘇里，王湘桃，張陽，等．易陣游戲中兩子交換算法的研究[J]．計算機應(yīng)用與軟件，2009，26(2)：272-274.

Wu Suli，Wang Xiangtao，Zhang Yang，et al. On two-piece exchange algorithm in Yizhen game[J]．Computer Applications and Software，2009，26(2)：272-274.

[17] Garg H, Rawat P. An improved algorithm for finding all pair shortest path[J]. International Journal of Computer Applications, 2012, 47(25):35-37.

[18] 任小康，吳尚智，茍平章．基于動態(tài)狀態(tài)樹的回溯算法[J]．計算機工程與設(shè)計，2007，28(4)：755-756,759.

Ren Xiaokang, Wu Shangzhi, Gou Pingzhang . Backtracking algorithm of dynamic state space tree[J]．Computer Engineering and Design，2007，28(4)：755-756，759.

[19] 楊勇虎，李楠．平面魔方游戲中算法的設(shè)計和優(yōu)化[J]．計算機應(yīng)用與軟件，2010，27(8)：273-275.

Yang Yonghu，Li Nan. Designing and optimising algorithm for plane magic cube game[J]．Computer Applications and Software，2010，27(8)：273-275.