在好例子网,分享、交流、成长!
您当前所在位置:首页C/C++ 开发实例C/C++语言基础 → 基于盲目搜索的宽度优先算法的八数码的解决办法

基于盲目搜索的宽度优先算法的八数码的解决办法

C/C++语言基础

下载此实例
  • 开发语言:C/C++
  • 实例大小:2.19M
  • 下载次数:40
  • 浏览次数:258
  • 发布时间:2016-12-12
  • 实例类别:C/C++语言基础
  • 发 布 人:asdfasdfqwefasd
  • 文件格式:.zip
  • 所需积分:0
 相关标签: 盲目搜索算法 八数码

实例介绍

【实例简介】
【实例截图】

【核心代码】

// AI_Bliend_BFS.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "list.h"
#include <stdio.h>
#include <stdlib.h>

int NumberOfInvert(int s[]);//求逆序数
bool isAimStatus(int s1[], int s2[]);//判断是否是目标状态
void zuoyi(statusNode *node, int s[], int count, int parent, int where0);//左移
void youyi(statusNode *node, int s[], int count, int parent, int where0);//右移
void shangyi(statusNode *node, int s[], int count, int parent, int where0);//上移
void xiayi(statusNode *node, int s[], int count, int parent, int where0);//下移
void printState(int i,int start[], int j,int end[]);//打印状态节点的状态转换过程

