当前位置: 首页 > 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运行工况采集与显示:清晰实时显示起重机械设备运行工况,主要显示的内容:起重量、起…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...