人工智能常见知识点⑨

一．实验目的：

1. 通过实例开发，熟悉启发式搜索算法。

2. 掌握启发式搜索算法的应用

二．实验设备：

电脑

相应的开发软件Visual C++ 6.0

……

三．实验要求：

问题描述

1. 坐标访问和父节点查找约定顺序：右，右上，上，左上，左，左下，下，右下，沿X轴增加的方向为右，沿Y轴增加的方向为上，父节点可能会有多个，这里选择代价最小最后搜索的为父节点。

坐标A(2，2)，目标坐标B(6，3)，已经对坐标A*进行了估值。使用启发式搜索算法的求解问题。

计算从初始节点到目标节点的各个F 、 G和H值，并给出最优路径。

H = 从指定的方格移动到终点 B 的估算成本。计算从当前方格横向或纵向移动到达目标所经过的方格数，忽略对角移动，然后把总数乘以 10

因此H = （（6-2）+（3-2））* 10 = 50

移动轨迹如下：

G 值计算，计算K到A的最小估价我们只需要计算K点的周围八个点，其中最小估价即为K点的值，这个点我们称为K点的父节点。k点正在访问，那么它周围至少有一个点已经被访问了

F = 14 + 10*3 = 44

选作：

编程实现A*搜索算法程序求解上题中的问题；

四．实验步骤：

1． *****实现

附上代码如下：

package 人工智能.ch5;
import java.util.Scanner;
/**
 * A*算法解决最小估价路径算法
 */
public class ch5 {
 // 起点X,Y坐标
 public static int X,Y;
 // 终点坐标
 public static int f_x,f_y;
 // 最小估价距离
 public static int result;
 //用户输入起点位置和终点位置
 public static void scan() {
 Scanner scanner = new Scanner(System.in);
 X = scanner.nextInt();
 Y = scanner.nextInt();
 f_x = scanner.nextInt();
 f_y = scanner.nextInt();
 System.out.println("首先起点位置: ("+X+", "+Y+"),终点位置: ("+f_x+", "+f_y+")");
 }
 // 寻找最小代价路径
 public static int ASearch(){
 // 如果刚好处于左右上下角，则估价为14
 if(Math.abs(X-f_x)==1&&Math.abs(Y-f_y)==1){
 result = 14;
 }
 // 如果刚好处于同一直线上
 else if (Math.abs(X-f_x)==0||Math.abs(Y-f_y)==0){
 // 起点和终点重合
 if (Math.abs(X-f_x)==0&&Math.abs(Y-f_y)==0){
 System.out.println("起点和重点重合拉!");
 result = 0;
 }
 // 都处于垂直X轴的某条直线
 else if(Math.abs(X-f_x)==0){
 result = Math.abs(Y-f_y)*10;
 }
 // 都处于垂直Y轴的某条直线
 else if (Math.abs(Y-f_y)==0){
 result = Math.abs(X-f_x)*10;
 }
 }
 else{
 result += Math.abs(Y-f_y)*14;
 result += (Math.abs(X-f_x)-1)*10;
 }
 return result;
 }
 public static void main(String[] args) {
 // 初始化起点和终点
 scan();
 // 找到最小估价路径
 ch5.result = ASearch();
 System.out.println("最小估价为："+result);
 }
}

2． 测试*****

五．实验结果

5.1 实验输入和输出

输入起点和终点坐标：3 3 7 4

输出最小估价路径距离：44

5.2 实验截图

六、实验结果分析与讨论

本次实验还可以耐人考虑，值得回味。

A*（A-star）搜索算法是一种在图形搜索中找到最短路径的算法。这是一种启发式搜索算法，因为它使用了一个启发式函数来指导搜索过程，从而加速找到解决方案。A*算法结合了最佳先搜索（利用启发式函数）和Dijkstra算法（考虑从起点到当前节点的已知最短路径）的特点。

A*算法的工作原理如下：

1. 维护两个集合：开放集（open set）和关闭集（closed set）。开放集包含待检查的节点，关闭集包含已检查的节点。
2. 初始化：将起点添加到开放集，并为其计算启发式值（通常是从起点到终点的估计距离）。
3. 循环以下步骤，直到找到目标节点或开放集为空： a. 从开放集中选择具有最低f(n)值的节点n，其中f(n) = g(n) + h(n)。g(n)是从起点到节点n的实际距离，h(n)是从节点n到终点的启发式估计（启发式函数）。 b. 将节点n从开放集移动到关闭集。 c. 如果节点n是目标节点，则构建从起点到目标节点的路径并退出循环。 d. 否则，检查节点n的所有邻居。对于每个邻居，如果它尚未在开放集或关闭集中，则将其添加到开放集，并计算其g(n)、h(n)和f(n)值。如果邻居已在开放集中，并且新路径的g值较小，则更新其g值和f值。
4. 如果未找到目标节点且开放集为空，则表示不存在路径。

A算法的性能取决于所选的启发式函数。一个好的启发式函数应该是一个可接受的启发式函数，这意味着它不会过高估计从任何节点到目标节点的实际距离。当启发式函数满足这一条件时，A算法保证找到最短路径。

常见的启发式函数包括曼哈顿距离（适用于网格）和欧几里得距离（适用于连续空间）。在实际应用中，可以根据问题类型选择合适的启发式函数。

我正在参与2024腾讯技术创作特训营第五期有奖征文，快来和我瓜分大奖！