深度优先算法解决八数码问题

首先我们来想象一只老鼠，在一座不见天日的迷宫内，老鼠在入口处进去，要从出 口出来。那老鼠会怎么走？当然是这样的：老鼠如果遇到直路，就一直往前走，如果遇到分叉路口，就任意选 择其中的一个继续往下走，如果遇到死胡同，就退回到最近的一个分叉路口，选择另一条道路再走下去，如果 遇到了出口，老鼠的旅途就算结束了。深度优先搜索法的基本原则就是这样：按照某种条件往前试探搜索，如 果前进中遭到失败（正如老鼠遇到死胡同）则退回头另选通路继续搜索，直到找到条件的目标为止。

实现这一算法，我们要用到编程的另一大利器--递归。递归是一个很抽象的概念， 但是在日常生活中，我们还是能够看到的。拿两面镜子来，把他们面对着面，你会看到什么？你会看到镜子中 有无数个镜子？怎么回事？A镜子中有B镜子的象，B镜子中有A镜子的象，A镜子的象就是A镜子本身的真实写 照，也就是说A镜子的象包括了A镜子，还有B镜子在A镜子中的象………………好累啊，又烦又绕口，还不好理 解。换成计算机语言就是A调用B，而B又调用A，这样间接的，A就调用了A本身，这实现了一个重复的功能。再 举一个例子；从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：从前有座山，山 里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：从前有座山，山里有座庙，庙里有个老和尚， 老和尚在讲故事，讲什么呢？讲：…………。好家伙，这样讲到世界末日还讲不玩，老和尚讲的故事实际上就 是前面的故事情节，这样不断地调用程序本身，就形成了递归。 万一这个故事中的某一个老和尚看这个故事不 顺眼，就把他要讲的故事换成：“你有完没完啊！”，这样，整个故事也就嘎然而止了。我们编程就要注意这 一点，在适当的时候，就必须要有一个这样的和尚挺身而出，把整个故事给停下来，或者使他不再往深一层次 搜索，要不，我们的递归就会因计算机存储容量的限制而被迫溢出，切记，切记。

我们把递归思想运用到上面的迷宫中，记老鼠现在所在的位置是(x,y),那它现在有 前后左右4个方向可以走，分别是(x+1,y),(x-1,y),(x,y+1),(x,y-1),其中一个方向是它来时的路，我们先不 考虑，我们就分别尝试其他三个方向，如果某个方向是路而不是墙的话，老鼠就向那个方向迈出一步。在新的 位置上，我们又可以重复前面的步骤。老鼠走到了死胡同又是怎么回事？就是除了来时的路，其他3个方向都是 墙，这时这条路就走到了尽头，无法再向深一层发展，我们就应该沿来时的路回去，尝试另外的方向。

例：八皇后问题：在标准国际象棋的棋盘上（88格）准备放置8只皇后，我们知 道，国际象棋中皇后的威力是最大的，她既可以横走竖走，还可以斜着走，遇到挡在她前进路线上的敌人，她 就可以吃掉对手。要求在棋盘上安放8只皇后，使她们彼此互相都不能吃到对方，求皇后的放法。

这是一道很经典的题目了，我们先要明确一下思路，如何运用深度优先搜索法，完 成这道题目。我们先建立一个88格的棋盘，在棋盘的第一行的任意位置安放一只皇后。紧接着，我们就来放 第二行，第二行的安放就要受一些限制了，因为与第一行的皇后在同一竖行或同一对角线的位置上是不能安放 皇后的，接下来是第三行，……，或许我们会遇到这种情况，在摆到某一行的时候，无论皇后摆放在什么位 置，她都会被其他行的皇后吃掉，这说明什么呢？这说明，我们前面的摆放是失败的，也就是说，按照前面 的皇后的摆放方法，我们不可能得到正确的解。那这时怎么办？改啊，我们回到上一行，把原先我们摆好的 皇后换另外一个位置，接着再回过头摆这一行，如果这样还不行或者上一行的皇后只有一个位置可放，那怎 么办？我们回到上一行的上一行，这和老鼠碰了壁就回头是一个意思。就这样的不断的尝试

八数码是一种数字游戏，游戏的最终目标是将随机排列的八个数字重新排列为1~8的顺序并留空一格。扭动数字的步数越少，意味着你的解题速度越快。相信很多人们玩八数码时都有过这样的一个问题，八数码为什么是9的阶乘？其实，这个问题的答案很简单。八数码的每个位置都有8种不同的数字选择，但是，棋盘上有一格是空的，因此总共的排列数量为8的阶乘，即8！。另外一种方法推导出来八数码总共的排列数量为9!-1，其中-1表示八数码被重排后不包括终止状态。这就是为什么可以玩好几十年不重复一种状态的原因。

#pragma warning(disable:4786)

#include <algorithm>

#include <cstdio>

#include <set>

#include <utility>

#include <ctime>

#include <cassert>

#include <cstring>

#include <iostream>

using namespace std;

/item记录搜索空间中一个结点

state 记录用整数形式表示的8数码格局

