a演算法解決八數碼問題

『壹』 求8數碼A或A*演算法（用C語言）

//dfs+hash+記憶化 爐灰出品
#include "stdio.h"
#define N 4
#define swap(a,b) a=a+b;b=a-b;a=a-b;
int map[N][N]/*={{0,0,0,0},{0,1,2,3},{0,8,0,4},{0,7,6,5}}*/,hashta[99991]={0},path[2000]={0},min=150,book[N][N]={0},H=0,step=0,choos[5]={0},len=0;

int hash(int x,int y,int temp[N][N])
{ int i=0,j=0,k=1,sum=0;
for(i=1;i<N;i++)
{ for(j=1;j<N;j++)
{ sum=sum*x+temp[i][j]*k-2;
k*=(y+4);
}
}
return sum;
}
void dfs(int x,int y)
{ int i=0,j=0,k=0,p=0,mark=0,temp=0,h=0;
h=hash(x,y,book)%99991;
if(step>min) return;
if(h==H)
{ if( step<min )
{ min=step;
//printf("%d\n",min);
//getch();
}
hashta[h]++;
return ;
}
if( hashta[h]!=0 ) {return ;}
hashta[h]=1;
if(x-1>0)
{ step++;
swap(book[x-1][y],book[x][y])
dfs(x-1,y);
swap(book[x-1][y],book[x][y])
step--;
}
if(x+1<N)
{ step++;
swap(book[x+1][y],book[x][y])
dfs(x+1,y);
swap(book[x+1][y],book[x][y])
step--;
}
if(y-1>0)
{ step++;
swap(book[x][y-1],book[x][y])
dfs(x,y-1);
swap(book[x][y-1],book[x][y])
step--;
}
if(y+1<N)
{ step++;
swap(book[x][y+1],book[x][y])
dfs(x,y+1);
swap(book[x][y+1],book[x][y])
step--;
}
hashta[h]=0;
}
int main(void)
{ int i=0,j=0,mark=0,k=0,p=0,x=0,y=0;
freopen("八數碼.in","r",stdin);
freopen("八數碼.out","w",stdout);
for(i=1;i<N;i++)
{ for(j=1;j<N;j++)
{ scanf("%d",&map[i][j]);
}
}
for(i=1;i<N;i++)
{ for(j=1;j<N;j++)
{ scanf("%d",&book[i][j]);
if(book[i][j]==0) {x=i;y=j;}
}
}
H=hash(2,2,map)%99991;
dfs(x,y);
if(hashta[H]!=0) printf("%d\n",min);
else printf("-1\n");
return 0;
}
因為原程序和此題稍有不同而臨時修改，所以可能還有點問題。 qiji8816你自己再看看吧，反正修改前是可以運行的。^_^

『貳』 求課設代碼

