八数码难题实验报告

一、实验目的

理解并熟悉掌握深度优先搜索和广度优先搜索地方法。

二、实验内容

九宫格中有8个数码，其中只有一个空，规则是只能把一个数码移动到空的格子中，要求从一个初始状态移动到一个目标状态所要花费的最少步数

【算法分析】

解决此类问题的办法是宽度搜索，深度搜索耗时太大无法接受。当需要移动的步数很多时，普通的宽度搜索仍旧无法满足需要，需要对其进行优化。
这个问题也可以推广到流行的拼图游戏。

【具体步骤】

1、确定问题规模（考虑搜索的时间代价）
2、确定产生式规则（如果规则太多，则时间代价会很大）
3、套用经典宽度搜索框架写程序

四、代码和结果

#define _CRT_SECURE_NO_WARNINGS
#include "stdlib.h"
#include"stdio.h"
typedef struct Node {int num[9]; //棋盘状态int deepth; //派生的深度g(n)int diffnum; //不在位的数目h(n)int value; //耗散值f(n)=g(n)+h(n)struct Node* pre;struct Node* next;struct Node* parent;
}numNode;
//棋盘初始状态
int chu_shi_zhuang_tai[9]; 
//棋盘目标状态
int mu_biao_zhuang_tai[9]; 
int numNode_num, total_step;
numNode* open, * close; 
numNode* create_numNode()
{return (numNode*)malloc(sizeof(numNode));
}
//返回第一项，并从Open表中删除
numNode* open_getfirst(numNode* head); 
//向Open表中按序插入新节点
void open_insert(numNode *head,numNode *item); 
//向Close表中插入新节点
void close_append(numNode *head,numNode *item); 
int expand(numNode *item); //扩展节点
int print_result(numNode* item); //打印结果
numNode* copy_numNode(numNode* orgin);
//是否在Open表或Close表中
char isNewNode(numNode* open, numNode* close, int num[9]);
void print_num(int num[9]); //打印棋盘状态
int diff(int num[9]); //求不在位棋子的个数
//初始化，获得棋盘初始状态和目标状态
void init(); 
void swap(int* a, int* b);
int operate(int num[], int op);
void free_list(numNode* head);
void open_insert(numNode* head, numNode* item);
void close_append(numNode* head, numNode* item);
int expand(numNode* p1);//程序入口
int main(int argc, char* argv[])
{//初始化Open表和Close表open = create_numNode();close = create_numNode();//由用户输入初始和目标状态open->pre = open->next = close->pre = close->next = NULL; init(); 
//初始化初始节点numNode* p1;p1 = create_numNode();p1->parent = NULL;p1->deepth = 0;int i = 0;for (i = 0; i < 9; i++){p1->num[i] = chu_shi_zhuang_tai[i];}open_insert(open, p1);numNode_num = 1;p1 = open_getfirst(open);while (p1 != NULL){close_append(close, p1);if (expand(p1))return EXIT_SUCCESS;p1 = open_getfirst(open);}printf("No solution!\n");return EXIT_SUCCESS;
} /* 主函数部分*/
//子函数
void init()
{while (1){printf("规定123456780 代表状态\n""1 2 3\n""4 5 6\n""7 8 0\n");printf("请输入初始状态(数字之间无空格)\n");char temp[10];scanf("%s", &temp);int i = 0;for (i = 0; i < 9 && temp[i] - '0' >= 0 && temp[i] - '0' <= 8; i++) {chu_shi_zhuang_tai[i] = temp[i] - '0';}printf("\n");printf("请输入目标状态（格式同上）:\n");scanf("%s", &temp);int j = 0;for (j = 0; j < 9 && temp[j] - '0' >= 0 && temp[j] - '0' <= 8; j++){mu_biao_zhuang_tai[j] = temp[j] - '0';}printf("\n");system("cls");if (i == 9 && j == 9){break;}}
}
void open_insert(numNode* head, numNode* item)
{numNode* p, * q;p = head->next;q = head;while (p != NULL && item->value > p->value) {q = p;p = p->next;}q->next = item;item->pre = q;item->next = p;if (p != NULL){p->pre = item;}
}
numNode* open_getfirst(numNode* head)
{numNode* p;if (head->next == NULL){return NULL;}p = head->next;head->next = p->next;if (p->next != NULL){p->next->pre = head;}p->pre = NULL;p->next = NULL;return p;
}
void close_append(numNode* head, numNode* item) {item->next = head->next;item->pre = head;head->next = item;if (item->next != NULL){item->next->pre = item;}
}
int expand(numNode* p1)
{numNode* p2;int op = 1;for (op = 1; op <= 4; op++){p2 = copy_numNode(p1);operate(p2->num, op);if (isNewNode(open, close, p2->num) == 'N'){p2->parent = p1;p2->deepth = p1->deepth + 1;p2->diffnum = diff(p2->num);p2->value = p2->deepth + p2->diffnum;if (p2->diffnum == 0){total_step = print_result(p2);printf("一共需要: %d步\n", total_step);free_list(open);free_list(close);return 1;}else{numNode_num++;open_insert(open, p2);}}elsefree(p2);}return 0;
}
int operate(int m[], int op)
{int blank;blank = 0;while (m[blank] != 0 && blank < 9)++blank;if (blank == 9) return 1;switch (op) {case 1: /* up */if (blank > 2)swap(m + blank, m + blank - 3);break;case 2: /* down */if (blank < 6)swap(m + blank, m + blank + 3);break;case 3: /* left */if (blank != 0 && blank != 3 && blank != 6)swap(m + blank, m + blank - 1);break;case 4: /* right */if (blank != 2 && blank != 5 && blank != 8)swap(m + blank, m + blank + 1);break;default: return 1;}return 0;
}
void swap(int* a, int* b)
{int c;c = *a;*a = *b;*b = c;
}
numNode* copy_numNode(numNode* chu_shi_zhuang_tai) {numNode* p;p = create_numNode();p->deepth = chu_shi_zhuang_tai->deepth;p->diffnum = chu_shi_zhuang_tai->diffnum;p->value = chu_shi_zhuang_tai->value;int i;for (i = 0; i < 9; i++){(p->num)[i] = (chu_shi_zhuang_tai->num)[i];}return p;
}
int diff(int num[9])
{int i, diffnum = 0;for (i = 0; i < 9; i++)if (num[i] != mu_biao_zhuang_tai[i])diffnum++;return diffnum;
}
char isNewNode(numNode* open, numNode* close, int num[9]) {numNode* p;int i = 0;p = open->next;while (p != NULL){for (i = 0; i < 9; i++){if (p->num[i] != num[i])break;}if (i == 9) return 'O'; //Openp = p->next;}p = close->next;while (p != NULL){for (i = 0; i < 9; i++){if (p->num[i] != num[i])break;}if (i == 9) return 'C'; //Closep = p->next;}return 'N';
}void free_list(numNode* head) {numNode* p, * q;p = head->next;while (p != NULL){q = p->next;free(p);p = q;}free(head);
}
void print_num(int num[9])
{int i;for (i = 0; i < 9; i++){printf("%d\t", num[i]);if ((i % 3) == 2)printf("\n");}
}
int print_result(numNode* item)
{numNode* p;int step;p = item;if (p != NULL){step = print_result(p->parent);printf("\n第%d步:\n", step + 1);print_num(p->num);return step + 1;}else{return -1;}
}

运行结果

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！