在Java 中使用启发式搜索更快地解决问题

2024-06-23 05:18

本文主要是介绍在Java 中使用启发式搜索更快地解决问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

了解启发式搜索领域及其在人工智能上的应用。本文作者展示了他们如何成功用 Java 实现了最广为使用的启发式搜索算法。他们的解决方案利用一个替代的 Java 集合框架,并使用最佳实践来避免过多的垃圾收集。

通过搜寻可行解决方案空间来解决问题是人工智能中一项名为状态空间搜索 的基本技术。 启发式搜索 是状态空间搜索的一种形式,利用有关一个问题的知识来更高效地查找解决方案。启发式搜索在各个领域荣获众多殊荣。在本文中,我们将向您介绍启发式搜索领域,并展示如何利用 Java 编程语言实现 A*,即最广为使用的启发式搜索算法。启发式搜索算法对计算资源和内存提出了较高的要求。我们还将展示如何避免昂贵的垃圾收集,以及如何利用一个替代的高性能 Java 集合框架 (JCF),通过这些改进 Java 实现。本文的所有代码都可以从 下载 部分获得。

启发式搜索

计算机科学中的许多问题可用一个图形数据结构表示,其中图形中的路径表示潜在的解决方案。查找最优解决方案需要找到一个最短路径。例如,以自主视频游戏角色为例。角色做出的每个动作都与图形中的一个边缘相对应,而且角色的目标是找到最短路径,与对手角色交手。

深度优先 搜索和广度优先 搜索等算法是流行的图形遍历算法。但它们被视为非启发式 算法,而且常常受到它们可以解决的问题规模的严格限制。此外,不能保证深度优先搜索能找到最优解决方案(或某些情况下的任何解决方案),可以保证广度优先搜索仅能在特殊情况下找到最优解决方案。相比之下,启发式搜索是一种提示性 搜索,利用有关一个问题的知识,以启发式方式进行编码,从而更高效地解决问题。启发式搜索可以解决非启发式算法无法解决的很多难题。

视频游戏寻路是启发式搜索的一个受欢迎的领域,它还可以解决更复杂的问题。2007 年举行的无人驾驶汽车比赛 “DARPA 城市挑战赛” 的优胜者就利用了启发式搜索来规划平坦的、直接的可行使路线。启发式搜索在自然语言处理中也有成功应用,它被用于语音识别中的文本和堆栈解码句法解析。它在机器人学和生物信息学领域也有应用。与传统的动态编程方法相比较,使用启发式搜索可以使用更少的内存更快地解决多序列比对 (Multiple Sequence Alignment, MSA),这是一个经过深入研究的信息学问题。

通过 Java 实现启发式搜索

Java 编程语言不是实现启发式搜索的一种受欢迎的选择,因为它对内存和计算资源的要求很高。出于性能原因,C/C++ 通常是首选语言。我们将证明 Java 是实现启发式搜索的一种合适的编程语言。我们首先表明,在解决受欢迎的基准问题集时,A* 的 textbook 实现确实很缓慢,并且会耗尽可用内存。我们通过重访一些关键实现细节和利用替代的 JCF 来解决这些性能问题。

很多这方面的工作都是本文作者合著的一篇学术论文中发表的作品的一个扩展。尽管原作专注于 C/C++  编程,但在这里,我们展示了适用于 Java 的许多同样的概念。

广度优先搜索

熟悉广度优先搜索(一个共享许多相同概念和术语的更简单的算法)的实现,将帮助您理解实现启发式搜索的细节。我们将使用广度优先搜索的一个以代理为中心 的视图。在一个以代理为中心的视图中,代理据说处于某种状态,并且可从该状态获取一组适用的操作。应用操作可将代理从其当前状态转换到一个新的后继 状态。该视图适用于多种类型的问题。

广度优先搜索的目标是设计一系列操作,将代理从其初始状态引导至一个目标状态。从初始状态开始,广度优先搜索首先访问最近生成的状态。所有适用的操作在每个访问状态都可以得到应用,生成新的状态,然后该状态被添加到未访问状态列表(也称为搜索的前沿)。访问状态并生成所有后继状态的过程被称为扩展 该状态。

