八數碼問題
摘要：近日來，人工智慧成為科技領域搜尋熱詞，無論是從人機大戰的新聞來看，還是從新提出的深度學習理論來分析，我們可以可以清晰的預見，人工智慧即將騰飛。
人工智慧，顧名思義，就是模擬人類思考模式的超級算法系統，學習能力和推理能力是其核心內容。舉個簡單的例子，“機器學習（MachineLearning）”就是人工智慧領域裡很有前途的課題，其主要內容是利用大資料訓練程式，讓它們找到一些可遵循的規律，並且讓程式本身大膽的預測結果。在這個過程中搜索策略變的尤為關鍵。本文主要論述計算機科學與技術專業大三下專業課《人工智慧》第二個實驗演算法。
關鍵字：人工智慧，搜尋問題，啟發式搜尋
Eight digital problem
Abstract： in recent days， the artificial intelligence search words become areas of science and technology， whether from the point of man-machine war news， or the depth of the new proposed learning theory to the analysis， we can clearly foresee， artificial intelligence is about to take off。
Artificial intelligence， as the name implies， is to simulate human thinking mode of super algorithm system， learning ability and reasoning ability is the core content。 A simple example， the “machine learning （MachineLearning）” is the field of artificial intelligence is a promising subject， its main content is to use big data training program， let them find some follow rules， and make bold prediction to the program itself。 In the process of the search strategy is particularly critical。 This paper mainly discusses the computer science and technology under the junior in professional course “artificial intelligence”。
Keywords： artificial intelligence， search problems， heuristic search
1，問題重述
3×3九宮棋盤，放置數碼為1 -8的8個棋牌，剩下一個空格，只能透過棋牌向空格的移動來改變棋盤的佈局。
要求：根據給定初始佈局（即初始狀態）和目標佈局（即目標狀態），如何移動棋牌才能從初始佈局到達目標佈局，找到合法的走步序列。
2，問題分析
對於八數碼問題的解決，首先要考慮是否有答案。每一個狀態可認為是一個1×9的矩陣，問題即透過矩陣的變換，是否可以變換為目標狀態對應的矩陣？由數學知識可知，可計算這兩個有序數列的逆序值，如果兩者都是偶數或奇數，則可透過變換到達，否則，這兩個狀態不可達。這樣，就可以在具體解決問題之前判斷出問題是否可解，從而可以避免不必要的搜尋。
如果初始狀態可以到達目標狀態，那麼採取什麼樣的方法呢？
常用的狀態空間搜尋有深度優先和廣度優先。廣度優先是從初始狀態一層一層向下找，直到找到目標為止。深度優先是按照一定的順序前查詢完一個分支，再查詢另一個分支，以至找到目標為止。廣度和深度優先搜尋有一個很大的缺陷就是他們都是在一個給定的狀態空間中窮舉。這在狀態空間不大的情況下是很合適的演算法，可是當狀態空間十分大，且不預測的情況下就不可取了。他的效率實在太低，甚至不可完成。由於八數碼問題狀態空間共有9！個狀態，對於八數碼問題如果選定了初始狀態和目標狀態，有9！/2個狀態要搜尋，考慮到時間和空間的限制，在這裡採用A*演算法作為搜尋策略。在這裡就要用到啟發式搜尋
啟發式搜尋就是在狀態空間中的搜尋對每一個搜尋的位置進行評估，得到最好的位置，再從這個位置進行搜尋直到目標。這樣可以省略大量無畏的搜尋路徑，提到了效率。在啟發式搜尋中，對位置的估價是十分重要的。採用了不同的估價可以有不同的效果。
啟發中的估價是用估價函式表示的，如：f（n） = g（n） +h（n）其中f（n） 是節點n的估價函式，g（n）是在狀態空間中從初始節點到n節點的實際代價，h（n）是從n到目標節點最佳路徑的估計代價。 在此八數碼問題中，顯然g（n）就是從初始狀態變換到當前狀態所移動的步數，估計函式f（n）我們就可採用當前狀態各個數字牌不在目標狀態未知的個數，即錯位數。
2。1使用寬度優先搜尋方法解決該問題
為問題狀態的表示建立資料結構：
（1）3×3的一個矩陣，矩陣元素S ij∈{0，1，…，8}；其中1≤i，j≤3，
（2）數字0指示空格，
（3）數字1 - 8指示相應棋牌。
（4）制定操作運算元集：
直觀方法——為每個棋牌制定一套可能的走步：左、上、右、下四種移動。這樣就需32個操作運算元。
簡易方法——僅為空格制定這4種走步，因為只有緊靠空格的棋牌才能移動。
空格移動的唯一約束是不能移出棋盤。
2。2使用深度優先搜尋解決該問題
首先擴充套件最新產生的（即最深的）節點。防止搜尋過程沿著無益的路徑擴充套件下去，往往給出一個節點擴充套件的最大深度——深度界限。與寬度優先搜尋演算法最根本的不同在於：將擴充套件的後繼節點放在OPEN表的前端。
2。3使用啟發式搜尋
特點：重排OPEN表，選擇最有希望的節點加以擴充套件
種類：有序搜尋（A演算法）、A*演算法等
用來加速搜尋過程的有關問題領域的特徵資訊。包括：
用於決定要擴充套件的下一個節點的資訊；
在擴充套件一個節點時，用於決定要生成哪一個或哪幾個後繼節點的資訊；
用於決定某些應該從搜尋樹中拋棄或修剪的節點的資訊；
使用啟發式資訊指導的搜尋過程稱為啟發式搜尋。
用來估算節點處於最佳求解路徑上的希望程度的函式f（n） = g（n） + h（n）
n ——搜尋圖中的某個當前被擴充套件的節點；
f（n） ——從初始狀態節點s， 經由節點n到達目標節點ng，估計的最小路徑代價；
g（n） ——從s到n 的實際路徑代價；
h（n）——從n到ng，估計的最小路徑代價。
估價函式：f（n）=d（n）+w（n）
其中：d（n）為n的深度 w（n）為不在位的棋子數
3，求解過程
不管哪種搜尋，都統一用這樣的形式表示：搜尋的物件是一個圖，它面向一個問題，不一定有明確的儲存形式，但它裡面的一個結點都有可能是一個解（可行解），搜尋的目的有兩個方面，或者求可行解，或者從可行解集中求最優解。
搜尋演算法可分為兩大類：無資訊的搜尋演算法和有資訊的搜尋演算法。無資訊的搜尋又稱盲目搜尋，其特點是隻要問題狀態可以形式化表示，原則上就可用使用無資訊的搜尋，無資訊搜尋有如下常見的幾種搜尋策略：廣度優先搜尋、代價一致搜尋、深度優先搜尋、深度有限搜尋、迭代深入優先搜尋、雙向搜尋。我們說DFS和BFS都是蠻力搜尋，因為它們在搜尋到一個結點時，在展開它的後續結點時，是對它們沒有任何‘認識’的，它認為它的孩子們都是一樣的‘優秀’，但事實並非如此，後續結點是有好有壞的。好，就是說它離目標結點‘近’，如果優先處理它，就會更快的找到目標結點，從而整體上提高搜尋效能。
為了改善上面的演算法，我們需要對展開後續結點時對子結點有所瞭解，這裡需要一個估值函式，估值函式就是評價函式，它用來評價子結點的好壞，因為準確評價是不可能的，所以稱為估值。這就是我們所謂的有資訊搜尋。如果估值函式只考慮結點的某種效能上的價值，而不考慮深度，比較有名的就是有序搜尋（Ordered-Search），它著重看好能否找出解，而不看解離起始結點的距離（深度）。如果估值函式考慮了深度，或者是帶權距離（從起始結點到目標結點的距離加權和），那就是A*如果不考慮深度，就是說不要求最少步數，移動一步就相當於向後多展開一層結點，深度多算一層，如果要求最少步數，那就需要用A*。簡單的來說A*就是將估值函式分成兩個部分，一個部分是路徑價值，另一個部分是一般性啟發價值，合在一起算估整個結點的價值，
考慮到八數碼問題的特點，在本實驗中使用A*演算法求解。A*搜尋是一種效的搜尋演算法，它把到達節點的耗散g（n）和從該節點到目標節點的消耗h（n）結合起來對節點進行評價：f（n）=g（n）+h（n）。當h（n）是可採納時，使用Tree-Search的A*演算法將是最優的。
A*演算法，1 在GRAPHSEARCH過程中，如果第8步的重排OPEN表是依據f（n）=g（n）+h（n）進行的，則稱該過程為A演算法。在A演算法中，如果對所有的n存在h（n）≤h*（n），則稱h（n）為h*（n）的下界，它表示某種偏於保守的估計。採用h*（n）的下界h（n）為啟發函式的A演算法，稱為A*演算法。當h=0時，A*演算法就變為有序搜尋演算法。
在A演算法中，如果滿足條件：
（1） g（n）是對g*（n）的估計，且g（n）>0；
（2） h（n）是h*（n）的下界，即對任意節點n均有0≤h（n）≤h*（n）則A演算法稱為A*演算法
A*演算法的可納性，對任一個圖，存在從S到目標的路徑，如果一個搜尋演算法總是結束在一條從S到目標的最佳路徑上，則稱此演算法是可採納的。演算法A*保證只要最短路徑存在，就一定能找出這條路徑，所以演算法A*是可納的。
估價函式：f（n）=d（n）+w（n）
其中：d（n）為n的深度 w（n）為不在位的棋子數
取h（n）=w（n），則有w（n）≤h*（n），h（n）滿足A*演算法的限制條件。
在八數碼難題中， 令估價函式
f（n）=d（n）+p（n）
啟發函式h（n）=p（n），p（n）為不在位的棋子與其目標位置的距離之和，則有p（n）≤h*（n），滿足A*演算法的限制條件。
w（n）——不在位的棋子數，不夠貼切，錯誤選用節點加以擴充套件。
更接近於h*（n）的h（n），其值是節點n與目標狀態節點相比較，每個錯位棋子在假設不受阻攔的情況下，移動到目標狀態相應位置所需走步的總和。（n）比w（n）更接近於h*（n），因為p（n）不僅考慮了錯位因素，還考慮了錯位的距離（移動次數）。
說明h值越大，啟發功能越強， 搜尋效率越高。特別地
（1）h（n）=h*（n）
搜尋僅沿最佳路徑進行， 效率最高。
（2）h（n）=0
無啟發資訊， 盲目搜尋， 效率低。
（3）h（n）>h*（n）
是一般的A演算法，效率高， 但不能保證找到最佳路徑。 有時為求解難題取h（n）>h*（n）， 以提高效率。
4，程式設計
#include
#include
#include
using
namespace
std
；
class
EightPuzzle
{
private
：
int
num
［
9
］；
int
malposition
；
int
depth
；
int
evaluation
；
public
：
EightPuzzle
*
parent
；
EightPuzzle
*
leaf_last
；
EightPuzzle
*
leaf_next
；
public
：
EightPuzzle
（
int
*
num_input
）；
void
init
（
int
*
target
）；
void
setNum
（
int
num
［］）；
int
*
getNum
（）；
void
getNum
（
int
*
num
）；
int
getMalposition
（）
{
return
this
->
malposition
；
}
int
getDepth
（）
{
return
this
->
depth
；
}
int
getEvaluation
（）
{
return
this
->
evaluation
；
}
void
（）；
bool
solvable
（
int
*
target
）；
bool
find_target
（
int
*
target
）；
EightPuzzle
&
operator
=
（
EightPuzzle
&
eightPuzzle
）；
EightPuzzle
&
operator
=
（
int
other_num
［
9
］）；
bool
operator
==
（
EightPuzzle
&
eigthPuzzle
）；
bool
operator
==
（
int
other_num
［
9
］）；
}；
EightPuzzle
：：
EightPuzzle
（
int
*
num_input
）
{
int
ii
；
for
（
ii
=
0
；
ii
<
9
；
ii
++
）
{
num
［
ii
］
=
num_input
［
ii
］；
}
this
->
leaf_last
=
NULL
；
this
->
leaf_next
=
NULL
；
this
->
parent
=
NULL
；
}
EightPuzzle
&
EightPuzzle
：：
operator
=
（
EightPuzzle
&
eightPuzzle
）
{
int
ii
；
for
（
ii
=
0
；
ii
<
9
；
ii
++
）
{
this
->
num
［
ii
］
=
eightPuzzle
。
getNum
（）［
ii
］；
}
this
->
malposition
=
eightPuzzle
。
getMalposition
（）；
this
->
depth
=
eightPuzzle
。
getDepth
（）
+
1
；
this
->
evaluation
=
this
->
malposition
+
this
->
depth
；
return
*
this
；
}
EightPuzzle
&
EightPuzzle
：：
operator
=
（
int
other_num
［
9
］）
{
int
ii
；
for
（
ii
=
0
；
ii
<
9
；
ii
++
）
{
num
［
ii
］
=
other_num
［
ii
］；
}
return
*
this
；
}
bool
EightPuzzle
：：
operator
==
（
EightPuzzle
&
eightPuzzle
）
{
int
match
=
1
；
int
ii
；
for
（
ii
=
0
；
ii
<
9
；
ii
++
）
{
if
（
this
->
num
［
ii
］
！=
eightPuzzle
。
getNum
（）［
ii
］）
{
match
=
0
；
break
；
}
}
if
（
match
==
0
）
return
false
；
else
return
true
；
}
bool
EightPuzzle
：：
operator
==
（
int
other_num
［
9
］）
{
int
match
=
1
；
int
ii
；
for
（
ii
=
0
；
ii
<
9
；
ii
++
）
{
if
（
this
->
num
［
ii
］
！=
other_num
［
ii
］）
{
match
=
0
；
break
；
}
}
if
（
match
==
0
）
return
false
；
else
return
true
；
}
void
EightPuzzle
：：
init
（
int
*
target
）
{
int
ii
；
int
temp
=
0
；
for
（
ii
=
0
；
ii
<
9
；
ii
++
）
{
if
（
num
［
ii
］
！=
target
［
ii
］）
{
temp
++
；
}
}
this
->
malposition
=
temp
；
if
（
this
->
parent
==
NULL
）
{
this
->
depth
=
0
；
}
else
{
this
->
depth
=
this
->
parent
->
depth
+
1
；
}
this
->
evaluation
=
this
->
malposition
+
this
->
depth
；
}
void
EightPuzzle
：：
setNum
（
int
num
［］）
{
int
ii
；
for
（
ii
=
0
；
ii
<
9
；
ii
++
）
{
this
->
num
［
ii
］
=
num
［
ii
］；
}
}
int
*
EightPuzzle
：：
getNum
（）
{
return
this
->
num
；
}
void
EightPuzzle
：：
getNum
（
int
*
num
）
{
int
ii
；
for
（
ii
=
0
；
ii
<
9
；
ii
++
）
{
num
［
ii
］
=
this
->
num
［
ii
］；
}
}
bool
EightPuzzle
：：
solvable
（
int
*
target
）
{
int
ii
，
ij
；
int
count_num
=
0
，
count_target
=
0
；
for
（
ii
=
0
；
ii
<
9
；
ii
++
）
{
for
（
ij
=
0
；
ij
<
ii
；
ij
++
）
{
if
（（
this
->
num
［
ij
］
<
this
->
num
［
ii
］）
&&
（
this
->
num
［
ij
］
！=
0
））
{
count_num
++
；
}
if
（
target
［
ij
］
<
target
［
ii
］
&&
target
［
ij
］
！=
0
）
{
count_target
++
；
}
}
}
if
（（
count_num
+
count_target
）
%
2
==
0
）
{
return
true
；
}
else
{
return
false
；
}
}
bool
EightPuzzle
：：
find_target
（
int
*
target
）
{
int
ii
；
for
（
ii
=
0
；
ii
<
9
；
ii
++
）
{
if
（
this
->
num
［
ii
］
！=
target
［
ii
］）
{
break
；
}
}
if
（
ii
==
9
）
{
return
true
；
}
else
{
return
false
；
}
}
bool
move_up
（
int
*
num
）
{
int
ii
；
for
（
ii
=
0
；
ii
<
9
；
ii
++
）
{
if
（
num
［
ii
］
==
0
）
{
break
；
}
}
if
（
ii
<
3
）
{
return
false
；
}
else
{
num
［
ii
］
=
num
［
ii
-
3
］；
num
［
ii
-
3
］
=
0
；
}
return
true
；
}
bool
move_down
（
int
*
num
）
{
int
ii
；
for
（
ii
=
0
；
ii
<
9
；
ii
++
）
{
if
（
num
［
ii
］
==
0
）
{
break
；
}
}
if
（
ii
>
5
）
{
return
0
；
}
else
{
num
［
ii
］
=
num
［
ii
+
3
］；
num
［
ii
+
3
］
=
0
；
}
return
true
；
}
bool
move_left
（
int
*
num
）
{
int
ii
；
for
（
ii
=
0
；
ii
<
9
；
ii
++
）
{
if
（
num
［
ii
］
==
0
）
{
break
；
}
}
if
（
ii
==
0
||
ii
==
3
||
ii
==
6
）
{
return
false
；
}
else
{
num
［
ii
］
=
num
［
ii
-
1
］；
num
［
ii
-
1
］
=
0
；
}
return
true
；
}
bool
move_right
（
int
*
num
）
{
int
ii
；
for
（
ii
=
0
；
ii
<
9
；
ii
++
）
{
if
（
num
［
ii
］
==
0
）
{
break
；
}
}
if
（
ii
==
2
||
ii
==
5
||
ii
==
8
）
{
return
false
；
}
else
{
num
［
ii
］
=
num
［
ii
+
1
］；
num
［
ii
+
1
］
=
0
；
}
return
true
；
}
void
EightPuzzle
：：
（）
{
int
ii
；
for
（
ii
=
0
；
ii
<
9
；
ii
++
）
{
if
（（
ii
+
1
）
%
3
！=
0
）
{
cout
<<
num
［
ii
］
<<
“，”
；
}
else
{
cout
<<
num
［
ii
］
<<
endl
；
}
}
}
bool
existed
（
int
*
num
，
EightPuzzle
*
start
）
{
EightPuzzle
*
temp
；
for
（
temp
=
start
；
temp
！=
NULL
；
temp
=
temp
->
parent
）
{
if
（
*
temp
==
num
）
{
return
true
；
}
}
return
false
；
}
EightPuzzle
*
best_route
（
EightPuzzle
*
start
，
EightPuzzle
*
target
）
{
EightPuzzle
*
temp
，
*
best
；
temp
=
best
=
start
；
start
->
init
（
target
->
getNum
（））；
int
min
=
start
->
getEvaluation
（）；
for
（
temp
=
start
；
temp
！=
NULL
；
temp
=
temp
->
leaf_next
）
{
if
（
min
>
temp
->
getEvaluation
（））
{
best
=
temp
；
min
=
temp
->
getEvaluation
（）；
}
}
return
best
；
}
void
print_route
（
EightPuzzle
*
best
，
int
list_length
）
{
int
step
=
0
；
EightPuzzle
*
temp
；
for
（
temp
=
best
->
parent
；
temp
！=
NULL
；
temp
=
temp
->
parent
）
{
cout
<<
endl
；
temp
->
（）；
step
++
；
}
cout
<<
endl
<<
“The total steps is ”
<<
step
<<
“。”
<<
endl
；
cout
<<
endl
<<
“The memory cost is ”
<<
list_length
<<
“。”
<<
endl
；
return
；
}
void
proceeding
（
EightPuzzle
&
start
，
EightPuzzle
&
target
）
{
if
（
！
start
。
solvable
（
target
。
getNum
（）））
{
cout
<<
endl
<<
“The serious number you input can‘t be solvable！”
<<
endl
；
return
；
}
EightPuzzle
*
best
=
&
start
；
EightPuzzle
*
list
=
&
start
；
EightPuzzle
*
apply
，
*
temp
；
int
num
［
9
］，
list_length
=
0
；
while
（
best
！=
NULL
）
{
best
=
best_route
（
list
，
&
target
）；
if
（
best
->
find_target
（
target
。
getNum
（）））
{
print_route
（
best
，
list_length
）；
return
；
}
temp
=
best
->
leaf_last
；
best
->
getNum
（
num
）；
if
（
move_up
（
num
）
&&
！
existed
（
num
，
best
））
{
apply
=
new
EightPuzzle
（
num
）；
apply
->
parent
=
best
；
apply
->
init
（
target
。
getNum
（））；
apply
->
leaf_last
=
temp
；
if
（
temp
==
NULL
）
{
list
=
apply
；
}
else
{
temp
->
leaf_next
=
apply
；
}
temp
=
apply
；
list_length
++
；
}
best
->
getNum
（
num
）；
if
（
move_down
（
num
）
&&
！
existed
（
num
，
best
））
{
apply
=
new
EightPuzzle
（
num
）；
apply
->
parent
=
best
；
apply
->
init
（
target
。
getNum
（））；
apply
->
leaf_last
=
temp
；
if
（
temp
==
NULL
）
{
list
=
apply
；
}
else
{
temp
->
leaf_next
=
apply
；
}
temp
=
apply
；
list_length
++
；
}
best
->
getNum
（
num
）；
if
（
move_left
（
num
）
&&
！
existed
（
num
，
best
））
{
apply
=
new
EightPuzzle
（
num
）；
apply
->
parent
=
best
；
apply
->
init
（
target
。
getNum
（））；
apply
->
leaf_last
=
temp
；
if
（
temp
==
NULL
）
{
list
=
apply
；
}
else
{
temp
->
leaf_next
=
apply
；
}
temp
=
apply
；
list_length
++
；
}
best
->
getNum
（
num
）；
if
（
move_right
（
num
）
&&
！
existed
（
num
，
best
））
{
apply
=
new
EightPuzzle
（
num
）；
apply
->
parent
=
best
；
apply
->
init
（
target
。
getNum
（））；
apply
->
leaf_last
=
temp
；
if
（
temp
==
NULL
）
{
list
=
apply
；
}
else
{
temp
->
leaf_next
=
apply
；
}
temp
=
apply
；
list_length
++
；
}
temp
->
leaf_next
=
best
->
leaf_next
；
if
（
best
->
leaf_next
！=
NULL
）
{
best
->
leaf_next
->
leaf_last
=
temp
；
}
best
->
leaf_next
=
best
->
leaf_last
=
NULL
；
}
}
void
input
（
int
num_init
［］）
{
int
ii
，
ij
；
cout
<<
“Please input the initial state of the eight puzzle：”
<<
endl
；
cout
<<
“（0 for the blank）”
<<
endl
<<
endl
；
for
（
ii
=
0
；
ii
<
9
；
ii
++
）
{
cin
>>
num_init
［
ii
］；
if
（
num_init
［
ii
］
<
0
||
num_init
［
ii
］
>
8
）
{
cout
<<
“Wrong number！ Please input again：（0-8）”
<<
endl
；
ii
——
；
}
for
（
ij
=
0
；
ij
<
ii
；
ij
++
）
{
if
（
num_init
［
ii
］
==
num_init
［
ij
］）
{
cout
<<
“The number you inputed is duplicated！ Try again：”
<<
endl
；
ii
——
；
}
}
}
}
int
main
（
int
argc
，
char
**
argv
）
{
double
time
；
clock_t
START
，
FINISH
；
int
num_init
［
9
］；
input
（
num_init
）；
EightPuzzle
*
start
=
new
EightPuzzle
（
num_init
）；
int
num_target
［
9
］
=
{
1
，
2
，
3
，
8
，
0
，
4
，
7
，
6
，
5
}；
EightPuzzle
*
target
=
new
EightPuzzle
（
num_target
）；
cout
<<
“The initial serial number is：”
<<
endl
；
start
->
（）；
cout
<<
“The target serial number is：”
<<
endl
；
target
->
（）；
START
=
clock
（）；
proceeding
（
*
start
，
*
target
）；
FINISH
=
clock
（）；
time
=
（
double
）（
FINISH
-
START
）
*
1000
/
CLOCKS_PER_SEC
；
cout
<<
endl
<<
“The total time cost to solve the puzzle is： ”
；
cout
<<
time
<<
“ millisecond。”
<<
endl
<<
endl
；
system
（
“pause”
）；
return
0
；
}
//
216408753
->
18
steps