blank 记录当前空格位置，主要用于程序优化，

扩展时可不必在寻找空格位置

g, h 对应g(n), h(n)

pre 记录当前结点由哪个结点扩展而来 /

struct item

{

int state;

int blank;

int g;

int h;

int pre;

};

const int MAXSTEPS = 100000;

const int MAXCHAR = 100;

char buf[MAXCHAR][MAXCHAR]; //open表

item open[MAXSTEPS];

//vector<item> open;

int steps = 0;

//closed表，已查询状态只要知道该状态以及它由哪个结点扩展而来即可，用于输出路径

//每次只需得到对应f值最小的待扩展结点，用堆实现提高效率

pair<int, int> closed[MAXSTEPS];

//读入，将8数码矩阵格局转换为整数表示

bool read(pair<int,int> &state)

{

if (!gets(buf[0]))

return false;

if (!gets(buf[1]))

return false;

if (!gets(buf[2]))

return false;

//cout << strlen(buf[0]) << ' ' << strlen(buf[1]) << ' ' << strlen(buf[2]) << endl;

assert(strlen(buf[0]) == 5 && strlen(buf[1]) == 5 && strlen(buf[2]) == 5);

// astarin中的每行数据长度必须为5

statefirst = 0;

for (int i = 0, p = 1; i < 3; ++i)

{

for (int j = 0; j < 6; j += 2)

{

if (buf[i][j] == '0')

statesecond = i 3 + j / 2; // statesecond为0（空格）在节点中的位置

else

statefirst += p (buf[i][j] - '0');

p = 10;

}

}

/ 若初试节点为:

1 2 3

8 0 4

7 6 5

则statefirst为567408321，statesecond为4

/

return true;

}

//计算当前结点距目标的距离

int calculate(int current, int target) // return h=the sum of distances each block have to move to the right position,这里的each block不包括空格

{

int c[9], t[9];

int i, cnt = 0;

for (i = 0; i < 9; ++i)

{

c[current % 10] = t[target % 10] = i;

current /= 10;

target /= 10;

}

for (i = 1; i < 9; ++i)

cnt += abs(c[i] / 3 - t[i] / 3) + abs(c[i] % 3 - t[i] % 3);

return cnt;

}

//open表中结点间选择时的规则 f(n) = g(n) + h(n)

class cmp

{

public: inline bool operator()(item a, item b)

{

return ag + ah > bg + bh;

}

};

//将整数形式表示转换为矩阵表示输出

void pr(int state)

{

memset(buf, ' ', sizeof(buf));

for (int i = 0; i < 3; ++i)

{

for (int j = 0; j < 6; j += 2)

{

if (state % 10)

buf[i][j] = state % 10 + '0';

state /= 10;

}

buf[i][5] = '\0';

puts(buf[i]);

}

}

//用于判断当前空格是否可以向对应方向移动

inline bool suit(int a, int b) //空格移动后的坐标为(a,b)

{

return (a >= 0 && a < 3 && b >= 0 && b < 3);

}

//递归输出搜索路径

void path(int index)

{

if (index == 0)

{

pr(closed[index]first);

puts("");

return;

}

path(closed[index]second);

pr(closed[index]first); //将整数形式表示转换为矩阵表示输出

puts("");

++steps;

}

int getNixuNum( int state ) //求节点的逆序对数

{

int sum = 0;

int result[9];

memset( result, 0, sizeof(result) );

//cout << result[8] << result[7] << endl;

char buf[10];

itoa( state, buf, 10 );

//cout << buf << endl;

int k = 0;

while( buf[k] != '\0' )

{

result[9-k-1] = buf[k] - '0';

k++;

}

for( int i = 0; i < 9; i++ )

{

for( int j = i + 1; j < 9; j++ )

{

if( result[i] && result[j] && result[i] > result[j] )

{

sum++;

}

}

}

return sum; //返回33方格数组的逆序对数

}

int main()

