数据结构课设实验二:隐式图的搜索问题

2024-03-28 20:38

本文主要是介绍数据结构课设实验二:隐式图的搜索问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

隐式图的搜索问题

  • 一、实验内容
  • 二、实验提示
  • 三、实验代码
  • 4、实验结果

一、实验内容

编写九宫重排问题的启发式搜索(A*算法)求解程序。
在3х3组成的九宫棋盘上,放置数码为1~8的8个棋子,棋盘中留有一个空格,空格周围的棋子可以移动到空格中,从而改变棋盘的布局。根据给定初始布局和目标布局,编程给出一个最优的走法序列。输出每个状态的棋盘
测试数据:初始状态:123456780 目标状态:012345678
【输入格式】
输入包含三行,每行3各整数,分别为0-8这九个数字,以空格符号隔开,标识问题的初始状态。0表示空格,例如:
2 0 3
1 8 4
7 6 5

在这里插入图片描述

二、实验提示

对于九宫重排问题的解决,首先要考虑是否有答案。每一个状态可认为是一个1×9的矩阵,问题即通过矩阵的变换,可以变换为目标状态对应的矩阵。由数学知识可知,可计算这两个有序数列的逆序值,如果两者都是偶数或奇数,则可通过变换到达,否则,这两个状态不可达。这样,就可以在具体解决问题之前判断出问题是否可解,从而可以避免不必要的搜索。
如果初始状态可以到达目标状态,那么采取什么样的方法呢?常用的状态空间搜索有深度优先和广度优先。广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法,可是当状态空间十分大,且不预测的情况下就不可取了。他的效率实在太低,甚至不可完成。由于九宫重排问题状态空间共有9!个状态,如果选定了初始状态和目标状态,有9!/2个状态要搜索,考虑到时间和空间的限制,在这里要求采用A算法求解。
A
算法是启发式搜索算法,启发式搜索就是在状态空间中对每一个搜索分支进行评估,得到最好的分支,再从这个分支进行搜索直到目标。这样可以省略大量无畏的搜索路径,提到了效率。在启发式搜索中,利用当前与问题有关的信息作为启发式信息指导搜索,这些信息能够有效省略大量无谓的搜索路径,大大提高了搜索效率。
启发式搜索算法定义了一个估价函数f(n),与问题相关的启发式信息都被计算为一定的 f(n) 的值,引入到搜索过程中。f(n) = g(n) +h(n)其中f(n) 是节点n的估价函数,g(n)是在状态空间中从初始节点到节点n的实际代价,h(n)是从节点n到目标节点最佳路径的估计代价。 在九宫重排问题中,显然g(n)就是从初始状态变换到当前状态所移动的步数,估计函数h(n)估计的是节点n到目标节点的距离,我们可以用欧几里德距离、曼哈顿距离或是两节的状态中数字的错位数来估计。

1、存储结构的定义
typedef struct node//八数码结构体
{
int nine[N][N];//数码状态
int f;//估价值
int direct;//空格移动方向
struct node *parent;//父节点
}pNode;
2、启发式搜索算法的描述:
(1)把初始节点S0 放入Open表中,f(S0)=g(S0)+h(S0);
(2)如果Open表为空,则问题无解,失败退出;
(3)把Open表的第一个节点取出放入Closed表,并记该节点为n;
(4)考察节点n是否为目标节点。若是,则找到了问题的解,成功退出;
(5)若节点n不可扩展,则转到第(2)步;
(6)扩展节点n,生成子节点ni(i=1,2,……),计算每一个子节点的估价值f(ni) (i=1,2,……),并为每一个子节点设置指向父节点的指针,然后将这些子节点放入Open表中;
(7)根据各节点的估价函数值,对Open表中的全部节点按从小到大的顺序重新进行排序;
(8)转到第(2)步。
启发式搜索算法的工作过程:
在这里插入图片描述

