?? 8數碼問題.cpp
字號:
/*--------------------------------------------------說明------------------------------------------------*/
/* 此程序為八數碼問題求解 */
/* 本程序利用啟發(fā)函數來實現(xiàn)A算法（實為A*算法），效率較高； */
/* 具體思想請參考人工智能相關書籍； */
/* 啟發(fā)函數為 深度+不在位數； */
/* 作者：張莉 學號:040640203; */
/* 日期：2008.06.21； */
/* 僅供學習使用。 */
#include<stdio.h>
#include<stdlib.h>
#define UP 1 //節(jié)點向上移
#define DOWN 2 //節(jié)點向下移
#define LEFT 3 //節(jié)點向左移
#define RIGHT 4 //節(jié)點向右移
#define MAXVEX 40320 //定義最大擴展節(jié)點數
/*---------------------------------------------部分參數--------------------------------------------------------*/
int origin_data[9]; //初始節(jié)點
int target_data[9]; //目標節(jié)點
typedef struct vex{ //定義結構體節(jié)點
int data[9]; //此時的數據排列,等價于八數碼狀態(tài)
int layer; //節(jié)點的層數
int diff; //節(jié)點與目標節(jié)點相比不同的位數
int point; //標志位，未被訪問為0，被open表訪問后為1，被close表訪問時為1
int weight; //weight=diff+layer,相當于A*算法中的f函數
struct vex *next;
struct vex *prio;
struct vex *father;
}vexnode;
vexnode *open_root;
vexnode*close_root;
/*------------------------------------------部分參數-----------------------------------------------------------*/
/*---------------------------------------------------主要函數------------------------------------------------------------*/
//函數名稱：vexnode*create_vexnode()
//功能說明：新建一個結構體節(jié)點，返回節(jié)點指針
//入口參數：無
//出口參數：結構體節(jié)點的指針
vexnode*create_vexnode(){
return(vexnode*)malloc(sizeof(vexnode));
}
//函數名稱：check_inputnum(int data[]);
//功能說明：檢查輸入數據的正確性
//入口參數：一維數組
//出口參數：若數組正確，返回值為1，反之返回0，并輸出錯誤原因
int check_inputnum(int data[]){
int i=0,j;
while(i<9){
if(data[i]>8){
printf("此輸入數據中第%d行%d列 %d大于8\n",i/3+1,i%3+1,data[i]);
return 0;
}//if
if(data[i]<0){
printf("此輸入數據中第%d行%d列 %d小于0\n",i/3+1,i%3+1,data[i]);
return 0;
}//if
i++;
}
for(i=0;i<9;i++)
for(j=i+1;j<9;j++){
if(data[i]==data[j]){
printf("此輸入數據中第%d行%d列與第%d行%d列數據%d相同.\n",i/3+1,i%3+1,j/3+1,j%3+1,data[i]);
return 0;
}//if
}//for
return 1;
}
//函數名稱：ary_attr(int data[]);
//功能說明：判斷一維數組的奇偶屬性
//入口參數：一維數組
//出口參數：若數組屬性為奇，返回值為1，為偶則返回為0
int ary_attr(int data[]){
int i,j,attri;
attri=0;
for(i=1;i<9;i++)
for(j=0;j<i;j++)
if(data[i]!=0&&data[j]!=0&&data[j]<data[i])
attri++;
return attri%2;
}
//函數名稱：input_data(int data1[],int data2[]);
//功能說明: 輸入初始節(jié)點和目標節(jié)點的八數碼狀態(tài)，并判斷正確性，直到輸入正確或退出程序為止
//入口參數：兩個一維數組
//出口參數：如果輸入正確，返回值為1，否則退出程序
int input_data(int data1[],int data2[]){
int i;
char choice1;
printf("請輸入初始節(jié)點數據: \n");
printf("請輸入3行從0到8的數據：\n");
for(i=0;i<9;i++)
scanf("%d",data1+i);
while(!check_inputnum(data1)){
printf("數據輸入錯誤!\n");
printf("要重新輸入嗎?(y/n)");
scanf("%c",&choice1);
if(choice1=='y'||choice1=='Y'){
printf("\n請重新輸入：");
for(i=0;i<9;i++)
scanf("%d",data1+i);
}//if
else if(choice1=='n'||choice1=='N'){
printf("\n抱歉，數據輸入錯誤，無法求解\n");
printf("\n下面將退出程序。");
exit(0);
}//else if
}//while
printf("初始數據輸入無誤!\n");
printf("\n下面請輸入目標節(jié)點數據:\n");
printf("請輸入3行從0到8的數據：\n");
for(i=0;i<9;i++)
scanf("%d",data2+i);
while(!check_inputnum(data2)){
printf("數據輸入錯誤!\n");
printf("要重新輸入嗎?(y/n)");
scanf("%c",&choice1);
if(choice1=='y'||choice1=='Y'){
printf("\n請重新輸入：");
for(i=0;i<9;i++)
scanf("%d",data2+i);
}//if
else if(choice1=='n'||choice1=='N'){
printf("\n抱歉，數據輸入錯誤，無法求解\n");
printf("\n下面將退出程序。\n");
exit(0);
}//else
}//while
printf("目標數據輸入無誤！\n");
return 1;
}//end of program
//函數名稱：copy(int data1[],int data2[])
//函數功能：復制數組
//入口參數：復制數組和被復制數組指針
//出口參數：無
void copy(int data1[],int data2[]){
int i=0;
for(i=0;i<9;i++)
data1[i]=data2[i];
}
//函數名稱：data_solution(int data1[],int data2[])
//函數功能：判斷目標節(jié)點到初始節(jié)點是否有解
//入口參數：連個一維數組（初始節(jié)點和目標節(jié)點八數碼狀態(tài)）
//出口參數：有解返回值1，無解重新輸入或退出
int data_solution(int data1[],int data2[]){
char choice2;
while(ary_attr(data1)!=ary_attr(data2)){
printf("\n抱歉，此8數碼無解!\n");
printf("需要重新輸入嗎？(y/n)");
scanf("%c",&choice2);
if(choice2=='y'||choice2=='Y'){
printf("\n下面請重新輸入數據:\n");
input_data(data1,data2);
}
else if(choice2=='N'||choice2=='n'){
printf("\n--下面將退出程序--\n");
exit(0);
}
}
return 1;
}
//函數名稱：insert_open(vexnode*root,vexnode*p);
//函數功能：將節(jié)點有序插入open表中
//入口參數：open表入口指針，插入節(jié)點指針
//出口參數：節(jié)點指針為空，則返回0，否則，插入open表返回值1
int insert_open(vexnode*root,vexnode*p){
if(p==NULL)
return 0;
vexnode*p1,*p2;
p1=root->next;
p2=root;
while(p1!=NULL&&p->weight>p1->weight){
p2=p1;
p1=p1->next;
}
p2->next=p;
p->prio=p2;
p->next=p1;
if(p1!=NULL)
p1->prio=p;
return 1;
}
//函數名稱：insert_close(vexnode*root,vexnode*p);
//函數功能：將節(jié)點插入close表中
//入口參數：close表入口指針，插入節(jié)點指針
//出口參數：節(jié)點指針為空，則返回0，否則，插入close表返回值1
int ADD_close(vexnode*closeroot,vexnode*p){
if(p==NULL)
return 0;
p->next=closeroot->next;
p->prio=closeroot;
closeroot->next=p;
if(p->next!=NULL)
p->next->prio=p;
return 1;
}
//函數名稱：*first_open(vexnode*root)
//函數功能：刪除open表中第一個節(jié)點
//入口參數：open表的入口指針
//出口參數：若open表為空，則返回NULL，否則返回刪除節(jié)點指針
vexnode*remove_open(vexnode*openroot){
vexnode *p;
if(openroot->next==NULL)
return NULL;
p=openroot->next;
openroot->next=p->next;
if(p->next!=NULL)
p->next->prio=openroot;
p->prio=NULL;
p->next=NULL;
return p;
}
//函數名稱：swap(int *data1,int *data2)
//函數功能：交換一維數組中的兩個數
//入口參數：一維數組中兩個數的指針
//出口參數：無
void swap(int *data1,int *data2){
int data;
data=*data1;
*data1=*data2;
*data2=data;
}
//函數名稱：do_direct(int m[],int op)
//函數功能：對八數碼中的數進行移動
//入口參數：一維數組(視為八數碼)，移動方向
//出口參數：移動成功返回值為1，否則為0
int do_direct(int m[],int op){
int blank;
blank=0;
while(m[blank]!=0&&blank<9)
blank++;
if(blank>=9)
printf("");
switch(op){
case UP:
if(blank>2)
swap(m+blank,m+blank-3);
break;
case DOWN:
if(blank<6)
swap(m+blank,m+blank+3);
break;
case LEFT:
if(blank%3!=0)
swap(m+blank,m+blank-1);
break;
case RIGHT:
if(blank%3!=2)
swap(m+blank,m+blank+1);
break;
default:return 0;
}
return 1;
}
//函數名稱：compare(int data1[],int data2[])
//函數功能：比較當前節(jié)點和目標節(jié)點，得出當前節(jié)點不在位數
//入口參數：兩個一維數組(視為八數碼當前狀態(tài))
//出口參數：返回節(jié)點不在位數
int compare(int data1[],int data2[]){
int i,diff;
diff=0;
for(i=0;i<9;i++)
if(data1[i]!=data2[i])
diff++;
return diff;
}
//函數名稱：has_appear(vexnode*open,vexnode*close,vexnode*p)
//函數功能：判斷移動后節(jié)點是否已經在open表或在close表中出現(xiàn)過
//入口參數：open表和close表入口指針，當前節(jié)點指針
//出口參數：出現(xiàn)過返回值為1，否則為0
int has_appear(vexnode*open,vexnode*close,vexnode*p){
vexnode *p1;
int i,same=1;
p1=open->next;
while(p1!=NULL){
for(i=0;i<9;i++)
if(p1->data[i]!=p->data[i])
same=0;
if(same)
return 1;
p1=p1->next;
}
p1=close->next;
while(p1!=NULL){
same=1;
for(i=0;i<9;i++)
if(p1->data[i]!=p->data[i])
same=0;
if(same)
return 1;
p1=p1->next;
}
return 0;
}
//函數名稱：vexnode *copy(vexnode *p);
//函數功能：復制節(jié)點
//入口參數：被復制節(jié)點指針
//出口參數：返回復制節(jié)點指針
vexnode *copy_vexnode(vexnode*p){
vexnode*p1;
p1=create_vexnode();
int i;
for(i=0;i<9;i++)
(p1->data)[i]=(p->data)[i];
p1->layer=p->layer;
p1->diff=p->diff;
p1->weight=p->weight;
return p1;
}
//函數名稱：print_vexdata(int data[])
//函數功能：打印節(jié)點的八數碼數據
//入口參數：一維數組(視為八數碼)
//出口參數：無
void print_vexdata(int data[]){
int i=0;
for(i=0;i<9;i++){
if((i%3)==0)
printf("\n");
printf("%d ",data[i]);
}
}
//函數名稱：print_allvex(vexnode *p)
//函數功能：采用遞歸，輸出從目標節(jié)點到初始節(jié)點路徑
//入口參數：一維數組(視為八數碼)，移動方向
//出口參數：當前輸出節(jié)點的層數
int print_allvex(vexnode*p){
vexnode*p1=p;
int layer;
if(p1!=NULL){
layer=print_allvex(p1->father);
printf("\n");
print_vexdata(p1->data);
return layer+1;
}
else
return -1;
}
//函數名稱：free_stru(vexnode*root)
//函數功能：釋放節(jié)點表
//入口參數：表入口指針
//出口參數：無
void free_stru(vexnode*root){
vexnode*p1,*p2;
p1=root->next;
while(p1!=NULL){
p2=p1->next;
free(p1);
p1=p2;
}
free(root);
}
//函數名稱:mian()
//函數功能：主程序執(zhí)行
//入口參數：無
//出口參數：無
void main(){
vexnode *p1,*p2;
int op;
int node_num,total_step;
open_root=create_vexnode();
close_root=create_vexnode();
open_root->prio=open_root->next=NULL;
close_root->prio=close_root->next=NULL;
p1=create_vexnode();
p1->father=NULL;
p1->layer=0;
input_data(origin_data,target_data);
data_solution(origin_data,target_data);
copy(p1->data,origin_data);
insert_open(open_root,p1);
node_num=1;
p1=remove_open(open_root);
while(p1!=NULL){
if(node_num<=MAXVEX){
ADD_close(close_root,p1);
for(op=1;op<=4;op++){
p2=copy_vexnode(p1);
do_direct(p2->data,op);
if(has_appear(open_root,close_root,p2)!=1){
p2->father=p1;
p2->layer=p1->layer+1;
p2->diff=compare(p2->data,target_data);
p2->weight=p2->layer+p2->diff;
if(compare(p2->data,target_data)==0){
total_step=print_allvex(p2);
printf("\n總步數為：%d\n",total_step);
free_stru(open_root);
free_stru(close_root);
}//if(compare)
else{
node_num++;
insert_open(open_root,p2);
}//else
}//if(has_appear)
else{
free(p2);
}//else
}//for
p1=remove_open(open_root);
}//if(node_num)
else {
printf("\n抱歉，此八數碼無解！\n");
}//else
}//while
printf("\n無解!\n");
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -