基本信息
源码名称：基于盲目搜索的宽度优先算法的八数码的解决办法
源码大小：2.19M
文件格式：.zip
开发语言：C/C++
更新时间：2016-12-12
×
请留下您的邮箱，我们将在2小时内将文件发到您的邮箱
源码介绍
// 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
*/