基於A演算法求解八數碼問題是一種規劃問題，即用有限步驟把初始狀態轉換成目標狀態的過程。A演算法是一種帶有啟發式函數的搜索演算法，用於通過估價函數指導搜索，提高搜索效率。
為了實現上述功能，需要定義若干個變數和函數，如下所示：
定義變數：
init_state：初始狀態，即八數碼問題的初始排列；
goal_state：目標狀態，即八數碼問題的最終排列；
f_score：估價函數值，即啟發函數和實際代價之和；
g_score：實際代價，即當前狀態到起始狀態的實際步數；
h_score：啟發函數值，即當前狀態到目標狀態的估計步數。
定義函數：
get_successor_states()：用於獲取當前狀態的所有後繼狀態；
get_heuristic_value()：用於計算當前狀態到目標狀態的估計步數，即啟發函數值；
get_g_value()：用於計算當前狀態到起始狀態的實際步數；
get_f_value()：用於計算當前狀態的估價函數值，即啟發函數值與實際代價之和；
compare_f_values()：用於比較兩個狀態的估價函數值的大小；
A*_search()：用於執行A*搜索演算法，求解八數碼問題。
在定義了上述變數和函數後，我們就可以編寫A*搜索演算法的代碼了。下面是一個可能的實現方式：
Copy code
# 定義估價函數
def get_heuristic_value(state):
h_value = 0
# 計算估價函數值
for i in range(len(state)):
for j in range(len(state[i])):
if state[i][j] != goal_state[i][j]:
h_value += 1
return h_value
# 定義實際代價函數
def get_g_value(state):
g_value = 0
# 計算實際代價值
for i in range(len(state)):
for j in range(len(state[i])):
if state[i][j] != init_state[i][j]:
g_value += 1
return g_value
# 定義估價函數值函數
def get_f_value(state):
# 計算估價函數值
f_value = get_g_value(state) + get_heuristic_value(state)
return f_value
# 定義估價函數值比較函數
def compare_f_values(state1, state2):
# 比較兩個狀態的估價函數值
f1 = get_f_value(state1)
f2 = get_f_value(state2)
if f1 < f2:
return -1
elif f1 > f2:
return 1
else:
return 0
# 定義A*搜索演算法
def A*_search():
# 初始化OPEN表和CLOSED表
open_list = []
closed_list = []
# 將初始狀態加入OPEN表
並更新估價函數值 open_list.append(init_state) f_values[init_state] = get_f_value(init_state)
# 循環執行直到OPEN表為空
while len(open_list) > 0:
# 從OPEN表中選擇估價函數值最小的狀態
current_state = min(open_list, key=get_f_value)
# 如果當前狀態是目標狀態，則演算法執行成功
if current_state == goal_state:
return True
# 將當前狀態從OPEN表中移除，並加入CLOSED表
open_list.remove(current_state)
closed_list.append(current_state)
# 獲取當前狀態的所有後繼狀態
successor_states = get_successor_states(current_state)
# 遍歷所有後繼狀態
for successor_state in successor_states:
# 如果後繼狀態已在CLOSED表中，則跳過
if successor_state in closed_list:
continue
# 如果後繼狀態不在OPEN表中，則加入OPEN表並更新估價函數值
if successor_state not in open_list:
open_list.append(successor_state)
f_values[successor_state] = get_f_value(successor_state)
# 如果新的路徑更優，則更新估價函數值
elif get_f_value(successor_state) < f_values[successor_state]:
f_values[successor_state] = get_f_value(successor_state)
# 如果OPEN表為空，則演算法執行失敗
return False
上面的代碼實現了A*搜索演算法的基本流程，包括初始化、主循環、狀態擴展和結束條件判斷。它使用了估價函數值來比較
不同狀態的優劣，從而決定搜索的方向和順序。
為了實現上述需求，我們還需要對代碼進行一些改進和完善，如下所示：
定義3種不同的啟發式函數：我們可以定義3種不同的啟發式函數，分別用於計算曼哈頓距離、歐幾里得距離和拼圖曼哈頓距離。這些啟發式函數的實現方式略有不同，但都基於當前狀態與目標狀態之間的位置關系進行計算。
提供可視化界面：我們可以創建一個可視化界面，用於展示搜索過程。該界面應能夠顯示搜索樹、估價函數值、OPEN表和CLOSED表的動態變化情況。同時，用戶應能夠選擇預定義的啟發式函數，隨機初始化初始狀態，單步執行或連續執行搜索演算法。
統計擴展節點數和執行時間：為了對採用不同啟發式函數的A*演算法進行性能對比研究，我們需要統計演算法執行過程中的擴展節點數和執行時間。這些信息可以用來評估演算法的效率和優劣。
通過上述

改進和完善，我們就可以實現一個能夠求解八數碼問題的A*演算法，具有較好的可視化展示和性能分析能力。

『叄』 問： 40 人工智慧及其應用期末作業 用A*演算法解決下面的八數碼難題。試定義估價函數，啟發函數，

