详细介绍如何利用 A star(A*)算法解决8数码问题
文章目录
- 1. A star(A*)算法简介
- 2. 利用A*解决8数码问题(含Python代码)
- 2.1 什么是8数码问题
- 2.2 A*算法中的开放列表和关闭列表
- 2.3 A*算法解决8数码问题过程
- 2.3.1 计算节点(棋盘顺序)间距离
- 2.3.2 交换数字生成新的节点
- 2.3.3 A*主求解程序
1. A star(A*)算法简介
A ∗ A^* A∗ 算法是一种常用的高效图搜索算法,用于在静态图中找到从起始节点到目标节点的最短路径。它结合了 D i j k s t r a Dijkstra Dijkstra 算法和 启发式(贪心)搜索算法的思想,通过使用“启发式函数”来控制搜索过程,从而提高大部分场景下的搜索效率。
D i j k s t r a Dijkstra Dijkstra 算法 (一种标号法)是每次优先搜索距离起始节点最近的待搜索节点,常用在带权值的路径搜素问题当中,这是典型的广度优先搜索,该算法能保证找到最短路,也常用在多目标节点或无目标节点的场景(挖宝游戏),但是这类算法在寻路场景下往往效率较低,需要花费大量的时间探索各个方向;启发式(贪心)搜索算法 则恰恰相反,它每次优先探索距离目标节点最近的节点,在无障碍的地图上,该算法效率极高,但如果有障碍,贪心搜索并不能保证找到的路线是最短的,或者遇到像挖宝这种无目标节点的场景则无法计算与目标的距离。
A ∗ A^* A∗ 算法 在考虑探索节点的优先顺序时,既考虑了与起始节点的距离,又考虑了与目标节点的预估距离,即综合考虑:从起始节点出发,经过当前节点到目标节点的总的估计代价(距离),既能保证找到最短路径,又能比广度优先搜索有更高的效率。
2. 利用A*解决8数码问题(含Python代码)
2.1 什么是8数码问题
8数码问题是一个经典的搜索问题。在一个 3 × 3 3\times 3 3×3 的棋盘上,放着数字 1 1 1 到 8 8 8,还有 1 1 1 个位置空着,通过交换空格与相邻位置的数字,来移动空格(只能上下左右),该问题会给出一个初始的棋盘顺序,以及期望的棋盘顺序,问最少移动多少下空格,能将初始顺序改变为目标顺序?
听着是不是有点像华容道
把空格的移动视作是棋盘顺序的移动,且这种对应关系是确定的,因此可以把8数码问题视为一个路径优化问题,每个棋盘顺序是一个节点。那么现在有个关键的问题,就是如何确定棋盘顺序(节点)与棋盘顺序(节点)之间的距离大小呢? 有两种简单的计算方法:
-
计算两个顺序中,未正确摆放的数字数量,对于目标顺序,该值为 0 0 0,该方法仅关注未摆放正确的数字数量,计算方法简单,但实际中,往往又不是这么回事,相同的错摆数量,确实不同的调整难度,如下例子:
1 , 2 , 3 2 , 3 4 , 5 , → 4 , 5 , 6 7 , 8 , 6 7 , 8 , 1 1, 2, 3\quad\quad \quad\quad2,3\\ 4,5, \quad\,\rightarrow\quad4,5,6\\7,8,6\quad\quad\quad7,8,1 1,2,32,34,5,→4,5,67,8,67,8,1
-
另一个距离公式是所有数字 1 − 8 1-8 1−8 在两个棋盘顺序中的位置距离之和,而对于二维棋盘上数字的位置,可以用一维的索引值表示,也可以用行列坐标表示,例如上面的例子,数字 6 6 6 在左边棋盘的位置可以是 8 8 8,也可以是 ( 2 , 2 )
相关文章:
详细介绍如何利用 A star(A*)算法解决8数码问题
文章目录 1. A star(A*)算法简介2. 利用A*解决8数码问题(含Python代码)2.1 什么是8数码问题2.2 A*算法中的开放列表和关闭列表2.3 A*算法解决8数码问题过程2.3.1 计算节点(棋盘顺序)间距离2.3.2 交换数字生成新的节点2.3.3 A*主求解程序1. A star(A*)算法简介 A ∗ A^*…...
如何锁定鼠标光标在水平、垂直或45度对角线模式下移动 - 鼠标水平垂直移动锁定器简易教程
在我们进行精细工作例如如创建图标和图形设计时,通常需要我们对鼠标移动进行精确控制。一旦向左或向右轻微移动,都可能导致设计出错。若出现不必要的错误,我们极有可能不得不重新开始,这会令人感到非常沮丧。这种情况下࿰…...
在 Docker 部署的 MySQL 容器内安装和使用 vim
在 Docker 部署的 MySQL 容器内安装和使用 vim 文章目录 在 Docker 部署的 MySQL 容器内安装和使用 vim步骤一:进入 MySQL 容器步骤二:更新软件源和安装 vim步骤三:验证 vim 安装步骤四:使用 vim 进行文件编辑步骤五:保…...
人工智能|深度学习——基于Xception实现戴口罩人脸表情识别
一、项目背景 近年来,随着人工智能技术的不断发展,人脸表情识别已经成为了计算机视觉领域中的重要研究方向之一。然而,在当前的疫情形势下,佩戴口罩已经成为了一项必要的防疫措施,但是佩戴口罩会遮挡住人脸的部分区域&…...
【HTML】简单制作一个动态3D正方体
目录 前言 开始 HTML部分 JS部分 CSS部分 效果图 总结 前言 无需多言,本文将详细介绍一段代码,具体内容如下: 开始 首先新建文件夹,创建两个文本文档,其中HTML的文件名改为[index.html],JS的文件名改…...
Linux 常用指令及其理论知识
个人主页:仍有未知等待探索-CSDN博客 专题分栏:http://t.csdnimg.cn/Tvyou 欢迎各位指教!!! 目录 一、理论知识 二、基础指令 1、ls指令(列出该目录下的所有子目录和文件) 语法: …...
论文阅读——Sat2Vid
Sat2Vid: Street-view Panoramic Video Synthesis from a Single Satellite Image 提出了一种新颖的方法,用于从单个卫星图像和摄像机轨迹合成时间和几何一致的街景全景视频。 即根据单个卫星图像和给定的观看位置尽可能真实地、尽可能一致地合成街景全景视频序列。…...
js怎样判断status
相信大家都知道Switch开关吧,他有两种状态,通常用1/2表示,开启时为true,关闭时为false,那么我们该怎样判断他是否为开启还是关闭你? 我们可以声明一个变量,让它等于status,判断它是否等于1/2&…...
多态.Java
(1)什么是多态? 同类型的对象,表现出不同的形态。前者指父类,后者指不同的子类 说简单点,就是父类的同一种方法,可以在不同子类中表现出不同的状态,或者说在不同子类中可以实现不同…...
SSL根证书是什么
根证书是什么? 根证书是CA认证中心给自己颁发的证书,是信任链的起始点。安装根证书意味着对这个CA认证中心的信任。 从技术上讲,证书其实包含三部分,用户的信息,用户的公钥,还有CA中心对该证书里面的信息的签名&#…...
大模型量化技术-GPTQ
大模型量化技术-GPTQ 2022年,Frantar等人发表了论文 GPTQ:Accurate Post-Training Quantization for Generative Pre-trained Transformers。 这篇论文详细介绍了一种训练后量化算法,适用于所有通用的预训练 Transformer模型,同时只有微小的性能下降。 GPTQ算法需要通过…...
NzN的数据结构--实现双向链表
上一章中,我们学习了链表中的单链表,那今天我们来学习另一种比较常见的链表--双向链表!! 目录 一、双向链表的结构 二、 双向链表的实现 1. 双向链表的初始化和销毁 2. 双向链表的打印 3. 双向链表的头插/尾插 4. 双向链表的…...
easyexcel-获取文件资源和导入导出excel
1、获取本地资源文件,根据模板填充数据导出 public void exportExcel(HttpServletResponse httpResponse, RequestBody AssayReportDayRecordQuery query) {AssayReportDayRecordDTO dto this.queryByDate(query);ExcelWriter excelWriter null;ExcelUtil.config…...
Android Monkey自动化测试
monkey一般用于压力测试,用户模拟用户事件 monkey 基本用法 adb shell monkey [参数] [随机事件数]monkey常用命令 -v:用于指定反馈信息级别,总共分三个等级-v -v -vadb shell mokey -v -v -v 100-s:用于指定伪随机数生成器的种…...
C++ //练习 11.20 重写11.1节练习(第376页)的单词计数程序,使用insert代替下标操作。你认为哪个程序更容易编写和阅读?解释原因。
C Primer(第5版) 练习 11.20 练习 11.20 重写11.1节练习(第376页)的单词计数程序,使用insert代替下标操作。你认为哪个程序更容易编写和阅读?解释原因。 环境:Linux Ubuntu(云服务…...
Nginx 安装与实践
目录 一、安装 Nginx1、先安装 Brew2、再安装 Nginx 二、常用的 Nginx 命令三、简单的 Nginx 配置四、查看日志的 Linux 命令1、查看日志的 Linux 命令2、实时查看项目运行时打印的日志 一、安装 Nginx 推荐使用 HomeBrew 来安装 Nginx。 1、先安装 Brew 详见:Home…...
QT 创建线程的几种方法
//qt创建线程的几种方法 //在Qt中,创建线程的主要方法有以下几种: //1.继承QThread类重写run方法 class MyThread : public QThread { Q_OBJECT public: void run() override { // 在这里执行你的代码 } }; // 使用 MyThread *myThread n…...
RocketMQ的简单使用
这里需要创建2.x版本的springboot项目 导入依赖 <dependencies><dependency><groupId>org.apache.rocketmq</groupId><artifactId>rocketmq-spring-boot-starter</artifactId><version>2.2.3</version></dependency>&…...
速盾:服务器有cdn 带宽上限建议多少
CDN(内容传输网络)是一种通过分布在全球不同地点的服务器来提供高效内容分发的技术。当用户请求访问某个网站时,CDN会根据用户的地理位置,将内容从离用户最近的服务器上提供给用户,这样可以减少延迟和带宽消耗…...
智慧工地安全+绿色施工方案
塔机监测 塔吊监测可以实现对塔机监测、群塔防碰撞、塔机区域防护和吊钩可视化 1司机身份识别认证:只有司机在监控设备进行刷卡、指纹、人脸、虹膜验证身份后才能进行设备的作业操作。 2运行工况采集与显示:清晰实时显示起重机械设备运行工况,主要显示的内容:起重量、起…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
C语言中提供的第三方库之哈希表实现
一. 简介 前面一篇文章简单学习了C语言中第三方库(uthash库)提供对哈希表的操作,文章如下: C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...