您可以将该搜索过程看作是生成了一个树:树的根节点表示初始状态,子节点由边缘连接,该边缘表示用于生成它们的操作。图 1 显示该搜索树的一个图解。白圈表示搜索前沿的节点。灰圈表示已展开的节点。

图 1. 二叉树上的广度优先搜索顺序

搜索树中的每一个节点表示某种状态,但两个独特的节点可表示同一状态。例如,搜索树中处于不同深度的一个节点可以与树中较高层的另一个节点具有同样的状态。这些重复 节点表示在搜索问题中达到同一状态的两种不同方式。重复节点可能存在问题,因此必须记住所有受访节点。

注:相关网站建设技

转自:http://www.sharetk.com/html/course/seo/8017.html

这篇关于在Java 中使用启发式搜索更快地解决问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Spring Security+JWT如何实现前后端分离权限控制

《SpringSecurity+JWT如何实现前后端分离权限控制》本篇将手把手教你用SpringSecurity+JWT搭建一套完整的登录认证与权限控制体系,具有很好的参考价值,希望对大家... 目录Spring Security+JWT实现前后端分离权限控制实战一、为什么要用 JWT?二、JWT 基本结构

java解析jwt中的payload的用法

《java解析jwt中的payload的用法》:本文主要介绍java解析jwt中的payload的用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java解析jwt中的payload1. 使用 jjwt 库步骤 1:添加依赖步骤 2:解析 JWT2. 使用 N

springboot项目如何开启https服务

《springboot项目如何开启https服务》:本文主要介绍springboot项目如何开启https服务方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录springboot项目开启https服务1. 生成SSL证书密钥库使用keytool生成自签名证书将

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Java中的JSONObject详解

《Java中的JSONObject详解》:本文主要介绍Java中的JSONObject详解,需要的朋友可以参考下... Java中的jsONObject详解一、引言在Java开发中,处理JSON数据是一种常见的需求。JSONObject是处理JSON对象的一个非常有用的类,它提供了一系列的API来操作J

使用Python实现图像LBP特征提取的操作方法

《使用Python实现图像LBP特征提取的操作方法》LBP特征叫做局部二值模式,常用于纹理特征提取,并在纹理分类中具有较强的区分能力,本文给大家介绍了如何使用Python实现图像LBP特征提取的操作方... 目录一、LBP特征介绍二、LBP特征描述三、一些改进版本的LBP1.圆形LBP算子2.旋转不变的LB

Maven的使用和配置国内源的保姆级教程

《Maven的使用和配置国内源的保姆级教程》Maven是⼀个项目管理工具,基于POM(ProjectObjectModel,项目对象模型)的概念,Maven可以通过一小段描述信息来管理项目的构建,报告... 目录1. 什么是Maven?2.创建⼀个Maven项目3.Maven 核心功能4.使用Maven H

SpringBoot多数据源配置完整指南

《SpringBoot多数据源配置完整指南》在复杂的企业应用中,经常需要连接多个数据库,SpringBoot提供了灵活的多数据源配置方式,以下是详细的实现方案,需要的朋友可以参考下... 目录一、基础多数据源配置1. 添加依赖2. 配置多个数据源3. 配置数据源Bean二、JPA多数据源配置1. 配置主数据

Python中__init__方法使用的深度解析

《Python中__init__方法使用的深度解析》在Python的面向对象编程(OOP)体系中,__init__方法如同建造房屋时的奠基仪式——它定义了对象诞生时的初始状态,下面我们就来深入了解下_... 目录一、__init__的基因图谱二、初始化过程的魔法时刻继承链中的初始化顺序self参数的奥秘默认

将Java程序打包成EXE文件的实现方式

《将Java程序打包成EXE文件的实现方式》:本文主要介绍将Java程序打包成EXE文件的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录如何将Java程序编程打包成EXE文件1.准备Java程序2.生成JAR包3.选择并安装打包工具4.配置Launch4