#pragma warning(disable:4786)
#include <algorithm>
#include <cstdio>
#include <set>
#include <utility>
#include <ctime>
#include <cassert>
#include <cstring>
#include <iostream>
using namespace std;

/*item記錄搜索空間中一個結點
state 記錄用整數形式表示的8數碼格局
blank 記錄當前空格位置，主要用於程序優化，
擴展時可不必在尋找空格位置
g, h 對應g(n), h(n)
pre 記錄當前結點由哪個結點擴展而來 */
struct item
{
int state;
int blank;
int g;
int h;
int pre;
};

const int MAXSTEPS = 100000;
const int MAXCHAR = 100;
char buf[MAXCHAR][MAXCHAR]; //open表
item open[MAXSTEPS];
//vector<item> open;
int steps = 0;

//closed表，已查詢狀態只要知道該狀態以及它由哪個結點擴展而來即可，用於輸出路徑
//每次只需得到對應f值最小的待擴展結點，用堆實現提高效率
pair<int, int> closed[MAXSTEPS];
//讀入，將8數碼矩陣格局轉換為整數表示

bool read(pair<int,int> &state)
{
if (!gets(buf[0]))
return false;
if (!gets(buf[1]))
return false;
if (!gets(buf[2]))
return false;

//cout << strlen(buf[0]) << ' ' << strlen(buf[1]) << ' ' << strlen(buf[2]) << endl;
assert(strlen(buf[0]) == 5 && strlen(buf[1]) == 5 && strlen(buf[2]) == 5);
// astar.in中的每行數據長度必須為5
state.first = 0;
for (int i = 0, p = 1; i < 3; ++i)
{
for (int j = 0; j < 6; j += 2)
{
if (buf[i][j] == '0')
state.second = i * 3 + j / 2; // state.second為0（空格）在節點中的位置
else
state.first += p * (buf[i][j] - '0');
p *= 10;
}
}

/* 若初試節點為:
1 2 3
8 0 4
7 6 5
則state.first為567408321，state.second為4
*/
return true;
}

//計算當前結點距目標的距離
int calculate(int current, int target) // return h=the sum of distances each block have to move to the right position,這里的each block不包括空格
{
int c[9], t[9];
int i, cnt = 0;
for (i = 0; i < 9; ++i)
{
c[current % 10] = t[target % 10] = i;
current /= 10;
target /= 10;
}

for (i = 1; i < 9; ++i)
cnt += abs(c[i] / 3 - t[i] / 3) + abs(c[i] % 3 - t[i] % 3);

return cnt;
}

//open表中結點間選擇時的規則 f(n) = g(n) + h(n)

class cmp
{
public: inline bool operator()(item a, item b)
{
return a.g + a.h > b.g + b.h;
}
};

//將整數形式表示轉換為矩陣表示輸出
void pr(int state)
{
memset(buf, ' ', sizeof(buf));
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 6; j += 2)
{
if (state % 10)
buf[i][j] = state % 10 + '0';
state /= 10;
}

buf[i][5] = '\0';
puts(buf[i]);
}
}

//用於判斷當前空格是否可以向對應方向移動
inline bool suit(int a, int b) //空格移動後的坐標為(a,b)
{
return (a >= 0 && a < 3 && b >= 0 && b < 3);
}

//遞歸輸出搜索路徑
void path(int index)
{
if (index == 0)
{
pr(closed[index].first);
puts("");
return;
}
path(closed[index].second);
pr(closed[index].first); //將整數形式表示轉換為矩陣表示輸出
puts("");
++steps;
}

int getNixuNum( int state ) //求節點的逆序對數
{
int sum = 0;
int result[9];
memset( result, 0, sizeof(result) );
//cout << result[8] << result[7] << endl;

char buf[10];
itoa( state, buf, 10 );
//cout << buf << endl;
int k = 0;
while( buf[k] != '\0' )
{
result[9-k-1] = buf[k] - '0';
k++;
}

for( int i = 0; i < 9; i++ )
{
for( int j = i + 1; j < 9; j++ )
{
if( result[i] && result[j] && result[i] > result[j] )
{
sum++;
}
}
}
return sum; //返回3*3方格數組的逆序對數
}

