每周一算法:A*(A Star)算法

八数码难题

题目描述

3 × 3 3\times 3 3×3 的棋盘上,摆有八个棋子,每个棋子上标有 1 1 1 8 8 8 的某一数字。棋盘中留有一个空格,空格用 0 0 0 来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为 123804765 123804765 123804765),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。

输入格式

输入初始状态,一行九个数字,空格用 0 0 0 表示。

输出格式

只有一行,该行只有一个数字,表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。

样例 #1

样例输入 #1

283104765

样例输出 #1

4

提示

样例解释

图中标有 0 0 0 的是空格。绿色格子是空格所在位置,橙色格子是下一步可以移动到空格的位置。如图所示,用四步可以达到目标状态。

并且可以证明,不存在更优的策略。

广度优先搜索

算法思想

根据题目描述,输入一个棋盘的初始状态,求从初始状态到目标状态需要的最少移动次数,可以用广度优先搜索求解,基本思想如下:

  • 将初始状态 start \text{start} start的移动步数设为 0 0 0,然后将其加入队列
  • 只要队列不为空
    • 从队首取出一个状态 state \text{state} state
    • 如果 state = end \text{state}=\text{end} state=end结束状态,则搜索结束,返回到达的 state \text{state} state移动步数
    • 否则,找到 state \text{state} state中字符 0 0 0的位置,向相邻方向进行扩展
      • 如果扩展到一个新的状态,则计算扩展到新状态的步数,并将新状态加入队列

代码实现

