A*算法實現8數或者15數問題（C＃實現）
2024-07-21 02:18:36
供稿：網友
注冊會員，創建你的web開發資料庫，－、問題描述
8數或15數問題是同一個問題，其就是一個隨機排列的8個或15個數在一個方正格子中移動到達規定的一個目標狀態。由于只有一個空格子，故只有在空格附近的棋子可以移動。
二、算法描述
f 算法選擇
此問題需要對所有可能的路徑進行窮舉，但是由于隨著樹的高度的加大，其子結點的增加宿舍劇增，所以對所有的子結點進行窮舉是不大現實的。而根據當前的狀態和目標狀態進行對比可以用一個評估函數來評估當前狀態的好壞情況。而在這里我們選擇a*算法來進行求解，a*算法是一種最好優先的算法。f'(n) = g'(n) + h'(n)，f'(n)是估價函數，g'(n)是起點到終點的最短路徑值，這里就表示樹的高度，h'(n)是n到目標的最斷路經的啟發值，其原理是把當前產生的狀態和以前所以的狀態的評估函數值進行對比，選擇其中最小的評估函數繼續進行下一步。這里我選擇h'(n)的啟發值為每個格子到達它的目標位置所需要經過的最少步數。
f 算法描述
需要說明的幾點：
1. 用openarr表示初始節點列表(待擴展，此為一個動態數組)
2．closedarr保存已經訪問過的結點
3．算法首先需要給出初始狀態，由于隨機產生的狀態并不一定能夠走到目標狀態，因此這里采用從標準狀態往回走產生一個被打亂的隨機狀態，這樣可以保證有解。
算法實現：
1. openarr放置初始結點
2. 如果openarr為空集，則退出并給出失敗信號
3. n取為openarr的第一個節點，并從openarr中刪除節點n
4. 如果n為目標節點，則退出并給出成功信號
5. 否則，將產生n子節點，并對n的每個子結點n’ 進行如下操作：
1）如果n’ 不在openarr和closedarr表中，則把n’放入openarr表中
2）否則，如果在openarr表中，計算評估值，并且如果比表中的評估函數的值小，則更新表中的評估值為當前的值。
3）否則，如果在closedarr表中，計算評估值，并且如果比表中的評估函數的值小，則把表中的評估值更新為當前的值，并把該結點從表中刪除，并在openarr表中加入該結點。
6、把n結點加入closedarr中
7、對openarr進行排序（根據評估函數從小到大），并轉到2。
三、程序設計
算法使用c＃語言來實現的。程序主要根據上面提供的廣度優先算法的描述來對算法進行實現的。程序共有四個類：
stepnode類，用來描述產生的各個結點的屬性以及方法等
heuristic_15num_search類，算法實現類
form1類，是界面設計的類。
這里分別提供了8數和15數問題的求解。并顯示了所經歷過的各個狀態轉移
以下主要對幾個核心算法的程序實現進行說明介紹。
//stepnode類 以下幾個方法主要是控制格子的左右上下的移動
//0 數字上移
private void moveup(position p)
{
if(p.x>=1)
{
stepnode node = new stepnode();
to(this,node);
position p1 = new position(p.x-1,p.y);
addchild(node,p,p1);
}
}
// 0 數字下移
private void movedown(position p)
{
if(p.x<=text_v.length-2)
{
stepnode node = new stepnode();
to(this,node);
position p1 = new position(p.x+1,p.y);
addchild(node,p,p1);
}
}
//0 數字左移
private void moveleft(position p)
{
if(p.y>=1)
{
stepnode node = new stepnode();
to(this,node);
position p1 = new position(p.x,p.y-1);
addchild(node,p,p1);
}
}
//0 數字右移
private void moveright(position p)
{
if(p.y<=text_v.length-2)
{
stepnode node = new stepnode();
to(this,node);
position p1 = new position(p.x,p.y+1);
addchild(node,p,p1);
}
}
//計算節點的啟發函數的值
private void computegeuristicgeneval()
{
int geneval = this.height ;
int g = 0; //啟發因子 每個數據到達標準位置需要走過的最少步數
for(int i=0;i<text_v.length;i++)
{
for(int j=0;j<text_v[0].length;j++)
{
position p1 = getposition(text_v[i][j]);
position p2 = getposition(aim[i,j]);
int xd = p1.x > p2.x ? p1.x - p2.x : p2.x - p1.x ;
int yd = p1.y > p2.y ? p1.y - p2.y : p2.y - p1.y ;
g += xd + yd ;
}
}
geneval += g;
this.heuristic_gene = geneval;
}
//heuristic_15num_search類
//核心算法實現部分
//循環搜索匹配
private void loopsearch(stepnode node)
{
while(openarr.count>0)
{
node = (stepnode)openarr[0];
openarr.remove(node);
//如果是目標節點則停止搜索
if(node.isaim())
{
setpath(node);
return;
}
else
{
//產生子節點。
node.createchildren();
//對每個子節點進行檢查
foreach(stepnode i in node.children)
{
//如果不在open和close表中。
if( contain(closedarr,i)==-1 && contain(openarr,i)==-1 )
{
openarr.add(i);
}
//如果在open表中
else if(contain(openarr,i)!=-1)
{
stepnode n = (stepnode)openarr[contain(openarr,i)];
//如果i的估計值小于open表中的估計值則替換表中的估計值
if(i.heuristic_gene<n.heuristic_gene)
{
n.heuristic_gene = i.heuristic_gene;
}
}
//如果在close中。
else
{
stepnode n = (stepnode)closedarr[contain(closedarr,i)];
//如果i的估計值小于closed表中的估計值則替換表中的估計值
if(i.heuristic_gene<n.heuristic_gene)
{
n.heuristic_gene = i.heuristic_gene;
closedarr.removeat(contain(openarr,i));
openarr.add(n);
}
}
}
//節點加入closed表中 表示已經訪問過了。
closedarr.add(node);
//對節點進行排序
openarr.sort(new mycomparer());
}
}
//理論上不可能出現這種情況
path = "not found @!";
return;
}
四、試驗結果
1）8數問題搜索路徑如下圖
generate 是用來隨機產生一個初始狀態（46） 表示從標準狀態見過隨機的46步后產生的一個隨機的初始狀態。這里46是一個隨機數，由于該數越大離目標越遠，搜索越復雜故將此隨機數控制在0－100之間。3表示3的方正即8數問題，4表示4的方正即表示15數問題。
2）15數問題搜索路徑如下圖
從以上結果來看，由于使用了啟發式的搜索過程，因此大大加快的搜索的速度以及能盡可能經過最少的路徑最快到達目標狀態，由于8數問題比較簡單因此搜索速度較快，而15數問題復雜度加大，當隨機產生的數接近100的時候搜索的時間迅速變慢，故算法還待改進，主要是因為隨著深度的加深，openarr和closearr表中的數據迅速擴大，故可以考慮把openarr表中的狀態數進行選擇性的排除一些，比如每次把openarr中表的數據經過排序后可以刪除最后的幾個最差的狀態，這樣在一定程度上提高了速度但是也減低了找到最優解的幾率不過這種減低是非常小的，因為被排除的已經是最差的情況了。
