实例介绍
【实例简介】
【实例截图】
【实例截图】
【核心代码】
// 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
*/
好例子网口号：伸出你的我的手 — 分享！
小贴士
感谢您为本站写下的评论，您的评论对其它用户来说具有重要的参考价值，所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字，对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙，所以请不要反馈意义不大的重复字符，也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明，或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦，又没人会搭理，于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享，对搜索内容的合法性不具有预见性、识别性、控制性，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论平台是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定，若资源存在侵权或相关问题请联系本站客服人员，点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论