《八数码问题实验报告.docx》由会员分享，可在线阅读，更多相关《八数码问题实验报告.docx（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、八数码问题实验报告一、实验目的二、实验内容九宫格中有8个数码，其中只有一个空，规则是只能把一个数码移动 到空的格子中，要求从一个初始状态移动到一个目标状态所要花费的最少 步数【算法分析】【具体步骤】四、代码和结果define CRT SECURE NO WARNINGS#include stdlib. h#include，zstdio. htypedef struct Node int num9; 棋盘状态int deepth; 派生的深度g(n)int diffnum; 不在位的数目h(n)int value; /耗散值 f (n)=g(n)+h(n) struct Node* pre;st
2、ruct Node* next;p2-parent = pl;p2-deepth = pl-deepth + 1;p2-diffnum = diff(p2-num);p2-value = p2-deepth + p2-diffnum;if (p2-diffnum 二二 0)(total_step = printresult (p2);printf C一共需要：步n，total step);free_list (open);free_list (close);return 1;)else(numNode num+;open_insert(open, p2);) elsefree(p2);retu
3、rn 0;int operate(int m, int op)(int blank;blank = 0;while (mblank != 0 & blank 2)swap(m + blank, m + blank - 3);break;/* down */if (blank 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 num)i = (chu_shi_zhuang_tai-num)i
4、;)return p;)int diff(int num9)(int i, diffnum = 0;for (i = 0; i next;while (p != NULL)(for (i = 0; i numi != numi) break;)if (i = 9) return O ; /Openp = p-next;)p 二 close-next;while (p != NULL)for (i = 0; i numi != numi) break;)if (i = 9) return C ; /Close p = p-next;)return N;void free_list(numNode
5、* head) numNode* p, * q;p = head-next;while (p != NULL)q = p-next;free(p);free(head);void print_num(int num9)(int i;for (i = 0; i parent);printf (n 第%d 步：n，step + 1);printnum(p-num);return step + 1;)else(return -1;ostruct Node* parent;numNode;棋盘初始状态int chushizhuangtai9;棋盘目标状态int mu_biao_zhuang_tai9;
6、int numNodenum, 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 expan
7、d(numNode *item); 扩展节点int print_result(numNode* item) ; /打印结果numNode* copy_numNode(numNode* orgin);是否在Open表或Close表中char isNewNode(numNode* open, numNode* close, int num9);void print_num(int num9); 打印棋盘状态int diff (int num9) ; /求不在位棋子的个数初始化，获得棋盘初始状态和目标状态void init(;void swap(int* a, int* b);int operate
8、(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* pl);程序入口int main(int argc, char* argv)(初始化Open表和Close表open = create_numNode(;close = create numNode(;由用户输入初始和目标状态open-pre = open-next = c
9、lose-pre = close-next = NULL; init(;初始化初始节点numNode* pl;pl 二 create numNode(;pl-parent = NULL;pl-deepth = 0;int i = 0;for (i = 0; i numi = chushizhuangtaii;)open_insert(open, pl);numNodenum = 1;pl 二 open getfirst (open);while (pl != NULL)close append(close, pl);if (expand(pl)return EXIT_SUCCESS;pl =
10、opengetfirst(open);)printf (，zNo solution!n，z);return EXIT_SUCCESS; /*主函数部分*/子函数void init(while (1)Iprintf (规定 123456780 代表状态n1 2 3n4 5 6n7 8 0n);printf (请输入初始状态(数字之间无空格)n);char temp10;scanf(%s， &temp);int i = 0;for (i = 0; i = 0 & tempi- O = 8; i+) chu_shi_zhuang_taii = tempi - O;)printf(n)；printf(
11、请输入目标状态(格式同上)：n)；scanf(%s， fetemp);int j = 0;for (j = 0; j = 0 & tempj- 0， 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(numNodc* head)(numNode* p;if (head-next = NULL)(return NULL;)p
12、= head-next;head-next = p-next;if (p-next != NULL)Ip-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)Iitem-next-pre = item;)int expand(numNode* pl)(numNode* p2;int op = 1;for (op = 1; op num, op);if (isNewNode(open, close, p2-num) = N)