① 人工智慧技術A*演算法解決八數碼問題的實驗

八數碼 估價函數可以選h(s)=ΣΣ[|i-⌊s[i,j]-1)/3⌋| + |j-(s[i,j]-1)mod3|]

② 人工智慧里的八數碼問題怎麼樣用C++語言實現

八數碼問題
有一個3*3的棋盤，其中有0-8 9個數字，0表示空格，其他的數字可以和0交換位置。求由初始狀態
1 2 3
4 5 6
7 8 0
到達目標狀態步數最少的解。

其典型演算法是廣度優先搜索，具體演算法是：
struct 類名 m_ar[可能結點數];
int h,r
main()
{
h=0;r=1;
while ((h<r)&&(r<可能結點數))
{
if (判斷每一種可能性，如果某一種操作符合要求)
&nbs……

③ 人工智慧的八數碼問題，過程化的c語言編程方法，求解，好的話要多少分給多少分！！！

#include <stdio.h>
#include <stdlib.h>
#define TIME 50 //限定只搜索前50步，步以後如果仍然沒有搜索到結果，認為無解。
#define MAXSIZE 200
int n=1;
int result[9]={1,2,3,8,0,4,7,6,5};//所要達到的最終狀態，0代表空格。
typedef struct{
int num[9];
char expension; //記錄是否可以擴展，Y代表可以擴展，N代表不可以。
char banOperate; //表示不可以執行的操作，'L'代表不能左移，'R'代表不能右移，
//'U'代表不能上移，'D'代表不能下移，'C'代表可以任意移動。
int father; //記錄父節點的下標。
}Node;
Node store[MAXSIZE]; //將搜索過的狀態存儲於該數組中。

int same(int temp) //判斷是否達到了目標狀態。
{
for(int j=0;j<9;j++)
if(store[temp].num[j]!=result[j])
return 0;
return 1;
}

void printResult() //輸出搜索結果。
{
for(int j=1;j<=n;j++)
{
printf("第%d步搜索後：\n",j);
printf("\t%d\t%d\t%d\n",store[j].num[0],store[j].num[1],store[j].num[2]);
printf("\t%d\t%d\t%d\n",store[j].num[3],store[j].num[4],store[j].num[5]);
printf("\t%d\t%d\t%d\n",store[j].num[6],store[j].num[7],store[j].num[8]);
printf("\n\n");
}
}

int left(int temp) //將空格進行左移操作。
{
for(int j=0;j<9;j++) //判斷空格的位置。
if(store[temp].num[j]==0)
break;
if(j==0||j==3||j==6)
return 0;
for(int k=0;k<9;k++)
store[n].num[k]=store[temp].num[k];
int tempNum=store[n].num[j-1]; //將移動後的狀態賦給store[n]
store[n].num[j-1]=0;
store[n].num[j]=tempNum;
store[temp].expension='N';
store[n].banOperate='R';
store[n].expension='Y';
store[n].father=temp;
if(same(n)) //判斷store[n]是否為最終想得到的狀態。
{
printResult();
exit(1);
}
n++;
return 1;
}

int right(int temp) //將空格進行右移操作。
{
for(int j=0;j<9;j++)
if(store[temp].num[j]==0)
break;
if(j==2||j==5||j==8)
return 0;
for(int k=0;k<9;k++)
store[n].num[k]=store[temp].num[k];
int tempNum=store[n].num[j+1];
store[n].num[j+1]=0;
store[n].num[j]=tempNum;
store[temp].expension='N';
store[n].banOperate='L';
store[n].expension='Y';
store[n].father=temp;
if(same(n))
{
printResult();
exit(1);
}
n++;
return 1;
}

int up(int temp) //將空格進行上移操作。
{
for(int j=0;j<9;j++)
if(store[temp].num[j]==0)
break;
if(j==0||j==1||j==2)
return 0;
for(int k=0;k<9;k++)
store[n].num[k]=store[temp].num[k];
int tempNum=store[n].num[j-3];
store[n].num[j-3]=0;
store[n].num[j]=tempNum;
store[temp].expension='N';
store[n].banOperate='D';
store[n].expension='Y';
store[n].father=temp;
if(same(n))
{
printResult();
exit(1);
}
n++;
return 1;
}

int down(int temp) //將空格進行下移操作。
{
for(int j=0;j<9;j++)
if(store[temp].num[j]==0)
break;
if(j==6||j==7||j==8)
return 0;
for(int k=0;k<9;k++)
store[n].num[k]=store[temp].num[k];
int tempNum=store[n].num[j+3];
store[n].num[j+3]=0;
store[n].num[j]=tempNum;
store[temp].expension='N';
store[n].banOperate='U';
store[n].expension='Y';
store[n].father=temp;
if(same(n))
{
printResult();
exit(1);
}
n++;
return 1;
}

void init()
{
Node start;
printf("請輸入初始狀態，用空格分開，0代表空格:\n");//輸入初始的狀態。
for(int i=0;i<9;i++)
scanf("%d",&start.num[i]);
for(int k=0;k<9;k++)
if(start.num[k]==0)
break;
start.banOperate='C';
start.expension='Y';
start.father=-1;
store[0]=start; //將初始狀態賦於store[0]。
}
void main(){
init();

if(same(0))
{
printf("沒有必要進行搜索，初始狀態即為最終狀態!");
exit(1);
}

for(int i=0;i<TIME;i++) //開始進行寬度搜索，限定搜索上限為50步。
{
if(store[i].expension='Y')
{
if(store[i].banOperate=='L')
{
up(i);
right(i);
down(i);
}
if(store[i].banOperate=='R')
{
left(i);
up(i);
down(i);
}
if(store[i].banOperate=='U')
{
left(i);
right(i);
down(i);
}
if(store[i].banOperate=='D')
{
left(i);
up(i);
right(i);
}
if(store[i].banOperate=='C')
{
left(i);
up(i);
right(i);
down(i);
}
}
if(n>=TIME) //50步以後仍然沒有達到所要求的狀態，認為無解。
{
n--;
printResult();
printf("Sorry，在所在搜索范圍內沒有搜索到結果！");
exit(1);
}
}

}

④ 程序實現八數碼問題的寬度優先及深度優先演算法，並指出演算法實現過程中程序代碼異同點

你們這些傢伙，我是指導老師，判你們作弊，如果你們不把答案寫給我的話

⑤ 人工智慧實驗報告


人工智慧實驗報告.docx
文檔名稱:人工智慧實驗報告.docx
格式:docx 大小:0.06MB 總頁數:14 展開↓


更多功能
 免費預覽本文檔（全文）
下載敬告：本站不保證該用戶上傳的文檔完整性，不預覽、不比對內容而直接下載產生的反悔... 展開↓
文檔介紹：「人工智慧」實驗報告專業智能科學與技術班級學號姓名日期：2015.實驗一搜索策略一實驗內容熟悉和掌握啟發式搜索的定義、估價函數和演算法過程；比較不同演算法的性能。2. 修改八數碼問題或路徑規劃問題的源程序，改變其啟發函數定義，觀察結果的變化，分析原因。3. 熟悉和掌握各種搜索策略的思想，掌握A*演算法的定義、估價函數和演算法過程，理解求解流程和搜索順序。二實驗思路1．分別以各種搜索演算法為例演示搜索過程，分析各種演算法中的OPEN表CLOSE表的生成過程，分析估價函數對搜索演算法的影響，分析某種啟發式搜索演算法的特點。進入演示系統後，選擇搜索策略演示程序，可從多種不同搜索演算法選擇裝載相

⑥ 問： 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;
}