A*算法解决迷宫寻路问题

2024-09-03 19:58

本文主要是介绍A*算法解决迷宫寻路问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

A*算法解决迷宫寻路问题

问题描述

下图是一个迷宫,试为机器人找一条从Start到End的最短路径设计一搜索算法
迷宫寻路

设计思路

a)状态空间的表示
首先将迷宫图转换为列表形式呈现,每个格子用
(横坐标,纵坐标,上通路状态,下通路状态,左通路状态,右通路状态)来表示,通路状态用1或0表示,可通过为1,不可通过为0。比如起点(1,1),假定不能从起点出去,所以(1,1)可以走下或走右,所以第一格的状态表示为(1,1,0,1,0,1)。
整张迷宫图的状态表示为:
迷宫图的状态表示
同时每一步操作都记录在列表中,比如向下移动一格后,列表元素变为[(1,2,1,1,0,1),(1,1,0,1,0,0)]。

b)操作集
该问题通过“上,下,左,右”四个方向进行下一节点的生成和移动,同时通过四个方向的通路状态来判断下一方向节点是否可通过,以此来限制节点的生成。

c)算法使用策略
使用A*算法,估价函数使用h(n) = A * B(A为横坐标,B为纵坐标),用h(n)递减重排open表,同时对生成节点进行是否重复判断。 为清楚起见,每一格子均以其右下角坐标(x,y)为标志。如start格用(1,1),end格用(7,6)标志。

完整代码

def GJ(this):#估价函数计算 h(n) = A*Breturn this[0] * this[1]def Judge(this,p):this_copy = this[:]this_copy.insert(0,p)for i in open:for x in i:if p == x:returnfor i in closed:for x in i:if p == x:returnopen.append(this_copy)returndef found(k,array):for i in array:if i[0:2]== k:return iif  __name__ == '__main__':M = [(1,1,0,1,0,0),(2,1,0,0,1,1),(3,1,0,0,1,0),(4,1,0,1,0,1),(5,1,0,0,1,0),(6,1,0,1,0,1,),(7,1

这篇关于A*算法解决迷宫寻路问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

最详细安装 PostgreSQL方法及常见问题解决

《最详细安装PostgreSQL方法及常见问题解决》:本文主要介绍最详细安装PostgreSQL方法及常见问题解决,介绍了在Windows系统上安装PostgreSQL及Linux系统上安装Po... 目录一、在 Windows 系统上安装 PostgreSQL1. 下载 PostgreSQL 安装包2.

usb接口驱动异常问题常用解决方案

《usb接口驱动异常问题常用解决方案》当遇到USB接口驱动异常时,可以通过多种方法来解决,其中主要就包括重装USB控制器、禁用USB选择性暂停设置、更新或安装新的主板驱动等... usb接口驱动异常怎么办,USB接口驱动异常是常见问题,通常由驱动损坏、系统更新冲突、硬件故障或电源管理设置导致。以下是常用解决

Mysql如何解决死锁问题

《Mysql如何解决死锁问题》:本文主要介绍Mysql如何解决死锁问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录【一】mysql中锁分类和加锁情况【1】按锁的粒度分类全局锁表级锁行级锁【2】按锁的模式分类【二】加锁方式的影响因素【三】Mysql的死锁情况【1

SpringBoot内嵌Tomcat临时目录问题及解决

《SpringBoot内嵌Tomcat临时目录问题及解决》:本文主要介绍SpringBoot内嵌Tomcat临时目录问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录SprinjavascriptgBoot内嵌Tomcat临时目录问题1.背景2.方案3.代码中配置t

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

如何解决idea的Module:‘:app‘platform‘android-32‘not found.问题

《如何解决idea的Module:‘:app‘platform‘android-32‘notfound.问题》:本文主要介绍如何解决idea的Module:‘:app‘platform‘andr... 目录idea的Module:‘:app‘pwww.chinasem.cnlatform‘android-32

kali linux 无法登录root的问题及解决方法

《kalilinux无法登录root的问题及解决方法》:本文主要介绍kalilinux无法登录root的问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,... 目录kali linux 无法登录root1、问题描述1.1、本地登录root1.2、ssh远程登录root2、

SpringBoot应用中出现的Full GC问题的场景与解决

《SpringBoot应用中出现的FullGC问题的场景与解决》这篇文章主要为大家详细介绍了SpringBoot应用中出现的FullGC问题的场景与解决方法,文中的示例代码讲解详细,感兴趣的小伙伴可... 目录Full GC的原理与触发条件原理触发条件对Spring Boot应用的影响示例代码优化建议结论F

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

MySQL 中查询 VARCHAR 类型 JSON 数据的问题记录

《MySQL中查询VARCHAR类型JSON数据的问题记录》在数据库设计中,有时我们会将JSON数据存储在VARCHAR或TEXT类型字段中,本文将详细介绍如何在MySQL中有效查询存储为V... 目录一、问题背景二、mysql jsON 函数2.1 常用 JSON 函数三、查询示例3.1 基本查询3.2