int main()
{
//cout << getNixuNum(87654321);
//open.resize(MAXSTEPS);
unsigned int t1 = clock();
//cout << open.size() << endl;
if( freopen("astar.in", "r", stdin) == NULL )
{
cout << "file not find\n";
exit(0);
};

freopen("astar2.out", "w", stdout);
set<int>states;
char tmp[100];
int i, x, y, a, b, nx, ny, end, next, index, kase = 0;
pair<int,int> start, target;
item head; //4個方向移動時的偏移量
const int xtran[4] = {-1, 0, 1, 0};
const int ytran[4] = {0, 1, 0, -1};
const int p[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};

while (read(start)) // 讀取初試狀態節點
{
unsigned int t2 = clock();
printf("Case %d:\n\n", ++kase);
gets(tmp);
read(target); // 讀取目標狀態節點
gets(tmp);

int targetNixuNum = getNixuNum(target.first);
//若兩者的逆序對數不是同為奇數或同為偶數，則無解
if( !(getNixuNum(start.first)&1 && targetNixuNum&1 || !(getNixuNum(start.first)&1) && !(targetNixuNum&1)) )
{
cout << "無法從初始節點到終態節點\n";
exit(0);
}
//初始化open表，將初始狀態加入
open[0].state = start.first;
open[0].h = calculate(start.first, target.first); // 計算當前節點到目標節點的估計距離
open[0].blank = start.second;
open[0].pre = -1; // 初始節點無父節點
open[0].g = 0; // 初始節點的g為0
index = 0;
states.insert(start.first); // 擴展過節點保存在states中，即出現過的狀態保存在states中，states為set<int>類型，其中的states中的元素唯一

//提取open表中f值最小元素放入closed表，並對該結點進行擴展
for (end = 1; end > 0; ++index) // end為open表中的元素個數，一直循環到open表為空
{
assert(index < MAXSTEPS);
//臨時存儲
head = open[0]; // 由於使用pop_heap函數和push_heap函數，所以open[0]為g+h最小的元素

//放入closed表記錄當前格局和由哪個結點擴展而來（該結點肯定已在closed表中）
closed[index].first = open[0].state; //放入close表中，表示已經擴展完的節點，下面的for循環會擴展其節點
closed[index].second = open[0].pre; // index表示當前close表中當前擴展節點的下標
//從open表中刪除該結點
pop_heap(open, open + end, cmp());//為algorithm文件中的函數，第一個參數指定開始位置，第二個指定結束，第三個指定比較函數
--end;

//得到結果，遞歸輸出路徑
if (head.state == target.first)
{
path(index);
break;
}

x = head.blank / 3;
y = head.blank % 3; //空格在3*3方格中的x,y坐標
/*
|2 0 3|
A = |1 8 4|
|7 6 5| // 看成3*3的數組
則head.blank=1
x=0,y=1,即空格的在3*3的數組中下標為(0,1)
*/
for (i = 0; i < 4; ++i)
{
nx = x + xtran[i];
ny = y + ytran[i];
/*
i=0時：(nx,ny）為當前空格向上移動一格後的坐標
i=1時：(nx,ny）為當前空格向右移動一格後的坐標
i=2時：(nx,ny）為當前空格向下移動一格後的坐標
i=3時：(nx,ny）為當前空格向左移動一格後的坐標
*/
if (suit(nx, ny)) // 判斷是否能夠移動
{
a = head.blank; // 空格當前位置,以上面矩陣A為例，a=1
b = nx * 3 + ny; // 空格移動後的新位置,開始是能夠向右邊移動，故b=0*3+2=2
//調換十進製表示整數對應兩個數字位
next = head.state + ((head.state % p[a + 1]) / p[a] - (head.state % p[b + 1]) / p[b]) * p[b] + ((head.state % p[b + 1]) / p[b] - (head.state % p[a + 1]) / p[a]) * p[a];
// 如head.state=567481302,空格向右移動一次後，next=567481032,即為移動後的節點

// 判斷能否由當前節點到達目標節點
if( ( getNixuNum(next)&1 && targetNixuNum&1 ) || ( !(getNixuNum(next)&1) && !(targetNixuNum&1) ) )
{
//判斷是否已經擴展過，即已經出現過
if (states.find(next) == states.end()) //沒出現就保存一下，也存入open表
{
states.insert(next);
open[end].pre = index; //擴展後的子節點，其父節點為當前擴展節點
open[end].blank = b;
open[end].state = next;
open[end].h = calculate(next,target.first);
open[end].g = head.g + 1;
++end; //open表中元素加1
push_heap(open, open + end, cmp()); //壓入堆中
}
}

}
}
}

if (end <= 0)
puts("No solution");
else
{
printf("Num of steps: %d\n", steps);
printf("Num of expanded: %d\n", index);
printf("Num of generated: %d\n", index + end);
printf("Time consumed: %d\n\n", clock() - t2);
}

states.clear();
steps = 0;
}
printf("Total time consumed: %d\n", clock() - t1);
return 0;
}

