⑴ 人工智慧的八數碼問題，過程化的c語言編程方法，求解，好的話要多少分給多少分！！！
#include <stdio.h>
#include <stdlib.h>
#define TIME 50 //限定只搜索前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);
}
}
}
⑵ 問： 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;
}
⑶ 八數碼問題 C語言 廣度優先 其他也OK
nclude "stdio.h"
typedef int datatype; /*假定線性表元素的類型為整型*/
#define maxsize 1024 /*假定線性表的最大長度為1024*/
# define n 100 /* 圖的頂點最大個數 */
typedef char VEXTYPE; /* 頂點的數據類型 */
typedef float ADJTYPE; /* 權值類型 */
typedef struct
{ VEXTYPE vexs[n] ; /* 頂點信息數組 */
ADJTYPE arcs[n][n] ; /* 邊權數組 */
int num ; /* 頂點的實際個數 */
}GRAPH;
/***********************1。置空圖**********************/
void GraphInit(GRAPH *L)
{
L->num=0;
}
/***********************2。求結點數**********************/
int GraphVexs(GRAPH *L)
{
return(L->num);
}
/***********************3。創建圖**********************/
void GraphCreate(GRAPH *L)
{
int i,j;
GraphInit(L);
printf("請輸入頂點數目：");
scanf("%d",&L->num);
printf("請輸入各頂點的信息(單個符號）：");
for(i=0;i<L->num;i++)
{
fflush(stdin);
scanf("%c",&L->vexs[i]);
}
printf("請輸入邊權矩陣的信息：");
for(i=0;i<L->num;i++)
{
for(j=0;j<L->num;j++)
{
scanf("%f",&L->arcs[i][j]);
}
}
printf("圖已經創建完畢！");
}
/***********************4。圖的輸出**********************/
void GraphOut(GRAPH L)
{
int i,j;
printf("\n圖的頂點數目為：%d",L.num);
printf("\n圖的各頂點的信息為：\n");
for(i=0;i<L.num;i++)
printf("%c ",L.vexs[i]);
printf("\n圖的邊權矩陣的信息為：\n");
for(i=0;i<L.num;i++)
{
for(j=0;j<L.num;j++)
{
printf("%6.2f ",L.arcs[i][j]);
}
printf("\n");
}
printf("圖已經輸出完畢！");
}
/***********************5。圖的深度周遊**********************/
void DFS(GRAPH g,int qidian,int mark[])
//從第qidian個點出發深度優先周遊圖g中能訪問的各個頂點
{
int v1;
mark[qidian]=1;
printf("%c ",g.vexs[qidian]);
for(v1=0;v1<g.num;v1++)
{
if(g.arcs[qidian][v1]!=0&&mark[v1]==0)
DFS(g,v1,mark);
}
}
/***********************6。圖的深度周遊**********************/
void GraphDFS(GRAPH g)
//深度優先周遊圖g中能訪問的各個頂點
{
int qidian,v,v1,mark[maxsize];
printf("\n深度周遊：");
printf("\n請輸入起點的下標：");
scanf("%d",&qidian);
for(v=0;v<g.num;v++)
{
mark[v]=0;
}
for(v=qidian;v<g.num+qidian;v++)
{
//printf("v=%d ",v);
v1=v%g.num;
if(mark[v1]==0)
DFS(g,v1,mark);
}
}
typedef int DATATYPE; //隊列元素的數據類型
typedef struct
{
DATATYPE data[maxsize]; //隊中元素
int front,rear; //隊頭元素下標、隊尾元素後面位置的下標
} SEQQUEUE;
/*****************************************************************************/
void QueueInit(SEQQUEUE *sq)
//將順序循環隊列sq置空（初始化）
{
sq->front=0;
sq->rear=0;
}
/*****************************************************************************/
int QueueIsEmpty(SEQQUEUE sq)
//如果順序循環隊列sq為空，成功返回1，否則返回0
{
if (sq.rear==sq.front)
return(1);
else
return(0);
}
/*****************************************************************************/
int QueueFront(SEQQUEUE sq,DATATYPE *e)
//將順序循環隊列sq的隊頭元素保存到e所指地址，成功返回1，失敗返回0
{
if (QueueIsEmpty(sq))
else
}
/*****************************************************************************/
int QueueIn (SEQQUEUE *sq,DATATYPE x)
//將元素x入隊列sq的隊尾，成功返回1，失敗返回0
{
if (sq->front==(sq->rear+1)%maxsize)
{
printf("queue is full!\n");
return 0;
}
else
{
sq->data[sq->rear]=x;
sq->rear=(sq->rear+1)%maxsize;
return(1);
}
}
/*****************************************************************************/
int QueueOut(SEQQUEUE *sq)
//將隊列sq隊首元素出隊列，成功返回1,失敗返回0
{
if (QueueIsEmpty(*sq))
{
printf("queue is empty!\n");
return 0;
}
else
{
sq->front=(sq->front+1)%maxsize;
return 1;
}
}
/***********************7。圖的廣度周遊**********************/
void BFS(GRAPH g,int v,int mark[])
//從v出發廣度優先周遊圖g中能訪問的各個頂點
{
int v1,v2;
SEQQUEUE q;
QueueInit(&q);
QueueIn(&q,v);
mark[v]=1;
printf("%c ",g.vexs[v]);
while(QueueIsEmpty(q)==0)
{
QueueFront(q,&v1);
QueueOut(&q);
for(v2=0;v2<g.num;v2++)
{
if(g.arcs[v1][v2]!=0&&mark[v2]==0)
{
QueueIn(&q,v2);
mark[v2]=1;
printf("%c ",g.vexs[v2]);
}
}
}
}
/***********************8。圖的廣度周遊**********************/
void GraphBFS(GRAPH g)
//深度優先周遊圖g中能訪問的各個頂點
{
int qidian,v,v1,mark[maxsize];
printf("\n廣度周遊：");
printf("\n請輸入起點的下標：");
scanf("%d",&qidian);
for(v=0;v<g.num;v++)
{
mark[v]=0;
}
for(v=qidian;v<g.num+qidian;v++)
{
v1=v%g.num;
if(mark[v1]==0)
BFS(g,v1,mark);
}
}
/***********************主函數**********************/
void main()
{
GRAPH tu;
GraphCreate(&tu);
GraphOut(tu);
GraphDFS(tu);
GraphBFS(tu);
}
另外,虛機團上產品團購,超級便宜
⑷ 高分懸賞C語言高手幫我把這段C程序加註釋
void print(int k) // 列印結果
{
if(out[k].pre != -1){
print(out[k].pre);
int i,j,f = out[k].data,tt;
printf("第%d步:\n",no++);
for(i = 2; i >= 0; i--){
for(j = 2; j >= 0; j--){
ot[i][j] = f%10;
f /= 10;
}
}
for(i = 0; i < 3; i++){
for(j = 0; j < 3; j++){
if(ot[i][j] == 0)
printf(" ");
else
printf("%d ",ot[i][j]);
}
printf("\n");
}
printf("\n");
}
}
int main(void)
{
int i,j,k,temp[9],s;
bool used[9] = {0};
char op[10];
printf("\t\t\t******************************\n");
printf("\t\t\t* 八數碼問題A*搜索求解程序 *\n");
printf("\t\t\t* *\n");
printf("\t\t\t******************************\n\n\n");
printf("程序默認目標狀態為：\n");
for(i = 0; i < 3; i++){
for(j = 0; j < 3; j++){
printf("%d ",ter[i][j]);
}
printf("\n");
}
while(1){
printf("確認請輸入y，取消另輸入目標狀態請輸入n:");
scanf("%s",op);
if(op[0] == 'n'){
printf("請參照上面的樣式輸入目標狀態（空白位置以0代替）:\n");
for(i = 0; i < 3; i++){
for(j = 0; j < 3; j++){
scanf("%d",&ter[i][j]);
}
}
}
else if(op[0] != 'y')
printf("輸入錯誤！\n");
else
break;
}
while(1){
printf("請參照上面的格式輸入初始狀態（空白位置以0代替）:\n");
k = 0;
bool error = false;
memset(used,0,sizeof(used));
for(i = 0; i < 3; i++){
for(j = 0; j < 3; j++){
scanf("%d",&sta[k]);
ot[i][j] = sta[k];
if(used[sta[k]]){
error = true;
}
used[sta[k]] = 1;
temp[k++] = ter[i][j];
}
}
int ts = nxnum(sta);
int tt = nxnum(temp);
if(error){
printf("輸入錯誤(有相同數字出現)，請重新輸入！\n");
continue;
}
if((ts&1) != (tt&1)){
printf("從初始狀態無法到達目標狀態，請重新輸入。\n");
}
else break;
}
if(H(ot) == 0){
printf("所輸入狀態就是目標狀態！\n");
return 0;
}
s = 0;
for(i = 0; i < 9; i++){
s = s*10 + sta[i];
}
astar(s);
print(pout);
printf("第%d步:\n",no);
for(i = 0; i < 3; i++){
for(j = 0; j < 3; j++){
if(ter[i][j] == 0)
printf(" ");
else
printf("%d ",ter[i][j]);
}
printf("\n");
}
printf("共走了%d步。\n",no);
long t = 10000000L;
clock_t start, finish;
double ration;
/* 測量一個事件持續的時間*/
start = clock();
while( t-- ) ;
finish = clock();
ration = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "搜索演算法執行時間為：%f seconds\n", ration );
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語言編程，注意C語言！！！
基於51的程序：
#include <reg52.h>
sbit sda=P0^5;
sbit scl=P0^6;
code char led_code[19]={0x11,0xd7,0x32,0x92,0xd4, // 0,1,2,3,4
0x98,0x18,0xd3,0x10,0x90, // 5,6,7,8,9
0x50,0x1c,0x39,0x16,0x38, // a,b,c,d,e,
0x78,0xfe,0xef,0xff}; // f - dot dark
void seperate(unsigned char second,minute,hour); //1調用拆分函數
void display(unsigned char second,minute,hour); // 2調用顯示函數 一定要在各處強調unsignde嗎？
void shift(unsigned char); //3調用移位函數
void delay_1s(unsigned int x); //4調用延時函數
unsigned char second,minute,hour;
unsigned char second0,second1,
minute0,minute1,
hour0,hour1; // 這三行表示了時、分、秒所佔數碼管的個數和位置。 叫形參？
void main()
{
while(1)
{
for(hour=0;hour<24;hour++) //三個for語句的安排妙啊！ 我們看到的鍾表時分秒的變化
！
{
for(minute=0;minute<60;minute++)
{
for(second=0;second<60;second++)
{
display(second,minute,hour);
delay_1s(65535);
}
}
}
}
}
void display(unsigned char second,minute,hour) //2對顯示函數的說明
{
seperate(second,minute,hour);
shift(second0);
shift(second1);
shift(16);
shift(minute0);
shift(minute1);
shift(16);
shift(hour0);
shift(hour1);
}
void seperate(unsigned char second,minute,hour) //1對拆分函數的說明
{
second0=second%10;
second1=second/10;
minute0=minute%10;
minute1=minute/10;
hour0=hour%10;
hour1=hour/10;
}
void shift(unsigned char n) //3對移位函數的說明
{
unsigned char dat,minute;
dat=led_code[n];
scl=0;
for(minute=0;minute<8;minute++)
{
if (dat&0x80) sda=1;
else sda=0;
scl=1;
scl=0;
dat<<=1;
}
}
void delay_1s(unsigned int a) //4對延時函數的說明
{
while(a--);
}
⑺ 求8數碼A或A*演算法（用C語言）
題目地址:http://acm.pku.e.cn/JudgeOnline/problem?id=1077
BFS:
#include <iostream>
using namespace std;
int fac[10]={1,1};
bool tflag[9];
struct bbit{
unsigned int val:4;
};
struct bbbit
{
unsigned int val:2;
};
struct Node
{
bbit s[9],pos;
int step;
bbbit path[21],tag;
int hashval()
{
int ret=0,i,j,tmp;
memset(tflag,false,sizeof(tflag));
for(i=0;i<8;i++)
{
tmp=0;
for(j=0;j<s[i].val;j++)
if(!tflag[j])
tmp++;
ret+=tmp*fac[8-i];
tflag[s[i].val]=true;
}
return ret;
}
bool up()
{
if(pos.val<=2)return false;
s[pos.val].val^=s[pos.val-3].val;
s[pos.val-3].val^=s[pos.val].val;
s[pos.val].val^=s[pos.val-3].val;
path[step].val=0;
pos.val-=3;
return true;
}
bool down()
{
if(pos.val>=6)return false;
s[pos.val].val^=s[pos.val+3].val;
s[pos.val+3].val^=s[pos.val].val;
s[pos.val].val^=s[pos.val+3].val;
path[step].val=1;
pos.val+=3;
return true;
}
bool left()
{
if(pos.val==0||pos.val==3||pos.val==6)return false;
s[pos.val].val^=s[pos.val-1].val;
s[pos.val-1].val^=s[pos.val].val;
s[pos.val].val^=s[pos.val-1].val;
path[step].val=2;
pos.val--;
return true;
}
bool right()
{
if(pos.val==2||pos.val==5||pos.val==8)return false;
s[pos.val].val^=s[pos.val+1].val;
s[pos.val+1].val^=s[pos.val].val;
s[pos.val].val^=s[pos.val+1].val;
path[step].val=3;
pos.val++;
return true;
}
bool operator==(const Node&x)const
{
int i;
for(i=0;i<9;i++)if(s[i].val!=x.s[i].val)return false;
return true;
}
}Q[362880],S,A,tmp,top;
struct Hash
{
bool d1,d2;
Node D;
}hash[362880];
inline void mkfac(){int i;for(i=2;i<=9;i++)fac[i]=fac[i-1]*i;}
inline int eval(char c){return c=='x'?0:c-'0';}
void o(Node x,Node y)
{
int i;
for(i=1;i<=x.step;i++)
{
switch(x.path[i].val)
{
case 0:putchar('u');break;
case 1:putchar('d');break;
case 2:putchar('l');break;
case 3:putchar('r');break;
}
}
for(i=y.step;i>=1;i--)
switch(y.path[i].val){
case 0:putchar('d');break;
case 1:putchar('u');break;
case 2:putchar('r');break;
case 3:putchar('l');break;
}
puts("");
}
int main()
{
char buf[11];
int i,t,l,r;
bool flag;
mkfac();
while(NULL!=gets(buf))
{
t=0;
for(i=0;i<=7;i++)A.s[i].val=i+1;A.s[8].val=0;A.pos.val=8;
for(i=0;buf[i];i++)
{
if(buf[i]==' ')continue;
S.s[t].val=eval(buf[i]);
if(S.s[t].val==0)
S.pos.val=t;
t++;
}
l=r=0;
flag=false;
for(i=0;i<362880;i++)hash[i].d1=hash[i].d2=false;
S.step=0;S.tag.val=1;
A.step=0;A.tag.val=2;
Q[r++]=S;//tag.val:1
Q[r++]=A;//tag.val:2
while(l<=r)
{
top=Q[l++];
top.step++;
tmp=top;
if(tmp.up())
{
if(tmp.tag.val==1)
{
if(!hash[t=tmp.hashval()].d1)
{
hash[t].d1=true;
Q[r++]=tmp;
if(hash[t].d2&&hash[t].D==tmp)
{
//find ans...
o(tmp,hash[t].D);
goto AA;
}
if(!hash[t].d2)hash[t].D=tmp;
}
}
else
{
if(!hash[t=tmp.hashval()].d2)
{
hash[t].d2=true;
Q[r++]=tmp;
if(hash[t].d1&&hash[t].D==tmp)
{
//find ans...
o(hash[t].D,tmp);
goto AA;
}
if(!hash[t].d1)hash[t].D=tmp;
}
}
}
tmp=top;
if(tmp.down())
{
if(tmp.tag.val==1)
{
if(!hash[t=tmp.hashval()].d1)
{
hash[t].d1=true;
Q[r++]=tmp;
if(hash[t].d2&&hash[t].D==tmp)
{
//find ans...
o(tmp,hash[t].D);
goto AA;
}
if(!hash[t].d2)hash[t].D=tmp;
}
}
else
{
if(!hash[t=tmp.hashval()].d2)
{
hash[t].d2=true;
Q[r++]=tmp;
if(hash[t].d1&&hash[t].D==tmp)
{
//find ans...
o(hash[t].D,tmp);
goto AA;
}
if(!hash[t].d1)hash[t].D=tmp;
}
}
}
tmp=top;
if(tmp.left())
{
if(tmp.tag.val==1)
{
if(!hash[t=tmp.hashval()].d1)
{
hash[t].d1=true;
Q[r++]=tmp;
if(hash[t].d2&&hash[t].D==tmp)
{
//find ans...
o(tmp,hash[t].D);
goto AA;
}
if(!hash[t].d2)hash[t].D=tmp;
}
}
else
{
if(!hash[t=tmp.hashval()].d2)
{
hash[t].d2=true;
Q[r++]=tmp;
if(hash[t].d1&&hash[t].D==tmp)
{
//find ans...
o(hash[t].D,tmp);
goto AA;
}
if(!hash[t].d1)hash[t].D=tmp;
}
}
}
tmp=top;
if(tmp.right())
{
if(tmp.tag.val==1)
{
if(!hash[t=tmp.hashval()].d1)
{
hash[t].d1=true;
Q[r++]=tmp;
if(hash[t].d2&&hash[t].D==tmp)
{
//find ans...
o(tmp,hash[t].D);
goto AA;
}
if(!hash[t].d2)hash[t].D=tmp;
}
}
else
{
if(!hash[t=tmp.hashval()].d2)
{
hash[t].d2=true;
Q[r++]=tmp;
if(hash[t].d1&&hash[t].D==tmp)
{
//find ans...
o(hash[t].D,tmp);
goto AA;
}
if(!hash[t].d1)hash[t].D=tmp;
}
}
}
}
AA:flag=true;
if(!flag)
puts("unsolvable");
}
return 0;
}
A*:
#include <iostream>
#include <queue>
using namespace std;
int fac[10]={1,1};
struct Node
{
int s[9],step,pos;
char path[501];
int hashval()
{
int ret=0,i,j,tmp;
bool flag[9];
memset(flag,false,sizeof(flag));
for(i=0;i<8;i++)
{
tmp=0;
for(j=0;j<s[i];j++)
if(!flag[j])
tmp++;
ret+=tmp*fac[8-i];
flag[s[i]]=true;
}
return ret;
}
bool up()
{
if(pos<=2)return false;
s[pos]^=s[pos-3];
s[pos-3]^=s[pos];
s[pos]^=s[pos-3];
path[step]='u';
pos-=3;
return true;
}
bool down()
{
if(pos>=6)return false;
s[pos]^=s[pos+3];
s[pos+3]^=s[pos];
s[pos]^=s[pos+3];
path[step]='d';
pos+=3;
return true;
}
bool left()
{
if(pos==0||pos==3||pos==6)return false;
s[pos]^=s[pos-1];
s[pos-1]^=s[pos];
s[pos]^=s[pos-1];
path[step]='l';
pos--;
return true;
}
bool right()
{
if(pos==2||pos==5||pos==8)return false;
s[pos]^=s[pos+1];
s[pos+1]^=s[pos];
s[pos]^=s[pos+1];
path[step]='r';
pos++;
return true;
}
bool operator==(const Node&x)const
{
int i;
for(i=0;i<9;i++)if(s[i]!=x.s[i])return false;
return true;
}
void show()
{
int i,j;
for(i=0;i<=6;i+=3,cout<<endl)
for(j=i;j<=i+2;j++)
cout<<s[j];
}
bool operator<(const Node&x)const
{
int la=0,lb=0,i;
for(i=0;i<8;i++)if(s[i]!=i+1)la++;la+=(s[8]!=0);
for(i=0;i<8;i++)if(x.s[i]!=i+1)lb++;lb+=(x.s[8]!=0);
return la>lb;
}
}S,A,tmp,top;
priority_queue<Node> Q;
bool hash[362880];
void mkfac(){int i;for(i=2;i<=9;i++)fac[i]=fac[i-1]*i;}
int eval(char c){return c=='x'?0:c-'0';}
void output(Node x)
{
int i;
for(i=1;i<=x.step;i++)
putchar(x.path[i]);
puts("");
}
int main()
{
char buf[11];
int i,t,l,r;
bool flag;
mkfac();
while(NULL!=gets(buf))
{
t=0;
for(i=0;i<=7;i++)A.s[i]=i+1;A.s[8]=0;A.pos=8;
for(i=0;buf[i];i++)
{
if(buf[i]==' ')continue;
S.s[t]=eval(buf[i]);
if(S.s[t]==0)
S.pos=t;
t++;
}
l=r=0;
flag=false;
memset(hash,false,sizeof(hash));
S.step=0;
while(!Q.empty())Q.pop();
Q.push(S);
while(!Q.empty())
{
top=Q.top();
Q.pop();
top.step++;
tmp=top;
if(tmp.up())
{
if(!hash[t=tmp.hashval()])
{
hash[t]=true;
Q.push(tmp);
if(tmp==A)
{
//find ans...
output(tmp);
goto AA;
}
}
}
tmp=top;
if(tmp.down())
{
if(!hash[t=tmp.hashval()])
{
hash[t]=true;
Q.push(tmp);
if(tmp==A)
{
//find ans...
output(tmp);
goto AA;
}
}
}
tmp=top;
if(tmp.left())
{
if(!hash[t=tmp.hashval()])
{
hash[t]=true;
Q.push(tmp);
if(tmp==A)
{
//find ans...
output(tmp);
goto AA;
}
}
}
tmp=top;
if(tmp.right())
{
if(!hash[t=tmp.hashval()])
{
hash[t]=true;
Q.push(tmp);
if(tmp==A)
{
//find ans...
output(tmp);
goto AA;
}
}
}
}
AA:flag=true;
if(!flag)
puts("unsolvable");
}
return 0;
}
⑻ 用c語言或c++實現，用深度優先演算法，寬度優先演算法和A演算法求解把數碼問題，請高手幫忙寫出代碼
看著懂，寫出來就困難了
⑼ 八數碼問題用c語言或者c++寫的程序，麻煩在附帶上演算法 謝了發到[email protected]
<html>
<head>
<script type="text/javascript">
function disPlay(){
var b1 = document.getElementById("box1");
var b2 = document.getElementById("box2");
if(window.location.href = "http://www.abc.com/"){
b1.style.display = "none";
b2.style.display = "block"
}
else{
b1.style.display = "block";
b2.style.display = "none"
}
}
</script>
</head>
<body onload="disPlay();"> //頁面載入以後及調用函數
<div id="box1">
box1需要顯示的內容
</div>
<div id="box2">
box2需要顯示的內容
</div>
</body>
</html>