#include <bits/stdc++.h>
using namespace std;
queue<string> q;
unordered_map<string,int> dis;int dx[]={-1, 1, 0, 0}, dy[]={0, 0, -1, 1};int bfs(string start)
{string end = "123804765";dis[start] = 0;q.push(start);while(!q.empty()){string state = q.front(); q.pop();int step = dis[state];if(state == end) return step;int k = state.find('0'); //在当前状态的字符串中找到字符0int x = k / 3, y = k % 3; //将字符串中的位置转换为矩阵中的坐标for(int i = 0; i < 4; i ++){int a = x + dx[i], b = y + dy[i]; if(a < 0 || a >= 3 || b < 0 || b >= 3) continue; //越界swap(state[k], state[a * 3 + b]); //将数字字符与0进行交换,转移到新状态if(!dis.count(state)) //没有访问过{ dis[state] = step + 1; //转移到state状态的最小步数q.push(state); //入队}swap(state[k], state[a * 3 + b]); //恢复现场,交换回来,为下次转移做准备}}return -1;
}int main()
{string start;char c;for(int i = 0; i < 9; i ++){cin >> c;start += c;}cout << bfs(start) << endl;return 0;
}

A*算法

通过BFS可以发现,对每个状态都可以将 0 0 0向上右下左四个方向进行扩展,在最坏情况下要搜索的状态空间为 4 9 4^9 49,指数级别,搜索的效率比较低。在这种情况下,可以使用A*算法进行求解。

A*(A Star)算法是一种很常用的路径查找和图形遍历算法,它有较好的性能和准确度。

A*算法通过下面的函数来计算每个状态的优先级:

f ( n ) = g ( n ) + h ( n ) f(n)=g(n) + h(n) f(n)=g(n)+h(n)
其中:

  • f ( n ) f(n) f(n)是当前状态 n n n综合优先级。当选择下一个要扩展的状态时,我们总会选取综合优先级最高(值最小)的状态。
  • g ( n ) g(n) g(n)是状态距离起点(初始状态)的代价
  • h ( n ) h(n) h(n)是状态 n n n距离终点(目标状态)的预计代价,这也就是A*算法的启发函数

算法思想

A*算法与BFS类似,不同之处在于A*算法使用优先队列,选取 f ( n ) f(n) f(n)值最小(优先级最高)的状态作为下一个待扩展的状态。基本思想如下:

  • 将初始状态 start \text{start} start的移动步数设为 0 0 0,然后其综合优先级初始状态加入优先队列
  • 只要队列不为空
    • 取出优先队列中综合优先级最高(值最小)的状态 state \text{state} state
    • 如果 state = end \text{state}=\text{end} state=end结束状态,则搜索结束,返回到达的 state \text{state} state移动步数
    • 否则,找到 state \text{state} state中字符 0 0 0的位置,向相邻方向进行扩展
      • 如果扩展到一个新状态,或者到达该状态的步数减少,将状态的综合优先级和状态本身继续加入优先队列

启发函数

从算法的基本思想可以看出来,启发函数会影响A*算法的行为。

  • 在极端情况下,当启发函数 h ( n ) h(n) h(n)为0时,则将由 g ( n ) g(n) g(n)决定状态的优先级,此时算法就退化成了Dijkstra算法。
  • 如果 h ( n ) h(n) h(n)始终小于等于状态 n n n到终点的代价,则A*算法保证一定能够找到最短路径。但是当 h ( n ) h(n) h(n)的值越小,算法将遍历越多的状态,也就导致算法越慢。
  • 如果 h ( n ) h(n) h(n)完全等于状态 n n n到终点的代价,则A*算法将找到最佳路径,并且速度很快。可惜的是,并非所有场景下都能做到这一点。因为在没有达到终点之前,很难确切算出距离终点还有多远。
  • 如果 h ( n ) h(n) h(n)的值比状态 n n n到终点的代价要大,则A*算法不能保证找到最短路径,不过此时会很快。

通过调节启发函数我们可以控制算法的速度和精确度。因为在一些情况,可能未必需要最短路径,而是希望能够尽快找到一个路径即可,这也是A*算法比较灵活的地方。

对于网格形式的图,有以下这些启发函数可以使用:

  • 如果图形中只允许朝上下左右四个方向移动,则可以使用曼哈顿距离(Manhattan distance)。
  • 如果图形中允许朝八个方向移动,则可以使用对角距离。
  • 如果图形中允许朝任何方向移动,则可以使用欧几里得距离(Euclidean distance)。

代码实现

#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
typedef pair<int, string> PIS;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
//启发函数取当前状态中每个数字与其目标位置的曼哈顿距离之和
int h(string state)
{int res = 0;for(int i = 0; i < state.size(); i ++){if(state[i] != '0'){int t = state[i] - '1';res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3); //累加每个数字到其正确位置的曼哈顿距离}}return res;
}
int bfs(string start)
{string end = "123804765";priority_queue<PIS, vector<PIS>, greater<PIS>> heap; //小顶堆unordered_map<string, int> dis; //记录到达每一种状态的步数//g(start)返回起点到终点的预估距离heap.push({0 + h(start), start});dis[start] = 0;while(heap.size()){PIS t = heap.top(); heap.pop();string state = t.second;if(state == end) break; //终点第一次出队,搜索结束int step = dis[state];int k = state.find('0'); //找到0所在位置int x = k / 3, y = k % 3; for(int i = 0; i < 4; i ++){int a = x + dx[i], b = y + dy[i];if(a < 0 || a >= 3 || b < 0 || b >= 3) continue;swap(state[x * 3 + y], state[a * 3 + b]); //将0和目标交换if(!dis.count(state) || dis[state] > step + 1) //如果扩展到一个新的状态,或者能够缩短到state的距离{dis[state] = step + 1;heap.push({dis[state] + h(state), state}); //将综合优先级和状态加入优先队列}swap(state[x * 3 + y], state[a * 3 + b]);//恢复现场}}return dis[end];
}
int main()
{char c;string start;for(int i = 0; i < 9; i ++){cin >> c;start += c;}cout << bfs(start);return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/271281.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【RT-DETR有效改进】全新的SOATA轻量化下采样操作ADown(轻量又涨点,附手撕结构图)

一、本文介绍 本文给大家带来的改进机制是利用2024/02/21号最新发布的YOLOv9其中提出的ADown模块来改进我们的Conv模块,其中YOLOv9针对于这个模块并没有介绍,只是在其项目文件中用到了,我将其整理出来用于我们的RT-DETR的项目,经过实验我发现该卷积模块(作为下采样模块)…

nicegui学习使用

https://www.douyin.com/shipin/7283814177230178363 python轻量级高自由度web框架 - NiceGUI (6) - 知乎 python做界面&#xff0c;为什么我会强烈推荐nicegui 秒杀官方实现&#xff0c;python界面库&#xff0c;去掉90%事件代码的nicegui python web GUI框架-NiceGUI 教程…

嵌入式学习第二十五天!(网络的概念、UDP编程)

网络&#xff1a; 可以用来&#xff1a;数据传输、数据共享 1. 网络协议模型&#xff1a; 1. OSI协议模型&#xff1a; 应用层实际收发的数据表示层发送的数据是否加密会话层是否建立会话连接传输层数据传输的方式&#xff08;数据包&#xff0c;流式&#xff09;网络层数据的…

吴恩达深度学习笔记:神经网络的编程基础2.1-2.3

目录 第一门课&#xff1a;神经网络和深度学习 (Neural Networks and Deep Learning)第二周&#xff1a;神经网络的编程基础 (Basics of Neural Network programming)2.1 二分类(Binary Classification)2.2 逻辑回归(Logistic Regression) 第一门课&#xff1a;神经网络和深度学…

基于YOLOv5的无人机视角水稻杂草识别检测

&#x1f4a1;&#x1f4a1;&#x1f4a1;本文主要内容:详细介绍了无人机视角水稻杂草识别检测整个过程&#xff0c;从数据集到训练模型到结果可视化分析。 博主简介 AI小怪兽&#xff0c;YOLO骨灰级玩家&#xff0c;1&#xff09;YOLOv5、v7、v8优化创新&#xff0c;轻松涨点…

Github 2024-03-08 Java开源项目日报 Top10

根据Github Trendings的统计,今日(2024-03-08统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Java项目9C++项目1非开发语言项目1《Hello 算法》:动画图解、一键运行的数据结构与算法教程 创建周期:476 天协议类型:OtherStar数量:63556…

网络原理初识(2)

目录 一、协议分层 1、分层的作用 2、OSI七层模型 3、TCP / IP五层&#xff08;或四层&#xff09;模型 4、网络设备所在分层 5、网络分层对应 二、封装和分用 发送过程&#xff08;封装&#xff09; 1、应用层(应用程序) QQ 2、输入层 3、网络层 4、数据链路层 5、物理…

金融行业专题|基金超融合架构转型与场景探索合集(2023版)

更新内容 更新 SmartX 超融合在基金行业的覆盖范围、部署规模与应用场景。更新信创云资源池、关键业务系统性能优化等场景实践。更多超融合金融核心生产业务场景实践&#xff0c;欢迎下载阅读电子书《金融核心生产业务场景探索文章合集》。 随着数字化经济的蓬勃发展&#xf…

记一次Flink任务无限期INITIALIZING排查过程

1.前言 环境&#xff1a;Flink-1.16.1&#xff0c;部署模式&#xff1a;Flink On YARN&#xff0c;现象&#xff1a;Flink程序能正常提交到 YARN&#xff0c;Job状态是 RUNNING&#xff0c;而 Task状态一直处于 INITIALIZING&#xff0c;如下图&#xff1a; 通过界面可以看到…

ue4.27 发现 getRandomReachedLocation 返回 false

把这个玩意儿删掉&#xff0c;重启工程&#xff0c;即可 如果还不行 保证运动物体在 volum 内部&#xff0c;也就是绿色范围内确保 project setting 里面的 navigation system 中 auto create navigation data 是打开的(看到过博客说关掉&#xff0c;不知道为啥) 如果还不行&…

智奇科技工业 Linux 屏更新开机logo

智奇科技工业 Linux 屏更新开机logo 简介制作logo.img文件1、转换格式得到logo.bmp2、使用Linux命令生成img文件 制作rootfs.img文件替换rootfs.img中的logo 生成update.img固件附件 简介 智奇科技的 Linux 屏刷开机logo必须刷img镜像文件&#xff0c;比较复杂。 制作logo.i…

深入浅出(二)MVVM

MVVM 1. 简介2. 示例 1. 简介 2. 示例 示例下载地址&#xff1a;https://download.csdn.net/download/qq_43572400/88925141 创建C# WPF应用(.NET Framework)工程&#xff0c;WpfApp1 添加程序集 GalaSoft.MvvmLight 创建ViewModel文件夹&#xff0c;并创建MainWindowV…

通过对话式人工智能打破语言障碍

「AI突破语言障碍」智能人工智能如何让全球交流无障碍 在当今互联的世界中&#xff0c;跨越语言界限进行交流的能力比以往任何时候都更加重要。 对话式人工智能&#xff08;包括聊天机器人和语音助手等技术&#xff09;在打破这些语言障碍方面发挥着关键作用。 在这篇博文中&am…

简站wordpress主题看上去差不多 实际大不一样

有人说简站wordpress主题&#xff0c;都差不多嘛。我表示无语。表面看上去是差不多的&#xff0c;实际的细节是不一样的。 下面以编号&#xff1a;JZP4431和编号&#xff1a;JZP4878这两个主题为例子来讲一下&#xff0c;简站wordpress主题&#xff0c;在细节方面的不一样之处…

【观察】华为:加速行业智能化,正在“走深向实”

毫无疑问&#xff0c;犹如历史上蒸汽机、电力、计算机和互联网等通用技术一样&#xff0c;近20年来&#xff0c;人工智能正以史无前例的速度和深度改变着人类社会和经济&#xff0c;为释放人类创造力和行业生产力&#xff0c;以及促进经济增长都提供了巨大的机会。 根据高盛报告…

字符串函数和内存函数

文章目录 字符串函数strlen函数模拟实现 strcpy函数模拟实现 strcat函数使用模拟实现 strcmp函数使用模拟实现 strncpy函数使用模拟实现 strstr函数使用模拟实现 strtok函数使用 strerror函数使用 内存函数memset函数使用memcmp函数memcpy函数使用模拟实现 memmove函数使用模拟…

【深度优先】【图论】【C++算法】2045. 到达目的地的第二短时间

作者推荐 视频算法专题 LeetCode2045. 到达目的地的第二短时间 城市用一个 双向连通 图表示&#xff0c;图中有 n 个节点&#xff0c;从 1 到 n 编号&#xff08;包含 1 和 n&#xff09;。图中的边用一个二维整数数组 edges 表示&#xff0c;其中每个 edges[i] [ui, vi] 表…

HCIP---IS-IS协议

文章目录 前言一、pandas是什么&#xff1f;二、使用步骤 1.引入库2.读入数据总结 一.IS-IS协议概述 IS-IS是一种基于链路状态的内部网关协议&#xff08;IGP&#xff09;&#xff0c;它使用最短路径优先算法&#xff08;SPF或Dijkstra&#xff09;进行路由计算。这种协议在自治…

[密码学]入门篇——加密方式

一、概述 加密方法主要分为两大类&#xff1a; 单钥加密&#xff08;private key cryptography&#xff09;&#xff1a;加密和解密过程都用同一套密码双钥加密&#xff08;public key cryptography&#xff09;&#xff1a;加密和解密过程用的是两套密码 历史上&#xff0c…

u盘里文件损坏无法打开怎么恢复?这样操作更简单

U盘已经成为我们传输和存储数据的重要工具。然而有时候我们可能会遇到U盘里的文件损坏无法识别的情况&#xff0c;这无疑给我们的工作和学习带来了不小的困扰。 那么面对这种情况应该如何应对呢&#xff1f;本文将为你介绍个实用的恢复方法&#xff0c;帮助你轻松解决U盘文件损…