A*算法求解迷宫寻路问题实验

这篇具有很好参考价值的文章主要介绍了A*算法求解迷宫寻路问题实验。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、实验目标:

熟悉和掌握A*算法实现迷宫寻路功能,要求掌握启发式函数的编写以及各类启发式函数效果的比较。

二、实验内容与完成情况:

寻路问题常见于各类游戏中角色寻路、三维虚拟场景中运动目标的路径规划、机器人寻路等多个应用领域。迷宫寻路问题是在以方格表示的地图场景中,对于给定的起点、终点和障碍物(墙),如何找到一条从起点开始避开障碍物到达终点的最短路径。

假设在一个n×m 的迷宫里,入口坐标和出口坐标分别为(1,1)和(5,5) ,每一个坐标点有两种可能:0或1,其中0表示该位置允许通过,1表示该位置不允许通过。

如地图:

0 0 0 0 0

1 0 1 0 1

0 0 1 1 1

0 1 0 0 0

0 0 0 1 0

最短路径应该是:

A B 0 0 0

1 C 1 0 1

E D 1 1 1

F 1 J K L

G H I 1 M

即:(1,1)-(1,2)-(2,2) -(3,2)-(3,1)-(4,1)-(5,1)-(5,2)-(5,3)-(4,3)-(4,4)-(4,5) -(5,5)

以寻路问题为例实现A昇法的水解程序(编程语言不限),要求设计两种不同的估价函数。

实验要求:

1.画出用A”算法求解迷宫最短路径的流程图。

