八数码问题C语言A星算法详细实验报告含代码(2)

可以在运行程序前检查初始状态和目标状态的排序的奇偶行是否相同，相同则问题可解，应当能搜索到路径。否则无解。

七、源程序及注释

#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; // 深度

int index; // 索引值 } Node;

Node src, dest;

vectornode_v; // 储存节点

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

return 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) { 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<< \<

void Swap(int& a, int& b) { //交换 int t; 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; i

else if ((node_v[i].dist + node_v[i].dep)

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

returnloc; }

boolisExpandable(Node& node) { //判断是否可扩展 for (inti = 0; i

return 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; 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; }

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); 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;

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 = Distance(node_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() { int number;

cout<< \输入初始状态:\for (inti = 0; i< ROW; i++) for (int j = 0; j < COL; j++) { cin>> number;

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

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

cout<< \输入目标状态\for (int m = 0; m < ROW; m++) for (int n = 0; n < COL; n++) { cin>> number;

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

node_v.push_back(src);

while (1) {

if (isEmptyOfOPEN()) { cout<< \找不到解!\return -1; } else {

intloc; // the location of the minimize node loc = GetMinNode();

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

cout<< \初始状态：\cout<

PrintSteps(loc, rstep_v); cout<< \成功!\break; } else

ProcessNode(loc); } }

return 0; }