详细介绍如何利用 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运行工况采集与显示:清晰实时显示起重机械设备运行工况,主要显示的内容:起重量、起…...
SQL Server 存储过程:BBS论坛(表结构文档下载及30个存储过程)
基于 Asp.Net 和 SQL Server 实现了一个BBS论坛,论坛功能比较强大,论坛大部分业务逻辑基于存储过程实现,记录一下。 BBS论坛存储过程清单 序号存储过程功能说明1sp_bbs_admin_add添加管理员2sp_bbs_admin_del删除系统管理员3sp_bbs_admin_m…...
03 Python进阶:MySQL - mysql-connector
mysql-connector安装 要在 Python 中使用 MySQL 数据库,你需要安装 MySQL 官方提供的 MySQL Connector/Python。下面是安装 MySQL Connector/Python 的步骤: 首先,确保你已经安装了 Python,如果没有安装,可以在 Python…...
InnoDB 行记录格式(“存储一行行数据的结构“)
1.行格式 1.1 Compact行格式 1.1.1 示意图 1.1.2 准备一下 1)建表 mysql> CREATE TABLE record_format_demo (-> c1 VARCHAR(10),-> c2 VARCHAR(10) NOT NULL,-> c3 CHAR(10),-> c4 VARCHAR(10)-> ) CHARSETascii ROW_FORMATCOM…...
【洛谷】P9236 [蓝桥杯 2023 省 A] 异或和之和
题目链接 P9236 [蓝桥杯 2023 省 A] 异或和之和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路 1. 暴力求解 直接枚举出所有子数组,求每个子数组的异或和,再对所有的异或和求和 枚举所有子数组的时间复杂度为O(N^2)&…...
ThreadLocal加切面实现线程级别的方法缓存
1、实现效果 当一个请求线程多次请求A方法时,只会触发一次A方法的实际调用,会将方法结果缓存起来,避免多次调用。 2、实现过程 1. 需要一个注解ThreadLocalCache,在需要缓存的方法上加上该注解 2. 需要一个切面,借助ThreadLocal,将结果缓存起来,利用环绕通知来实现方法拦截从…...
使用 Flume 将 CSV 数据导入 Kafka:实现实时数据流
使用 Flume 将 CSV 数据导入 Kafka:实现实时数据流 文介绍了如何使用 Apache Flume 将 CSV 格式的数据从本地文件系统导入到 Apache Kafka 中,以实现实时数据流处理。通过 Flume 的配置和操作步骤,我们可以轻松地将数据从 CSV 文件中读取并发…...
对代理模式的理解
目录 一、前言二、案例1 代码2 自定义代理类【静态代理】2.1 一个接口多个实现,到底注入哪个依赖呢?2.1.1 Primary注解2.1.2 Resource注解(指定name属性)2.1.3 Qualifier注解 2.2 面向接口编程2.3 如果没接口咋办呢?2.…...
#QT项目实战(天气预报)
1.IDE:QTCreator 2.实验: 3.记录: (1)调用API的Url a.调用API获取IP whois.pconline.com.cn/ipJson.jsp?iphttp://whois.pconline.com.cn/ipJson.jsp?ip if(window.IPCallBack) {IPCallBack({"ip":&quo…...
数据挖掘|关联分析与Apriori算法详解
数据挖掘|关联分析与Apriori算法 1. 关联分析2. 关联规则相关概念2.1 项目2.2 事务2.3 项目集2.4 频繁项目集2.5 支持度2.6 置信度2.7 提升度2.8 强关联规则2.9 关联规则的分类 3. Apriori算法3.1 Apriori算法的Python实现3.2 基于mlxtend库的Apriori算法的Python实现 1. 关联分…...
ChatGPT Excel 大师
原文:ChatGPT Excel Mastery 译者:飞龙 协议:CC BY-NC-SA 4.0 序言 欢迎来到 Excel 掌握的变革之旅,在这里,尖端技术和永恒专业知识在“ChatGPT Excel 掌握:释放专家技巧和窍门的力量”中融合。在当今快节…...
nodejs可以做网站吗/新手怎么开始做电商
故障现象:客户端报错:service zabbix-agent 启动后,端口没有被正常监听,服务端也无法正常连接 将客户端改为二进制文件安装也不能正常启动/usr/local/zabbix/sbin/zabbix_agentd -c /usr/local/zabbix/conf/zabbix_agentd.conf 百…...
wordpress本地化图片/seo常见优化技术
Oracle-用户权限与管理目标:1,掌握建立用户、概要文件的使用2,掌握系统权限的含义及授予、回收3,掌握对象权限的含义及授予、回收4,掌握角色的含义、对角色授予权限、把角色分配给用户Oracle 11g默认用户SYS:用于维护系…...
天津网站建设好公司/网站推广公司排行榜
没有用过memcached,看了一些关于memcached的博客,写的都挺好的,自己整合的时候也遇到了一些问题。 下载win的安装包,貌似没有64位的安装包,反正我是没找到。下载地址:http://pan.baidu.com/s/1kTC99kj首先定…...
网站怎么后台登陆/职业技能培训
Android中Intent传递类对象提供了两种方式一种是 通过实现Serializable接口传递对象,一种是通过实现Parcelable接口传递对象。 要求被传递的对象必须实现上述2种接口中的一种才能通过Intent直接传递。 Intent中传递这2种对象的方法: Bundle.putSerial…...
人和动物做愛视频网站/郑州网络推广方法
实验要求 【任务介绍】根据给定的上下文无关文法,分析任意一个算术表达式的语法结构。 【输入】任意的算术表达式。 【输出】与输入对应的一颗语法树或者错误。 【题目】设计一个程序,根据给定的上下文无关文法,构造一颗语法树来表达任意…...
青岛网站开发培训/百度推广电话客服24小时
一、成员修饰符 共有成员 私有成员, __字段名 - 无法直接访问,只能间接访问 1. 私有成员 1.1 普通方法种的私有成员 1 class Foo: 2 def __init__(self, name, age): 3 self.name name 4 # self.age age 5 …...