2.设置不同的地图,以及不同的初始状态和目标状态,记录A`算法的求解结果,包括最短路径、扩展节点数、生成节点数和算法运行时间。

3.对于相同的初始状态和目标状态,设计不同的启发式函数,比较不同启发式函数对迷宫寻路速度的提升效果,包括扩展节点数、生成节点数和算法运行时间。

三、实验步骤与结果:

首先在5×5的地图上实现A*算法:

1、根据A*算法的特点:f(n) = g(n) + h(n),需要设计两个函数来满足A*算法。

g(n)为起点到当前点的距离

h(n)是对当前方格到目的地方格距离的估算,估算方法设计两种:

  • 曼哈顿距离
  • 欧几里得距离

2、定义一个地图

A*算法求解迷宫寻路问题实验

3、创建Openlist和Closelist,由于在本实验中,设定的移动方向只有上、下、左、右,所以第一步从起始点开始判断。

将起始点放入Openlist和Closelist中,从起始点开始判断其周围可以到达的方格点,将当前点从Openlist中移除,找到周围f最小的方格点。

A*算法求解迷宫寻路问题实验

将其放入Openlist中,然后将当前点放入Closelist中,Closelist中的方格点不可再访问,所以需要在更新函数上增加对周围方格点是否在Closelist的判断。

当移动到f最小的点后,重复上述操作。

4、 5×5实验结果如下:

采用欧几里得距离时:

A*算法求解迷宫寻路问题实验

采用曼哈顿距离时:

A*算法求解迷宫寻路问题实验

通过实验结果我们可以看到,在地图为5×5大小时,扩展节点数,生成节点数和算法时间没有明显的差距。

5、下面通过20×20的地图进行比较:

     A*算法求解迷宫寻路问题实验

曼哈顿距离函数:

A*算法求解迷宫寻路问题实验

点的移动轨迹为:

[1,1]-->[2,1]-->[3,1]-->[4,1]-->[4,2]-->[4,3]-->[3,3]-->[3,4]-->[3,5]-->[4,5]-->[5,5]-->[6,5]-->[7,5]-->[8,5]-->[9,5]-->[9,6]-->[9,7]-->[9,8]-->[9,9]-->[9,10]-->[9,11]-->[10,11]-->[10,12]-->[10,13]-->[9,13]-->[9,14]-->[9,15]-->[10,15]-->[11,15]-->[12,15]-->[13,15]-->[13,14]-->[12,14]-->[12,13]-->[12,12]-->[12,11]-->[12,10]-->[12,9]-->[12,8]-->[12,7]-->[13,7]-->[14,7]-->[15,7]-->[16,7]-->[16,6]-->[16,5]-->[16,4]-->[17,4]-->[18,4]-->[19,4]-->[19,5]-->[19,6]-->[19,7]-->[20,7]-->[20,8]-->[19,8]-->[19,9]-->[18,9]-->[18,10]-->[18,11]-->[19,11]-->[19,12]-->[18,12]-->[18,13]-->[18,14]-->[19,14]-->[20,14]-->[20,15]-->[19,15]-->[19,16]-->[19,17]-->[18,17]-->[18,18]-->[18,19]-->[18,20]-->[19,20]-->[20,20]

欧几里得函数:

A*算法求解迷宫寻路问题实验

点的移动轨迹为:

[1,1]-->[2,1]-->[3,1]-->[4,1]-->[4,2]-->[4,3]-->[3,3]-->[3,4]-->[3,5]-->[4,5]-->[5,5]-->[6,5]-->[6,6]-->[7,6]-->[7,7]-->[8,7]-->[8,8]-->[9,8]-->[9,9]-->[9,10]-->[9,11]-->[10,11]-->[10,12]-->[10,13]-->[9,13]-->[9,14]-->[9,15]-->[10,15]-->[11,15]-->[12,15]-->[13,15]-->[13,14]-->[12,14]-->[12,13]-->[12,12]-->[12,11]-->[12,10]-->[12,9]-->[12,8]-->[12,7]-->[13,7]-->[14,7]-->[15,7]-->[16,7]-->[16,6]-->[16,5]-->[16,4]-->[17,4]-->[18,4]-->[19,4]-->[19,5]-->[19,6]-->[19,7]-->[19,8]-->[19,9]-->[18,9]-->[18,10]-->[18,11]-->[18,12]-->[18,13]-->[18,14]-->[18,15]-->[18,16]-->[18,17]-->[18,18]-->[18,19]-->[18,20]-->[19,20]-->[20,20]

  通过比较我们可以得到,欧几里得距离函数相对于曼哈顿函数来说,扩展的节点数以及生成的节点数都要更少,算法的运行时间也要比曼哈顿距离算法的时间要更短一些,总体来说欧几里得距离算法比曼哈顿距离算法的性能要更好。文章来源地址https://www.toymoban.com/news/detail-444443.html

到了这里,关于A*算法求解迷宫寻路问题实验的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 模拟退火算法与遗传算法求解多目标优化问题的算法实现(数学建模)

    模拟退火算法是一种全局优化算法,解决的问题通常是找到一个最小化(或最大化)某个函数的全局最优解。它通过模拟物理退火的过程来搜索解空间,在开始时以一定的温度随机生成初始解,然后一步步降低温度,同时在当前解的周围随机搜索新的解,并根据一定概率接受

    2024年02月02日
    浏览(57)
  • 【数据结构 迷宫问题求解】栈的应用|c语言|迷宫问题

    亲测可行: 使用蓝桥杯比赛编译器:DEV C++  求迷宫中从入口到出口的路径是一个经典的程序设计问题,通常采用“穷举求解”的方法,即顺着某一方向向前探索,若能走通,则继续往前走;否则原路返回,换一个方向继续探索,直至所有可能的通路都探索到为止。 因此,在

    2024年02月08日
    浏览(49)
  • DFS求解迷宫问题

       下面来具体分析一下算法的具体实现 首先要进行搜索,对搜索方向的顺序规定为:右--下--左--上   按照搜索顺序从起点开始搜索,在搜索的过程中将已经搜索过的位置设为已访问,这样我们就可以得到如下图所示的一条路线。 在到达终点后要进行回溯,利用 回溯 找到其

    2024年02月11日
    浏览(43)
  • 人工智能导论——遗传算法求解TSP问题实验

    一、实验目的: 熟悉和掌握遗传算法的原理、流程和编码策略,并利用遗传算法求解组合优化问题,理解求解TSP问题的流程并测试主要参数对结果的影响。 二、实验原理: 旅行商问题,即TSP问题(Traveling Salesman Problem)是数学领域中著名问题之一。假设有一个旅行商人要拜

    2023年04月13日
    浏览(46)
  • 人工智能原理实验4(1)——遗传算法、蚁群算法求解TSP问题

    TSP问题是组合数学中一个古老而又困难的问题,也是一个典型的组合优化问题,现已归入NP完备问题类。NP问题用穷举法不能在有效时间内求解,所以只能使用启发式搜索。遗传算法是求解此类问题比较实用、有效的方法之一。下面给出30个城市的位置信息: 应用遗传算法和蚁

    2024年01月24日
    浏览(59)
  • 算法 |【实验5.2】1-深度优先搜索暴力求解旅行商问题

    商品推销员要去n个城市推销商品,城市从1至n编号,任意两个城市间有一定距离,该推销员从城市1出发,需要经过所有城市并回到城市1,求最短总路径长度。 把旅行商问题看作一种排列问题,不难想出,这道题的蛮力做法即穷举所有路线。选定起点有n种选法,选定起点后的

    2023年04月08日
    浏览(74)
  • 【人工智能】实验三 A*算法求解八/十五数码问题实验与基础知识

    熟悉和掌握启发式搜索的定义、估价函数和算法过程,并利用A*算法求解N数码难题,理解求解流程和搜索顺序。 以8数码问题和15数码问题为例实现A*算法的求解程序(编程语言不限)。 设计两种不同的估价函数。 设置相同的初始状态和目标状态,针对不同的估价函数,求得

    2024年02月03日
    浏览(127)
  • 算法设计与分析实验二:动态规划法求解TSP问题和01背包问题

    【实验内容】 (1)tsp问题:利用动态规划算法编程求解TSP问题,并进行时间复杂性分析。 输入:n个城市,权值,任选一个城市出发; 输出:以表格形式输出结果,并给出向量解和最短路径长度。 (2)01背包问题:利用动态规划算法编程求解0-1背包问题,并进行时间复杂性分

    2024年02月03日
    浏览(58)
  • 用栈求解迷宫问题的所有路径及最短路径程序(纯c语言)

    参考了这个博客 学校作业,在各种地方搜了半天,看别人的要么就是有点错,要么就是很复杂用了不少我不知道的库,还要么就是只求了一条路径,还要么就是用了c++没学过。 写了半天,写出了一个应该是比较简单的方法,应该是还能优化,不过作业能跑就行,懒得搞了。

    2023年04月12日
    浏览(40)
  • 【任务分配】多目标粒子群算法求解多无人机多任务路分配及路径规划(最短路程+最短时间)问题【含Matlab源码 3522期】

    1 粒子群算法 粒子群算法是智能算法领域中除蚁群算法、鱼群算法又一个智能群体算法。 PSO算法首先在可行解空间中初始化一群粒子,每个粒子都代表极值优化问题的一个潜在最优解。粒子在解空间中运动,通过跟踪个体极值Pbest和群体极值Gbest更新个体位置。 粒子每更新一次

    2024年02月04日
    浏览(69)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包