void printList(statusNode *head);//遍历链表
void printTrace(statusNode *head, statusNode &node);//打印路径
int main()
{
	//节点状态输入
	int start[9] = { 0 };
	int end[9] = { 0 };
	printf("请输入初始状态:");
	for (int i = 0; i < 9; i  ) {
		scanf("%d", &start[i]);
	}
	printf("请输入目标状态:");
	for (int i = 0; i < 9; i  ) {
		scanf("%d", &end[i]);
	}
	printf("输入结束\n");

	//计算初始状态和结束状态的逆序值
	int sN = NumberOfInvert(start);
	int eN = NumberOfInvert(end);
	
	//判断是否可达
	if ((sN % 2) == (eN % 2)) {
		printf("可达");
	}
	else {
		printf("初始状态和目标状态不可达");
		return 0;
	}

	//将初始节点放入open表
	statusNode *open, *closed;
	//初始化链表头
	initList(&open);
	initList(&closed);

	statusNode snode;
	snode.i = 1;
	for (int i = 0; i < 9; i  ) {
		snode.s[i] = start[i];
	}
	snode.wayOfBirth = 0;
	snode.parent = 0;
	snode.next = NULL;
	insertListHead(open, snode);

	if (isAimStatus(snode.s, end)) {
		printf("达到目标状态\n");
	}
	else {
		printf("状态不相同\n");
	}

	bool isSuccess = false;//判断是否达到目标状态
	int count = 2;//生成节点的序号
	while (!isEmpty(open) && !isSuccess) {
		statusNode *node=deleteHeadNode(open);
		insertListHead(closed,*node);
		isSuccess = isAimStatus(node->s,end);
		if (isSuccess) {
			break;
		}
		else {
			//扩展节点node
			int where0;
			for (int i = 0; i < 9; i  ) {
				if (node->s[i] == 0) {
					where0 = i;
					break;
				}
			}
			printf("状态%d中0的位置是%d\n",node->i,where0);
			switch (where0) {//0表示根节点,1上移,2下移,3左移,4右移
			case 0: {
				statusNode *n;
			//空格向右移(4)
				if (node->wayOfBirth == 3) {//判断上一步是不是左移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					youyi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
			//空格向下移(2)
				if (node->wayOfBirth == 1) {//判断上一步是不是上移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					xiayi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
				break;
			}
			case 1: {
				statusNode *n;
			//空格向左移(3)
				if (node->wayOfBirth == 4) {//判断上一步是不是右移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					zuoyi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i,n->s);
				}
			//空格向右移
				if (node->wayOfBirth == 4) {//判断上一步是不是右移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					youyi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
			//空格向下移
				if (node->wayOfBirth == 1) {//判断上一步是不是上移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					xiayi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
				break;
			}
			case 2: {
				statusNode *n;
			//空格向左移
				if (node->wayOfBirth == 4) {//判断上一步是不是右移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					zuoyi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
			//空格向下移
				if (node->wayOfBirth == 1) {//判断上一步是不是上移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					xiayi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
				break;
			}
			case 3: {
				statusNode *n;
			//空格向上移
				if (node->wayOfBirth == 2) {//判断上一步是不是下移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					shangyi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
			//空格向右移
				if (node->wayOfBirth == 3) {//判断上一步是不是左移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					youyi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
			//空格向下移
				if (node->wayOfBirth == 1) {//判断上一步是不是上移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					xiayi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
				break;
			}
			case 4: {
				statusNode *n;
			//空格向上移(1)
				if (node->wayOfBirth == 2) {//判断上一步是不是下移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					shangyi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
			//空格向下移(2)
				if (node->wayOfBirth == 1) {//判断上一步是不是上移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					xiayi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
			//空格向右移(4)
				if (node->wayOfBirth == 3) {//判断上一步是不是左移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					youyi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
			//空格向左移(3)
				if (node->wayOfBirth == 4) {//判断上一步是不是右移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					zuoyi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
				break;
			}
			case 5: {
				statusNode *n;
			//空格向上移(1)
				if (node->wayOfBirth == 2) {//判断上一步是不是下移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					shangyi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
			//空格向下移(2)
				if (node->wayOfBirth == 1) {//判断上一步是不是上移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					xiayi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
			//空格向左移(3)
				if (node->wayOfBirth == 4) {//判断上一步是不是右移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					zuoyi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
				break;
			}
			case 6: {
				statusNode *n;
			//空格向上移(1)
				if (node->wayOfBirth == 2) {//判断上一步是不是下移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					shangyi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
			//空格向右移(4)
				if (node->wayOfBirth == 3) {//判断上一步是不是左移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					youyi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
				break;
			}
			case 7: {
				statusNode *n;
			//空格向上移(1)
				if (node->wayOfBirth == 2) {//判断上一步是不是下移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					shangyi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
			//空格向右移(4)
				if (node->wayOfBirth == 3) {//判断上一步是不是左移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					youyi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
			//空格向左移(3)
				if (node->wayOfBirth == 4) {//判断上一步是不是右移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					zuoyi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
				break;
			}
			case 8: {
				statusNode *n;
			//空格向上移(1)
				if (node->wayOfBirth == 2) {//判断上一步是不是下移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					shangyi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
			//空格向左移(3)
				if (node->wayOfBirth == 4) {//判断上一步是不是右移
					
				}
				else {
					n = (statusNode *)malloc(sizeof(statusNode));
					zuoyi(n, node->s, count, node->i, where0);
					count  ;
					insertListTail(open, *n);
					printState(node->i, node->s, n->i, n->s);
				}
				break;
			}
			}
		}

	}

	if (isSuccess) {
		printf("成功\n");
	}
	system("pause");
	return 0;
}
int NumberOfInvert(int s[]) {
	//求出数组中的逆序对的数目
	int count = 0;
	for (int i = 0; i < 8; i  ) {
		if (s[i] == 0) {
			continue;
		}
		for (int j = i   1; j < 9; j  ) {
			if (s[j] == 0) {
				continue;
			}

			if (s[i] > s[j]) {
				count  ;
			}
		}
	}
	return count;
}

bool isAimStatus(int s1[], int s2[]) {
	bool isEqual = true;
	for (int i = 0; i < 9; i  ) {
		if (s1[i]!=s2[i]) {
			isEqual = false;
			return isEqual;
		}
	}
	return isEqual;
}
void zuoyi(statusNode *node,int s[],int count,int parent,int where0) {
	node->i = count;
	for (int i = 0; i < 9; i  ) {
		node->s[i] = s[i];
	}
	node->parent = parent;
	node->next = NULL;
	node->wayOfBirth = 3;
	int temp;
	temp = node->s[where0];
	node->s[where0] = node->s[where0 - 1];
	node->s[where0 - 1] = temp;
}
void youyi(statusNode *node, int s[], int count, int parent, int where0) {
	node->i = count;
	for (int i = 0; i < 9; i  ) {
		node->s[i] = s[i];
	}
	node->parent = parent;
	node->next = NULL;
	node->wayOfBirth = 4;
	int temp;
	temp = node->s[where0];
	node->s[where0] = node->s[where0   1];
	node->s[where0   1] = temp;
}
void shangyi(statusNode *node, int s[], int count, int parent, int where0) {
	node->i = count;
	for (int i = 0; i < 9; i  ) {
		node->s[i] = s[i];
	}
	node->parent = parent;
	node->next = NULL;
	node->wayOfBirth = 1;
	int temp;
	temp = node->s[where0];
	node->s[where0] = node->s[where0 - 3];
	node->s[where0 - 3] = temp;
}
void xiayi(statusNode *node, int s[], int count, int parent, int where0) {
	node->i = count;
	for (int i = 0; i < 9; i  ) {
		node->s[i] = s[i];
	}
	node->parent = parent;
	node->next = NULL;
	node->wayOfBirth = 2;
	int temp;
	temp = node->s[where0];
	node->s[where0] = node->s[where0   3];
	node->s[where0   3] = temp;
}

void printState(int i, int start[], int j, int end[]) {
	printf("(%d)  ------------>   (%d)\n", i, j);
	for (int k = 0; k < 9; k =3) {
		printf("%d%d%d       %d%d%d\n", start[k], start[k   1], start[k   2], end[k], end[k   1], end[k   2]);
	}
	printf("\n");
	printf("\n");
}

/*
调试过程中发现的bug简记(实验报告再详细展开):
1.链表初始化问题。
2.链表的插入结点的传递问题。
3.从一个状态衍生出1-4个状态的选择问题的解决办法的思考过程。(switch case结构)。
4.序号问题的思考以及解决办法count变量的设置,和isSuccess变量出现以及放置位置的思考。
5.将stateNode放在switch前所出的问题以及解决办法。
6.每个case中的特色以及四个移位算法的想出。
7.每个case变量中if表达式里防止break所导致的问题以及解决办法。

ggs——2016/11/2
*/

实例下载地址

基于盲目搜索的宽度优先算法的八数码的解决办法

不能下载?内容有错? 点击这里报错 + 投诉 + 提问

好例子网口号:伸出你的我的手 — 分享

网友评论

发表评论

(您的评论需要经过审核才能显示)

查看所有0条评论>>

小贴士

感谢您为本站写下的评论,您的评论对其它用户来说具有重要的参考价值,所以请认真填写。

  • 类似“顶”、“沙发”之类没有营养的文字,对勤劳贡献的楼主来说是令人沮丧的反馈信息。
  • 相信您也不想看到一排文字/表情墙,所以请不要反馈意义不大的重复字符,也请尽量不要纯表情的回复。
  • 提问之前请再仔细看一遍楼主的说明,或许是您遗漏了。
  • 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦,又没人会搭理,于人于己都无利。

关于好例子网

本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享,对搜索内容的合法性不具有预见性、识别性、控制性,仅供学习研究,请务必在下载后24小时内给予删除,不得用于其他任何用途,否则后果自负。基于互联网的特殊性,平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查;无论平台是否已进行审查,用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场,基于网友分享,根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定,若资源存在侵权或相关问题请联系本站客服人员,点此联系我们。关于更多版权及免责申明参见 版权及免责申明

;
报警