当前位置: 首页 > news >正文

详细介绍如何利用 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数码问题视为一个路径优化问题,每个棋盘顺序是一个节点。那么现在有个关键的问题,就是如何确定棋盘顺序(节点)与棋盘顺序(节点)之间的距离大小呢? 有两种简单的计算方法:

  1. 计算两个顺序中,未正确摆放的数字数量,对于目标顺序,该值为 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

  2. 另一个距离公式是所有数字 1 − 8 1-8 18 在两个棋盘顺序中的位置距离之和,而对于二维棋盘上数字的位置,可以用一维的索引值表示,也可以用行列坐标表示,例如上面的例子,数字 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度对角线模式下移动 - 鼠标水平垂直移动锁定器简易教程

在我们进行精细工作例如如创建图标和图形设计时,通常需要我们对鼠标移动进行精确控制。一旦向左或向右轻微移动,都可能导致设计出错。若出现不必要的错误,我们极有可能不得不重新开始,这会令人感到非常沮丧。这种情况下&#xff0…...

在 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&#xff08;内容传输网络&#xff09;是一种通过分布在全球不同地点的服务器来提供高效内容分发的技术。当用户请求访问某个网站时&#xff0c;CDN会根据用户的地理位置&#xff0c;将内容从离用户最近的服务器上提供给用户&#xff0c;这样可以减少延迟和带宽消耗&#xf…...

智慧工地安全+绿色施工方案

塔机监测 塔吊监测可以实现对塔机监测、群塔防碰撞、塔机区域防护和吊钩可视化 1司机身份识别认证:只有司机在监控设备进行刷卡、指纹、人脸、虹膜验证身份后才能进行设备的作业操作。 2运行工况采集与显示:清晰实时显示起重机械设备运行工况,主要显示的内容:起重量、起…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...