三、实验代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;struct node {int nine[3][3];//数码状态  int f;         //估价值int direct;     //记录深度node* parent;  //父节点node(int direct) :direct(direct) {}bool operator == (node& q) {          //判断两个状态对应位置元素是否完全相等for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {if (nine[i][j] != q.nine[i][j])return false;}}return true;}node& operator = (node& p) //以状态p为当前状态赋值,对应位置元素相同
{         for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {nine[i][j] = p.nine[i][j];}}return *this;}
};int Pos[9] = { 4, 0, 1, 2, 5, 8, 7, 6, 3 };//每一位是某个数字应该在的位置所代表的数,除3和对3取余可以求出行列void print(node* p) 
{         for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++)cout << "    " << p->nine[i][j] << " ";cout << endl;}cout << endl;
}int geth(node& p) //计算p的h值。
{             int h = 0;for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) if (p.nine[i][j] != 0)h += abs(Pos[p.nine[i][j]] / 3 - i) + abs(Pos[p.nine[i][j]] % 3 - j);}return h;
}int find0(node& p) 
{               for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) if (p.nine[i][j] == 0)return i * 3 + j;
}int f(node* p) //计算f()
{               return geth(*p) + p->direct;
}bool cmp(node* p, node* q) //比较两个状态的f值
{       return f(p) > f(q);
}vector<node*> open;         //open表
vector<node*> close;        //close表vector<node*>::iterator look_up_dup(vector<node*>& vec, node* p) 
{vector<node*>::iterator it = vec.begin();for (; it < vec.end(); it++) if ((*(*it)) == *p) break;return it;
}node* search(node& s) //A*算法
{      int deep = 0;open.push_back(&s);while (!open.empty()) {sort(open.begin(), open.end(), cmp);//对open表中的元素进行排序node* p = open.back();open.pop_back();if (geth(*p) == 0)return p;           //所有数到达目标位置,搜索过程结束deep = p->direct + 1;int zeroPos = find0(*p);int x = zeroPos / 3;int y = zeroPos % 3;for (int i = 0; i < 4; i++) //上下左右四个方向{  int x_offset = 0, y_offset = 0;switch (i) {case 0:x_offset = 0, y_offset = 1; break;   //右case 1:x_offset = 0, y_offset = -1; break;  //左case 2:x_offset = 1, y_offset = 0; break;   //上case 3:x_offset = -1, y_offset = 0; break;  //下};if (x + x_offset < 0 || x + x_offset >= 3 || y + y_offset < 0 || y + y_offset >= 3)continue;node* q = new node(deep);q->parent = p;*q = *p;q->nine[x][y] = q->nine[x + x_offset][y + y_offset];q->nine[x + x_offset][y + y_offset] = 0;bool skip = 0;vector<node*>::iterator dup = look_up_dup(open, q);if (dup != open.end()) {if (f(q) < f(*dup)) {(*dup)->direct = q->direct;(*dup)->parent = q->parent;}skip = 1;}dup = look_up_dup(close, q);if (dup != close.end()) {if (f(q) < f(*dup)) {delete* dup;close.erase(dup);open.push_back(q);skip = 1;}}if (!skip) {open.push_back(q);}}close.push_back(p);}
}void printAn(node* p)       //输出解路径
{vector<node*> trace;while (p) {trace.push_back(p);p = p->parent;}int count = 0;while (!trace.empty()) {cout << "----------step" << count << "------------" << endl;cout << endl;print(trace.back());cout << "f:" << f(trace.back()) << "     g:" << count << "      h:" << geth(*trace.back()) << endl << endl;trace.pop_back();count++;}
}int main()
{node p(0);p.nine[0][0] = 2;//设置初始状态p.nine[0][1] = 0;p.nine[0][2] = 3;p.nine[1][0] = 1;p.nine[1][1] = 8;p.nine[1][2] = 4;p.nine[2][0] = 7;p.nine[2][1] = 6;p.nine[2][2] = 5;p.parent = NULL;node* q;q = search(p);printAn(q);system("pause");
}

4、实验结果

在这里插入图片描述

这篇关于数据结构课设实验二:隐式图的搜索问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/856639

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close