『肆』 為什麼八數碼問題用a*演算法求解合適

其實A*演算法也是一種最好優先的演算法只不過要加上一些約束條件罷了。由於在一些問題求解時，我們希望能夠求解出狀態空間搜索的最短路徑，也就是用最快的方法求解問題，A*就是干這種事情的！我們先下個定義，如果一個估價函數可以找出最短的路徑，我們稱之為可採納性。A*演算法是一個可採納的最好優先演算法。A*演算法的估價函數可表示為：f'(n)=g'(n)+h'(n)這里，f'(n)是估價函數，g'(n)是起點到節點n的最短路徑值，h'(n)是n到目標的最短路經的啟發值。由於這個f'(n)其實是無法預先知道的，所以我們用前面的估價函數f(n)做近似。g(n)代替g'(n)，但g(n)>=g'(n)才可（大多數情況下都是滿足的，可以不用考慮），h(n)代替h'(n)，但h(n)<=h'(n)才可（這一點特別的重要）。可以證明應用這樣的估價函數是可以找到最短路徑的，也就是可採納的。我們說應用這種估價函數的最好優先演算法就是A*演算法。舉一個例子，其實廣度優先演算法就是A*演算法的特例。其中g(n)是節點所在的層數，h(n)=0，這種h(n)肯定小於h'(n)，所以由前述可知廣度優先演算法是一種可採納的。實際也是。當然它是一種最臭的A*演算法。再說一個問題，就是有關h(n)啟發函數的信息性。h(n)的信息性通俗點說其實就是在估計一個節點的值時的約束條件，如果信息越多或約束條件越多則排除的節點就越多，估價函數越好或說這個演算法越好。這就是為什麼廣度優先演算法的那麼臭的原因了，誰叫它的h(n)=0，一點啟發信息都沒有。但在游戲開發中由於實時性的問題，h(n)的信息越多，它的計算量就越大，耗費的時間就越多。就應該適當的減小h(n)的信息，即減小約束條件。但演算法的准確性就差了，這里就有一個平衡的問題。

『伍』 C++ A* 演算法實現中，怎樣便捷地實現「搜索節點在OPEN表和CLOSED表之間 切換」

你是在用A*演算法做八數碼問題么。

比如你要在open表中刪除一個節點，然後放到close表中，你可以反過來做，

先找到這個結點，在close表中插入，然後再在open表中刪除

我把我寫的windows下的代碼貼過來你看看，順便說一句，open表和close表都要經常做刪除節點的操作，所以用vector（線性表）其實性能不好，我用的List。