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

2024-08-21 17:18

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

前言

本篇文章是机器人自动寻路算法实现的第二章。我们要讨论的是一个在一个M×N的格子的房间中,有若干格子里有灰尘,有若干格子里有障碍物,而我们的扫地机器人则是要在不经过障碍物格子的前提下清理掉房间内的灰尘。具体的问题情景请查看人工智能: 自动寻路算法实现(一、广度优先搜索)这篇文章,即我们这个系列的第一篇文章。在上一篇文章里,我们介绍了通过广度优先搜索算法来实现扫地机器人自动寻路的功能。在这篇文章中,我们要介绍与之相对应的另一种算法:深度优先搜索算法。

项目下载地址

正文

算法介绍

深度优先算法,与广度优先搜索算法类似,唯一不同的是,它是沿着树的深度遍历数的节点,尽可能遍历搜索数的分支。也就是说,从根节点开始,它会首先遍历根节点的第一个子节点,接着遍历子节点的第一个子节点,并沿着树的深度一直遍历下去。下面两幅图就是深度优先搜索和广度优先搜索遍历顺序的对比,图中节点上的数字就表示该节点在这个算法中被遍历到的顺序


这里写图片描述
深度优先搜索


这里写图片描述
广度优先搜索

深度优先搜索的算法伪代码如下:

开始
将顶点入栈
循环  当栈为非空时,继续执行,否则算法结束取得队栈顶点V;访问并标记为已访问如果顶点V有未被访问过的子节点查找顶点V的第一个未被访问过的子节点W1标记W1为已访问将W1入栈否则将顶点V出栈

可以看出相对于上一篇文章中的广度优先搜索算法,深度优先搜索只是更改了一个数据结构:将队列改为栈。这里也是用到了栈的后进先出的特性。

代码

关于State和Point的代码,与前一篇文章人工智能: 自动寻路算法实现(一、广度优先搜索)中完全相同。这里不再贴出。下面是算法实现类的代码:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;public class Robot {//行数public static int colomnNum;//列数public static int rowNum;//障碍物数量public static int obstacleNum;//用于深度优先搜索的栈public static Stack<State> stack;//地图public static String[][] map;//灰尘坐标列表public static List<Point> dirtList;//closeList,用于存放已经存在的statepublic static List<State> closeList;//遍历总耗费public static int cost = 0;public static void main(String[] args) {State initialState = new State();Scanner sc = new Scanner(System.in);   System.out.println("Please Enter Row Number:");rowNum = sc.nextInt();System.out.println("Please Enter Colomn Number:"); colomnNum = sc.nextInt();map = new String[rowNum][colomnNum];dirtList = new ArrayList<Point>();closeList = new ArrayList<State>();sc.nextLine();for(int i=0; i<rowNum; i++){System.out.println("Please Enter the Elements in row " + (i + 1) + ":"); String line = sc.nextLine();for(int j=0; j<colomnNum; j++){//统计障碍物数量if(line.charAt(j) == '#'){                   obstacleNum++;}//将灰尘格子坐标存入list中if(line.charAt(j) == '*'){dirtList.add(new Point(i, j));}//设置机器人初始坐标if(line.charAt(j) == 

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



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

相关文章

HTML5 getUserMedia API网页录音实现指南示例小结

《HTML5getUserMediaAPI网页录音实现指南示例小结》本教程将指导你如何利用这一API,结合WebAudioAPI,实现网页录音功能,从获取音频流到处理和保存录音,整个过程将逐步... 目录1. html5 getUserMedia API简介1.1 API概念与历史1.2 功能与优势1.3

Java实现删除文件中的指定内容

《Java实现删除文件中的指定内容》在日常开发中,经常需要对文本文件进行批量处理,其中,删除文件中指定内容是最常见的需求之一,下面我们就来看看如何使用java实现删除文件中的指定内容吧... 目录1. 项目背景详细介绍2. 项目需求详细介绍2.1 功能需求2.2 非功能需求3. 相关技术详细介绍3.1 Ja

使用Python和OpenCV库实现实时颜色识别系统

《使用Python和OpenCV库实现实时颜色识别系统》:本文主要介绍使用Python和OpenCV库实现的实时颜色识别系统,这个系统能够通过摄像头捕捉视频流,并在视频中指定区域内识别主要颜色(红... 目录一、引言二、系统概述三、代码解析1. 导入库2. 颜色识别函数3. 主程序循环四、HSV色彩空间详解

PostgreSQL中MVCC 机制的实现

《PostgreSQL中MVCC机制的实现》本文主要介绍了PostgreSQL中MVCC机制的实现,通过多版本数据存储、快照隔离和事务ID管理实现高并发读写,具有一定的参考价值,感兴趣的可以了解一下... 目录一 MVCC 基本原理python1.1 MVCC 核心概念1.2 与传统锁机制对比二 Postg

一文详解MySQL如何设置自动备份任务

《一文详解MySQL如何设置自动备份任务》设置自动备份任务可以确保你的数据库定期备份,防止数据丢失,下面我们就来详细介绍一下如何使用Bash脚本和Cron任务在Linux系统上设置MySQL数据库的自... 目录1. 编写备份脚本1.1 创建并编辑备份脚本1.2 给予脚本执行权限2. 设置 Cron 任务2

SpringBoot整合Flowable实现工作流的详细流程

《SpringBoot整合Flowable实现工作流的详细流程》Flowable是一个使用Java编写的轻量级业务流程引擎,Flowable流程引擎可用于部署BPMN2.0流程定义,创建这些流程定义的... 目录1、流程引擎介绍2、创建项目3、画流程图4、开发接口4.1 Java 类梳理4.2 查看流程图4

C++中零拷贝的多种实现方式

《C++中零拷贝的多种实现方式》本文主要介绍了C++中零拷贝的实现示例,旨在在减少数据在内存中的不必要复制,从而提高程序性能、降低内存使用并减少CPU消耗,零拷贝技术通过多种方式实现,下面就来了解一下... 目录一、C++中零拷贝技术的核心概念二、std::string_view 简介三、std::stri

C++高效内存池实现减少动态分配开销的解决方案

《C++高效内存池实现减少动态分配开销的解决方案》C++动态内存分配存在系统调用开销、碎片化和锁竞争等性能问题,内存池通过预分配、分块管理和缓存复用解决这些问题,下面就来了解一下... 目录一、C++内存分配的性能挑战二、内存池技术的核心原理三、主流内存池实现:TCMalloc与Jemalloc1. TCM

OpenCV实现实时颜色检测的示例

《OpenCV实现实时颜色检测的示例》本文主要介绍了OpenCV实现实时颜色检测的示例,通过HSV色彩空间转换和色调范围判断实现红黄绿蓝颜色检测,包含视频捕捉、区域标记、颜色分析等功能,具有一定的参考... 目录一、引言二、系统概述三、代码解析1. 导入库2. 颜色识别函数3. 主程序循环四、HSV色彩空间

HTML5 搜索框Search Box详解

《HTML5搜索框SearchBox详解》HTML5的搜索框是一个强大的工具,能够有效提升用户体验,通过结合自动补全功能和适当的样式,可以创建出既美观又实用的搜索界面,这篇文章给大家介绍HTML5... html5 搜索框(Search Box)详解搜索框是一个用于输入查询内容的控件,通常用于网站或应用程