人工智能: 自动寻路算法实现(一、广度优先搜索)

2024-08-21 17:18

本文主要是介绍人工智能: 自动寻路算法实现(一、广度优先搜索),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

随着人工智能技术的日益发达,我们的生活中也出现了越来越多的智能产品。我们今天要关注的是智能家居中的一员:扫地机器人。智能扫地机器人可以在主人不在家的情况下自动检测到地面上的灰尘,并且进行清扫。有些更为对路线进行规划,找到可以清理灰尘的最短路径,达到省电的效果。当然,绕过障碍物也是必须拥有的技能。我们今天就来看一下扫地机器人自动寻路的算法的简单实现。这里我们不对机器人如何识别出灰尘进行讨论,我们只讨论发现了灰尘之后,机器人的路径规划进行一个分析。为了简单起见,我们假设机器人所处在的是一个M×N的格子的房间中,其中某些格子是灰尘,某些格子是障碍物,而另外有些格子则是单纯的空地。
我们再抽象一些,设星号(*)表示灰尘,井号(#)表示障碍物,下划线(_)表示空地,而我们的机器人所在的初始格子(当然首先要是一块空地)用at(@)表示。比如如下的图示

*#_*
_*__
_#_@

表示在一个3×4的空间内(俯视图),第一行有两个灰尘和一个障碍物,第二行有一个障碍物,第三行有一个障碍物, 而我们的机器人在右下角这个位置。它的目标就是在不经过任何障碍物的格子的情况下,用尽量少的步数,把房间中的灰尘都清除掉。我们假设机器人每次行动一个格子会消耗一点的行动力,当机器人处在灰尘所在的格子上时,清除这个格子里面的灰尘也消耗一点行动力。

项目下载地址

正文

问题分析

广度优先搜索(breadth-first search)是解决自动寻路功能的算法之一。作为一种常见的图形搜索算法,它也被广泛应用于解决其他各类算法问题。一般情况下,对于一个节点,它的邻居节点的集合被称作open list,而在这个节点被遍历之前,其他所有已经遍历过的节点存于close list中。
算法描述如下:

开始
将顶点入队列
循环  当队列为非空时,继续执行,否则算法结束出队列取得队列头顶点V;访问并标记为已访问查找列头顶点V的所有邻接顶点W1,W2,...Wn对于上述的所有每一个顶点Wn循环若Wn在close list中, 则继续遍历下一个顶点Wn+1否则将Wn入队列,并加入到close list

代码

首先我们建立一个坐标点的类,用于表示一个点的坐标。

public class Point {private int X;private int Y;public Point(int x, int y){this.X = x;this.Y = y;}public int getX() {return X;}public void setX(int x) {X = x;}public int getY() {return Y;}public void setY(int y) {Y = y;}//判断两个点是否坐标相同public static boolean isSamePoint(Point point1, Point point2){if(point1.getX() == point2.getX() && point1.getY() == point2.getY())return true;return false;}}

接下来就是比较重要的节点类,这里我们用state表示,state的意思为状态,也可以理解为当前屋子里的一个状态,比如当前的节点下我们的机器人的位置、房间内剩余的灰尘格子数量等等。

import java.util.ArrayList;
import java.util.List;public class State {//机器人位置private Point robotLocation;//操作,分为N(向上移动一格), S(向下移动一格), W(向左移动一格), E(向右移动一格)以及C(清理灰尘)private String operation;//当前节点的父节点, 用于达到目标后进行回溯private State previousState;//灰尘所在坐标的listprivate List<Point> dirtList;public Point getRobotLocation() {return robotLocation;}public void setRobotLocation(Point robotLocation) {this.robotLocation = robotLocation;}public String getOperation() {return operation;}public void setOperation(String operation) {this.operation = operation;}public State getPreviousState() {return previousState;}public void setPreviousState(State previousState) {this.previousState = previousState;}public List<Point> getDirtList() {return dirtList;}public void setDirtList(List<Point> dirtList) {this.dirtList = new ArrayList<Point>();for(Point point : dirtList){this.dirtList.add(point);}}//用于判断两个节点是否相同public static boolean isSameState(State state1, State state2){//若机器人位置不同,则节点不同if(!Point.isSamePoint(state1.getRobotLocation(), state2.getRobotLocation()))return fa

这篇关于人工智能: 自动寻路算法实现(一、广度优先搜索)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1093784

相关文章

Python实现终端清屏的几种方式详解

《Python实现终端清屏的几种方式详解》在使用Python进行终端交互式编程时,我们经常需要清空当前终端屏幕的内容,本文为大家整理了几种常见的实现方法,有需要的小伙伴可以参考下... 目录方法一:使用 `os` 模块调用系统命令方法二:使用 `subprocess` 模块执行命令方法三:打印多个换行符模拟

SpringBoot+EasyPOI轻松实现Excel和Word导出PDF

《SpringBoot+EasyPOI轻松实现Excel和Word导出PDF》在企业级开发中,将Excel和Word文档导出为PDF是常见需求,本文将结合​​EasyPOI和​​Aspose系列工具实... 目录一、环境准备与依赖配置1.1 方案选型1.2 依赖配置(商业库方案)二、Excel 导出 PDF

Python实现MQTT通信的示例代码

《Python实现MQTT通信的示例代码》本文主要介绍了Python实现MQTT通信的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 安装paho-mqtt库‌2. 搭建MQTT代理服务器(Broker)‌‌3. pytho

使用zip4j实现Java中的ZIP文件加密压缩的操作方法

《使用zip4j实现Java中的ZIP文件加密压缩的操作方法》本文介绍如何通过Maven集成zip4j1.3.2库创建带密码保护的ZIP文件,涵盖依赖配置、代码示例及加密原理,确保数据安全性,感兴趣的... 目录1. zip4j库介绍和版本1.1 zip4j库概述1.2 zip4j的版本演变1.3 zip4

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1:使用 UUID 模块(推荐)方法 2:使用 Secrets 模块(安全敏感场景)方法

Spring StateMachine实现状态机使用示例详解

《SpringStateMachine实现状态机使用示例详解》本文介绍SpringStateMachine实现状态机的步骤,包括依赖导入、枚举定义、状态转移规则配置、上下文管理及服务调用示例,重点解... 目录什么是状态机使用示例什么是状态机状态机是计算机科学中的​​核心建模工具​​,用于描述对象在其生命

Spring Boot 结合 WxJava 实现文章上传微信公众号草稿箱与群发

《SpringBoot结合WxJava实现文章上传微信公众号草稿箱与群发》本文将详细介绍如何使用SpringBoot框架结合WxJava开发工具包,实现文章上传到微信公众号草稿箱以及群发功能,... 目录一、项目环境准备1.1 开发环境1.2 微信公众号准备二、Spring Boot 项目搭建2.1 创建

IntelliJ IDEA2025创建SpringBoot项目的实现步骤

《IntelliJIDEA2025创建SpringBoot项目的实现步骤》本文主要介绍了IntelliJIDEA2025创建SpringBoot项目的实现步骤,文中通过示例代码介绍的非常详细,对大家... 目录一、创建 Spring Boot 项目1. 新建项目2. 基础配置3. 选择依赖4. 生成项目5.

Linux下删除乱码文件和目录的实现方式

《Linux下删除乱码文件和目录的实现方式》:本文主要介绍Linux下删除乱码文件和目录的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下删除乱码文件和目录方法1方法2总结Linux下删除乱码文件和目录方法1使用ls -i命令找到文件或目录

SpringBoot+EasyExcel实现自定义复杂样式导入导出

《SpringBoot+EasyExcel实现自定义复杂样式导入导出》这篇文章主要为大家详细介绍了SpringBoot如何结果EasyExcel实现自定义复杂样式导入导出功能,文中的示例代码讲解详细,... 目录安装处理自定义导出复杂场景1、列不固定,动态列2、动态下拉3、自定义锁定行/列,添加密码4、合并