一、 实验目的
熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用 A*算法求解迷宫问题，理解求解流程和搜索顺序。
二、 实验内容
迷宫问题可以表述为：一个二维的网格，0表示点可走，1表示点 不可以走，点用（x，y）表示，寻从某一个给定的起始单元格出发， 经由行相邻或列相邻的单元格（可以通过的），最终可以到达目标单元 格的、所走过的单元格序列。在任一个单元格中，都只能看到与它邻 近的4个单元格（如果位于底边，则只有3个；位于4个角上，则只 有2个是否能通过）。 A*算法是人工智能中的一种搜索算法，是一种启发式搜索算法， 它不需遍历所有节点，只是利用包含问题启发式信息的评价函数对节 点进行排序，使搜索方向朝着最有可能到目标并产生最优解的方 向。它的独特之处是检查最短路径中每个可能的节点时引入了全局信 息，对当前节点距终点的距离做出估计，并作为评价节点处于最短路 线上的可能性的度量。 数据存储安全检测
A*算法中引入了评估函数，评估函数为：f（n）=g（n）+h河灯怎么做（n）
其中：n是搜索中遇到的任意状态°g（n）是从起始状态到n的代价。
h（n）无水氯化镁是对n到目标状态代价的启发式估计。即评估函数f （ n）是从初 始节点到达节点n处已经付出的代价与节点n到达目标节点的接近 程度估价值的总和。
这里我们定义n点到目标点的最小实际距离为h(n)*，A*算法 要满足的条件为：h(n)<=h(n)*
迷宫走的时候只能往上下左右走，每走一步，代价为虹吸式咖啡壶1,这里我
们采用的估价函数为当前节点到目标节点的曼哈顿距离，即：
h (物联网实验设备n) =| - |+ | - |
这里end表示迷宫的目标点，n表示当前点，很明显这里h (n)
<=h (n) *。
g (n)容易表示，即每走一步的代价是1，所以利用f (n) =g (n) +h (n)这种策略，我们可以不
断地逼近目标点，从而到问题的解。
时间复杂度：m行n列的迷宫矩阵实现算法的时间复杂度为O(m*n).
实验结果：
■ ' C:\US "
输入二迷宫左边长，上边宽，例如：驰蜀
9 8
从下一行刑含输入迷宫信息：
0 0 1 0 0 0 10 0 1 0 0 0 1 0
^6001101 0 1110010
9QQ1&QQQ ^1000101
B1111001 t 1 0 0 0 1
riV 0 a 0 葡入瞳点坐标.目标点坐标，例如H 1 30 20 119 8 T 遍用旺算法打段结果如R 1?>,<7,7>,<8,7>,<9,7>,<9,8> 宣共是了出步 Press any key to continue
实验源码：
#include <queue>
#include <vector>
$电容器串联
#include <iostream>
using namespace std;
int direc [4] [2]={{0,1},{-1,0},{0,-1},{1,0}};
enum Flag
SEAL,
OPEN,
UNVISITED
&
};
typedef struct node
{
int _x,_y; oint!=NULL)
{
delete _seal[i][j].point;
}
}
}
for(i=0;i<=_len;++i)
{
delete []_seal[i];
delete []_maze[i];
}
delete []_seal;
delete []_maze;
void input()
{
cout<<"输入：迷宫左边长，上边宽！例如：30 20"<<endl;
cin>>_len>>_wid;
_seal=new Seal*[_len+1];
_maze=new unsigned char*[_len+1];
for(int i=0;i<=_len;++i)
{
_seal[i]=new Seal[_wid+1];
_maze[i]=new unsigned char[_wid+1];
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议