用A算法解决八数码问题之欧阳美创编

2021.01.01

用A*算法解决八数码问题

一、

时间：2021.01.01 创作：欧阳美 二、 题目：八数码问题也称为九宫问题。在3×3的棋盘，

有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要解决的问题是：任意给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。

三、

问题的搜索形式描述

状态：状态描述了8个棋子和空位在棋盘的9个方格上的分布。

初始状态：任何状态都可以被指定为初始状态。 操作符：用来产生4个行动（上下左右移动）。 目标测试：用来检测状态是否能匹配上图的目标布局。 路径费用函数：每一步的费用为1，因此整个路径的费用是路径中的步数。

现在任意给定一个初始状态，要求找到一种搜索策略，用尽可能少的步数得到上图的目标状态算法介绍

三、解决方案介绍

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

1.A*算法的一般介绍

A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即

fgnsqrtdxnx*dxnxdyny*dyny；

这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于盲目搜索策略。

A star算法在静态路网中的应用

2.算法伪代码

创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。算起点的估价值，将起点放入OPEN表。 while(OPEN!=NULL) {

从OPEN表中取估价值f最小的节点n; if(n节点==目标节点) {break;}

for(当前节点n 的每个子节点X) {

算X的估价值;

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

if(X in OPEN) {

if( X的估价值小于OPEN表的估价值 ) {把n设置为X的父亲;

更新OPEN表中的估价值; //取最小路径的估价值} }

if(X inCLOSE) {

if( X的估价值小于CLOSE表的估价值 ) {把n设置为X的父亲;

更新CLOSE表中的估价值;

把X节点放入OPEN //取最小路径的估价值} }

if(X not inboth) {把n设置为X的父亲; 求X的估价值;

并将X插入OPEN表中; //还没有排序} }//end for

将n节点插入CLOSE表中;

按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

进行。

}//end while(OPEN!=NULL)

保存路径，即 从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径.

源程序

#include #include #include using namespace std; constint ROW = 3; constint COL = 3;

constint MAXDISTANCE = 10000; constint MAXNUM = 10000; int abs(int a) {

if (a>0) return a; else return -a; }

typedefstruct _Node{ int digit[ROW][COL]; intdist; // 距离 intdep; // 深度

欧阳美创编 2021.01.01 2021.01.01

欧阳美创编

四、 欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

int index; // 索引值 } Node;

Node src, dest;

vectornode_v; // 储存节点

boolisEmptyOfOPEN() { //判断Open表是否空 for (inti = 0; ireturn true; }

boolisEqual(int index, int digit[][COL]) {//判断节点是否与索引值指向的节点相同

for (inti = 0; i< ROW; i++) for (int j = 0; j < COL; j++) { if

(node_v[index].digit[i][j]

!=

digit[i][j])

return false; }

return true; }

ostream& operator<<(ostream&os, Node& node)

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

{

for (inti = 0; i< ROW; i++) { for (int j = 0; j < COL; j++) os<returnos; } void

PrintSteps(int

index,

vector&rstep_v){//输出步骤

rstep_v.push_back(node_v[index]); index = node_v[index].index; while (index != 0) {

rstep_v.push_back(node_v[index]); index = node_v[index].index; }

for (inti = rstep_v.size() - 1; i>= 0; i--) cout<< \"Step \" <void Swap(int& a, int& b) { //交换 int t;

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

t = a; a = b; b = t; }

void Assign(Node& node, int index) {//获取节点

for (inti = 0; i< ROW; i++) for (int j = 0; j < COL; j++) node.digit[i][j] node_v[index].digit[i][j];

}

intGetMinNode() {//获取启发值最小的节点 intdist = MAXNUM;

intloc; // the location of minimize node for (inti = 0; ielse if ((node_v[i].dist + node_v[i].dep) loc = i;

dist = node_v[i].dist + node_v[i].dep; }

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

=

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

}

returnloc; }

boolisExpandable(Node& node) {//判断是否可扩展

for (inti = 0; ireturn true; }

int Distance(Node& node, int digit[][COL]) {//计算距离

int distance = 0; bool flag = false;

for(inti = 0; i< ROW; i++) for (int j = 0; j < COL; j++) for (int k = 0; k < ROW; k++) { for (int l = 0; l < COL; l++) {

if (node.digit[i][j] == digit[k][l]) { distance += abs(i - k) + abs(j - l); flag = true;

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

break; } else

flag = false; } if (flag) break; }

return distance; }

intMinDistance(int a, int b) {//二者取小 return (a < b ? a : b); }

void ProcessNode(int index) {//展开节点 int x, y; bool flag;

for (inti = 0; i< ROW; i++) { for (int j = 0; j < COL; j++) { if (node_v[index].digit[i][j] == 0) { x =i; y = j; flag = true; break;

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

}

else flag = false; } if(flag) break; }

Node node_up; //上移操作 Assign(node_up, index); intdist_up = MAXDISTANCE; if (x > 0) {

Swap(node_up.digit[x][y], node_up.digit[x - 1][y]);

if (isExpandable(node_up)) {

dist_up = Distance(node_up, dest.digit); node_up.index = index; node_up.dist = dist_up;

node_up.dep = node_v[index].dep + 1; node_v.push_back(node_up); } }

Node node_down; //下移操作 Assign(node_down, index);

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

intdist_down = MAXDISTANCE; if (x < 2) {

Swap(node_down.digit[x][y], node_down.digit[x + 1][y]);

if (isExpandable(node_down)) {

dist_down = Distance(node_down, dest.digit); node_down.index = index; node_down.dist = dist_down;

node_down.dep = node_v[index].dep + 1; node_v.push_back(node_down); } }

Node node_left;//左移操作 Assign(node_left, index); intdist_left = MAXDISTANCE; if (y > 0) {

Swap(node_left.digit[x][y], node_left.digit[x][y - 1]);

if (isExpandable(node_left)) {

dist_left = Distance(node_left, dest.digit); node_left.index = index; node_left.dist = dist_left;

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

node_left.dep = node_v[index].dep + 1; node_v.push_back(node_left); } }

Node node_right; //右移操作 Assign(node_right, index); intdist_right = MAXDISTANCE; if (y < 2) {

Swap(node_right.digit[x][y], node_right.digit[x][y + 1]);

if (isExpandable(node_right)) { dist_right dest.digit);

node_right.index = index; node_right.dist = dist_right;

node_right.dep = node_v[index].dep + 1; node_v.push_back(node_right); } }

node_v[index].dist = MAXNUM; }

int main() {

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

= Distance(node_right,

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

int number;

cout<< \"输入初始状态:\" <> number;

src.digit[i][j] = number; }

src.index = 0; src.dep = 1;

cout<< \"输入目标状态\" <> number;

dest.digit[m][n] = number; }

node_v.push_back(src); while (1) {

if (isEmptyOfOPEN()) { cout<< \"找不到解!\" <欧阳美创编 2021.01.01 2021.01.01

欧阳美创编

欧阳美创编 2021.01.01 欧阳美创编

2021.01.01

intloc; // the location of the minimize node

loc = GetMinNode();

if(isEqual(loc, dest.digit)) { vectorrstep_v;

cout<< \"初始状态：\" <PrintSteps(loc, rstep_v); cout<< \"成功!\" <ProcessNode(loc); } }

return 0; }

时间：2021.01.01 创作：欧阳美 欧阳美创编 2021.01.01 欧阳美创编

2021.01.01