在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 Bean初始化及@PostConstruc执行顺序示例详解

《SpringBean初始化及@PostConstruc执行顺序示例详解》本文给大家介绍SpringBean初始化及@PostConstruc执行顺序,本文通过实例代码给大家介绍的非常详细,对大家的... 目录1. Bean初始化执行顺序2. 成员变量初始化顺序2.1 普通Java类(非Spring环境)(

Spring Boot 中的默认异常处理机制及执行流程

《SpringBoot中的默认异常处理机制及执行流程》SpringBoot内置BasicErrorController,自动处理异常并生成HTML/JSON响应,支持自定义错误路径、配置及扩展,如... 目录Spring Boot 异常处理机制详解默认错误页面功能自动异常转换机制错误属性配置选项默认错误处理

java如何实现高并发场景下三级缓存的数据一致性

《java如何实现高并发场景下三级缓存的数据一致性》这篇文章主要为大家详细介绍了java如何实现高并发场景下三级缓存的数据一致性,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 下面代码是一个使用Java和Redisson实现的三级缓存服务,主要功能包括:1.缓存结构:本地缓存:使

C++中detach的作用、使用场景及注意事项

《C++中detach的作用、使用场景及注意事项》关于C++中的detach,它主要涉及多线程编程中的线程管理,理解detach的作用、使用场景以及注意事项,对于写出高效、安全的多线程程序至关重要,下... 目录一、什么是join()?它的作用是什么?类比一下:二、join()的作用总结三、join()怎么

Java Spring的依赖注入理解及@Autowired用法示例详解

《JavaSpring的依赖注入理解及@Autowired用法示例详解》文章介绍了Spring依赖注入(DI)的概念、三种实现方式(构造器、Setter、字段注入),区分了@Autowired(注入... 目录一、什么是依赖注入(DI)?1. 定义2. 举个例子二、依赖注入的几种方式1. 构造器注入(Con

SpringBoot 异常处理/自定义格式校验的问题实例详解

《SpringBoot异常处理/自定义格式校验的问题实例详解》文章探讨SpringBoot中自定义注解校验问题,区分参数级与类级约束触发的异常类型,建议通过@RestControllerAdvice... 目录1. 问题简要描述2. 异常触发1) 参数级别约束2) 类级别约束3. 异常处理1) 字段级别约束

mybatis中resultMap的association及collectio的使用详解

《mybatis中resultMap的association及collectio的使用详解》MyBatis的resultMap定义数据库结果到Java对象的映射规则,包含id、type等属性,子元素需... 目录1.reusltmap的说明2.association的使用3.collection的使用4.总

如何在Java Spring实现异步执行(详细篇)

《如何在JavaSpring实现异步执行(详细篇)》Spring框架通过@Async、Executor等实现异步执行,提升系统性能与响应速度,支持自定义线程池管理并发,本文给大家介绍如何在Sprin... 目录前言1. 使用 @Async 实现异步执行1.1 启用异步执行支持1.2 创建异步方法1.3 调用

java内存泄漏排查过程及解决

《java内存泄漏排查过程及解决》公司某服务内存持续增长,疑似内存泄漏,未触发OOM,排查方法包括检查JVM配置、分析GC执行状态、导出堆内存快照并用IDEAProfiler工具定位大对象及代码... 目录内存泄漏内存问题排查1.查看JVM内存配置2.分析gc是否正常执行3.导出 dump 各种工具分析4.

Spring Boot配置和使用两个数据源的实现步骤

《SpringBoot配置和使用两个数据源的实现步骤》本文详解SpringBoot配置双数据源方法,包含配置文件设置、Bean创建、事务管理器配置及@Qualifier注解使用,强调主数据源标记、代... 目录Spring Boot配置和使用两个数据源技术背景实现步骤1. 配置数据源信息2. 创建数据源Be