{

//cout << getNixuNum(87654321);

//openresize(MAXSTEPS);

unsigned int t1 = clock();

//cout << opensize() << endl;

if( freopen("astarin", "r", stdin) == NULL )

{

cout << "file not find\n";

exit(0);

};

freopen("astar2out", "w", stdout);

set<int>states;

char tmp[100];

int i, x, y, a, b, nx, ny, end, next, index, kase = 0;

pair<int,int> start, target;

item head; //4个方向移动时的偏移量

const int xtran[4] = {-1, 0, 1, 0};

const int ytran[4] = {0, 1, 0, -1};

const int p[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};

while (read(start)) // 读取初试状态节点

{

unsigned int t2 = clock();

printf("Case %d:\n\n", ++kase);

gets(tmp);

read(target); // 读取目标状态节点

gets(tmp);

int targetNixuNum = getNixuNum(targetfirst);

//若两者的逆序对数不是同为奇数或同为偶数，则无解

if( !(getNixuNum(startfirst)&1 && targetNixuNum&1 || !(getNixuNum(startfirst)&1) && !(targetNixuNum&1)) )

{

cout << "无法从初始节点到终态节点\n";

exit(0);

}

//初始化open表，将初始状态加入

open[0]state = startfirst;

open[0]h = calculate(startfirst, targetfirst); // 计算当前节点到目标节点的估计距离

open[0]blank = startsecond;

open[0]pre = -1; // 初始节点无父节点

open[0]g = 0; // 初始节点的g为0

index = 0;

statesinsert(startfirst); // 扩展过节点保存在states中，即出现过的状态保存在states中，states为set<int>类型，其中的states中的元素唯一

//提取open表中f值最小元素放入closed表，并对该结点进行扩展

for (end = 1; end > 0; ++index) // end为open表中的元素个数，一直循环到open表为空

{

assert(index < MAXSTEPS);

//临时存储

head = open[0]; // 由于使用pop_heap函数和push_heap函数，所以open[0]为g+h最小的元素

//放入closed表记录当前格局和由哪个结点扩展而来（该结点肯定已在closed表中）

closed[index]first = open[0]state; //放入close表中，表示已经扩展完的节点，下面的for循环会扩展其节点

closed[index]second = open[0]pre; // index表示当前close表中当前扩展节点的下标

//从open表中删除该结点

pop_heap(open, open + end, cmp());//为algorithm文件中的函数，第一个参数指定开始位置，第二个指定结束，第三个指定比较函数

--end;

//得到结果，递归输出路径

if (headstate == targetfirst)

{

path(index);

break;

}

x = headblank / 3;

y = headblank % 3; //空格在33方格中的x,y坐标

/

|2 0 3|

A = |1 8 4|

|7 6 5| // 看成33的数组

则headblank=1

x=0,y=1,即空格的在33的数组中下标为(0,1)

/

for (i = 0; i < 4; ++i)

{

nx = x + xtran[i];

ny = y + ytran[i];

/

i=0时：(nx,ny）为当前空格向上移动一格后的坐标

i=1时：(nx,ny）为当前空格向右移动一格后的坐标

i=2时：(nx,ny）为当前空格向下移动一格后的坐标

i=3时：(nx,ny）为当前空格向左移动一格后的坐标

/

if (suit(nx, ny)) // 判断是否能够移动

{

a = headblank; // 空格当前位置,以上面矩阵A为例，a=1

b = nx 3 + ny; // 空格移动后的新位置,开始是能够向右边移动，故b=03+2=2

//调换十进制表示整数对应两个数字位

next = headstate + ((headstate % p[a + 1]) / p[a] - (headstate % p[b + 1]) / p[b]) p[b] + ((headstate % p[b + 1]) / p[b] - (headstate % p[a + 1]) / p[a]) p[a];

// 如headstate=567481302,空格向右移动一次后，next=567481032,即为移动后的节点

// 判断能否由当前节点到达目标节点

if( ( getNixuNum(next)&1 && targetNixuNum&1 ) || ( !(getNixuNum(next)&1) && !(targetNixuNum&1) ) )

{

//判断是否已经扩展过，即已经出现过

if (statesfind(next) == statesend()) //没出现就保存一下，也存入open表

{

statesinsert(next);

open[end]pre = index; //扩展后的子节点，其父节点为当前扩展节点

open[end]blank = b;

open[end]state = next;

open[end]h = calculate(next,targetfirst);

open[end]g = headg + 1;

++end; //open表中元素加1

push_heap(open, open + end, cmp()); //压入堆中

}

}

}

}

}

if (end <= 0)

puts("No solution");

else

{

printf("Num of steps: %d\n", steps);

printf("Num of expanded: %d\n", index);

printf("Num of generated: %d\n", index + end);

printf("Time consumed: %d\n\n", clock() - t2);

}

statesclear();

steps = 0;

}

printf("Total time consumed: %d\n", clock() - t1);

return 0;

}

广度优先搜索法

在搜索法中，广度优先搜索法是寻找最短路经的首选。

1广度优先搜索算法的基本步骤

1）建立一个队列，将初始结点入队，并设置队列头和尾指针

2）取出队列头（头指针所指）的结点进行扩展，从它扩展出子结点，并将这些结点按扩展的顺序加入队列。

3）如果扩展出的新结点与队列中的结点重复，则抛弃新结点，跳至第六步。

4）如果扩展出的新结点与队列中的结点不重复，则记录其父结点，并将它加入队列，更新队列尾指针。

5）如果扩展出的结点是目标结点，则输出路径，程序结束。否则继续下一步。

6）如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。

2搜索路径的输出

搜索到目标结点后，需要输出搜索的路径。每个结点有一个数据域last，它记录了结点的父结点，因此输出搜索路径时，就是从目标结点Q出发，根据last找到它的父结点，再根据这个结点的last找到它的父结点，,最后找到初始结点。搜索的路径就是从初始结点循相反方向到达目标结点的路径。

以上就是关于深度优先算法解决八数码问题全部的内容，包括:深度优先算法解决八数码问题、八数码为什么是9的阶乘、问： 40 人工智能及其应用期末作业 用A*算法解决下面的八数码难题。试定义估价函数，启发函数，等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！