Java 中的广度优先搜索

2024-04-03

我必须在 Java 中运行广度优先搜索来查找作业。我有一个 5x5 的图块网格(总共 24 个图块 - 1 个图块留为“空白”)。搜索的重点是通过向上、下、左或右移动“空白”来重新排列图块,最终将图块重新排列成正确的顺序。

为了进行此搜索,我创建了一个 Arraylist“队列”。我有一个方法,它获取此数组列表索引 0 处的状态,找到可以遵循的每个合法移动,然后将它们分别添加到数组列表的末尾。

理论上,这种情况会一直持续到最终找到“目标状态”为止。问题是,当我运行搜索时,“队列”数组列表继续变得越来越大。今天我让它运行了几个小时,但仍然没有找到解决方案。

这表明我可能以错误的方式解决了这个问题,并且有更好的方法可以在 Java 中进行广度优先搜索。我知道我的解决方案确实有效(最终),因为当我使用与目标状态没有太大不同的开始状态时,找到正确的路径并不需要太长时间。然而,我已经得到了一个可以使用的起始状态,不幸的是,它与目标状态相去甚远!

任何提示或技巧将不胜感激!


首先,我肯定会使用实际的 Queue 对象而不是 ArrayList。这是 Queue 接口上的 Java API 页面:http://java.sun.com/j2se/1.5.0/docs/api/java/util/Queue.html http://java.sun.com/j2se/1.5.0/docs/api/java/util/Queue.html- 你可以在该页面上看到 Queue 的实现有很多,如果你不知道该选择什么,一个简单的 LinkedList 就可以了。 ArrayList 会对性能造成巨大影响,因为它只能从末尾快速删除,如果从数组中的其他任何位置删除,它必须移动一切下一个(SLOW!)。你会在最后入队并在开始时出队,因此SLOW!

现在,您没有明确提到在完成项目后您正在将项目出队(删除它们),所以我认为您是这样,因为这将是原因之一。

您是否必须专门使用广度优先搜索?如果我没算错的话,有25个! (阶乘)组合,所以这是 15511210043330985984000000 个组合,理论上这意味着如果您正在进行广度优先搜索,您的算法不太可能完成。深度优先搜索不允许吗?如果必须使用广度优先搜索,则使其速度更快的唯一方法是修剪掉不可能导致最佳解决方案的状态。不知道你会怎么做。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

Java 中的广度优先搜索 的相关文章

  • 为什么 Gradle 或 Maven 没有依赖版本锁定文件?

    最近 在阅读 NPM Yarn Paket Cargo 等包管理器时 我了解到依赖版本锁定文件的概念 我的理解是 它是一个列出所有直接和传递依赖项及其确切依赖项的文件 版本号 因此保证后续构建使用一组等效的依赖项 这似乎是一个理想的功能 因
  • Java ArrayList 和 LinkedList - 在末尾添加元素实现细节

    我对为什么 arraylist 比链表更快的理解是 使用 arraylist 基本上只需要一个操作 更新末尾数组元素的引用 而使用链表你必须做更多的事情 例如创建一个新节点 更新 2 个引用 遍历链表并更新最后一个节点以指向新节点等 但是我
  • 活动完成时 resultCode 的默认值

    这可能是一个基本问题 但我希望能得到一些澄清 我正在尝试做的事情 1 使用 requestCode 启动一个 Activity 并处理两个操作 onActivityResult 一个使用 RESULT OK 另一个使用 RESULT CAN
  • XML 节点上的 getNodeName() 操作返回 #text

  • 如何开始:使用 AssertJ Swing 测试 Java Swing GUI

    在使用 Swing 开发 Java 桌面应用程序时 我需要直接测试 UI 而不仅仅是通过单元测试测试底层控制器 模型类 This 答案 关于 基于 Swing 的应用程序的最佳测试工具是什么 https stackoverflow com
  • 如何向JTable中插入数据?

    我编写此代码用于在表中显示字符串 但它没有显示并且没有任何效果 有什么问题吗 public pamnel initComponents String columnNames First Name Last Name Sport of Yea
  • 如何创建可以分发或打包的可执行jar文件?

    我在用getdown https github com threerings getdown wiki创建更新 java 应用程序的方法 当我完成本教程后 我测试了它是否可以在命令行上运行 如下所示 java jar c downloads
  • PreparedStatement缓存——它是什么意思(它是如何工作的)

    例如 我使用 c3p0 和一些定义的 maxStatements 来进行准备语句缓存 这个缓存到底有什么作用 它缓存什么样的数据 在什么级别 数据库 应用程序 从例子中理解它会很好 例如我有一个查询 从某个表中选择 其中某个列 现在我在未缓
  • 当一个对象被分配给另一个对象时会发生什么

    public class DrumKitTestDrive param args public static void main String args TODO Auto generated method stub Echo e1 new
  • Java 中枚举类型的强制初始化

    我试图找到一种方法来强制 Java 加载 初始化枚举类型 嵌套在包含静态 Map 的类中 这对我来说很重要 因为枚举类型有一个填充所述映射的构造函数 并且如果没有显式方法来初始化此枚举 则映射将保持为空 我尝试过使用Class forNam
  • 您会如何向六年级学生解释 Scala 的抽象类功能? [复制]

    这个问题在这里已经有答案了 我试图理解 O Reilly 的 Scala 编程中的代码示例 我是一名 JavaScript 程序员 书中的大部分解释都假设我有 Java 背景 我正在寻找对抽象类及其用途的简单 高级的解释 package s
  • 使用 Java EE 将文件存储在云中

    我正在使用 CloudBees 部署我的 Java EE 应用程序 因为我需要写入和读取文件 但我找不到 CloudBees 中的任何云文件系统 请向我推荐任何免费的云文件系统存储和用于访问该文件系统的java代码 使用 jclouds 您
  • java android 取消静音按钮的问题

    我正在创建一个简单的点击计数器 Android 应用程序 单击按钮时会播放声音 并且在离开计数屏幕然后返回时也会保存计数 我遇到了静音按钮的问题 当我单击它时 它会静音整个应用程序 而不仅仅是特定的 GUI 屏幕 活动 第一个问题是静音按钮
  • Servlet异步处理请求

    当我探索 NodeJS 应用程序和 Java 应用程序如何处理请求时 我遇到了 Servlet 对请求的异步处理 根据我在不同地方读到的内容 请求将由 Servlet 容器中的 HTTP 线程接收和处理 如果发生阻塞操作 如 I O 则可以
  • VFS2错误无法删除文件并且无法获取当前用户的组ID(错误代码:-1)

    I m using VFS2 to take and import files into the folders by SFTP protocol But I m obtaining an Error Picture below my co
  • 我需要关闭“PreparedStatement”吗? [关闭]

    这个问题不太可能对任何未来的访客有帮助 它只与一个较小的地理区域 一个特定的时间点或一个非常狭窄的情况相关 通常不适用于全世界的互联网受众 为了帮助使这个问题更广泛地适用 访问帮助中心 help reopen questions 我有一个网
  • 如何在服务器模式下运行H2数据库?

    我需要从我的应用程序以服务器模式启动 H2 数据库 尝试过以下代码 server Server createTcpServer start 这是连接的属性 javabase jdbc url jdbc h2 tcp localhost 90
  • JavaFX FXML 控制器 - 构造函数与初始化方法

    My Application类看起来像这样 public class Test extends Application private static Logger logger LogManager getRootLogger Overri
  • 是否可以使用多线程而不需要一遍又一遍地创建线程?

    首先 再次感谢所有已经回答我问题的人 我不是一个经验丰富的程序员 这是我第一次体验多线程 我有一个与我的问题非常相似的例子 我希望这可以缓解我们的情况 public class ThreadMeasuring private static
  • 一组内所有对的组合

    我想计算你可以组成一个集合的所有可能的对列表 例如 input 1 2 3 4 5 6 output 1 2 3 4 5 6 2 3 4 5 1 6 2 4 1 3 5 6 注意 这个例子只是输出中的一些随机内容 大部分都被删除了 我不关心

随机推荐

  • TableView 复选标记

    我想在选择字典数据数组时在表格视图中放置复选标记 例如 数组包含 10 个模型名称 它是字典 它包含子模型 我的问题是 当我选择子模型时 模型名称自动获得复选标记 现在我为不同的模型和子模型添加了复选标记 但是我们如何根据子模型添加复选标记
  • jquery 在视口检查器中同时检查多个元素

    我有一个 jQuery 函数来检查元素是否在视口中 如果是 它会添加 animate 类来启动动画并使元素可见 上面的方法有效 但现在 有多个元素 jQuery 仅针对该类的第一个元素blogcard 然后执行addClass animat
  • 证书对 Intranet SSL 有用吗?

    我的任务是开发命令行软件的内联网接口 现在我正在研究安全选项 我们的命令行应用程序已经完成 但我还没有开始编写 Web 界面 我不确切地知道潜在客户的安全要求是什么 尽管我相信ssh对于命令行界面来说通常是可以接受的 考虑到这一点 我请求帮
  • WebSocket 和纯 TCP 之间的根本区别是什么?

    我读过关于WebSockets http en wikipedia org wiki Web Sockets我想知道为什么浏览器不能像任何其他桌面应用程序一样简单地打开简单的 TCP 连接并与服务器通信 为什么可以通过 websocket
  • 如何将 Maven 原型添加到 Github?

    我已经使用 Maven 开发了我的自定义项目 我想将其分享给社区 是否可以将其放在 GitHub 上 以便可以从那里下载 并在 create archetype 命令中使用 谢谢 标记 这篇文章可能会提供一点帮助 http cemerick
  • 使用 NSSM 将 NodeJs 进程作为 Windows 服务启动不起作用

    我看过无数关于如何使用 NSSM 的文章 http nssm cc http nssm cc 启动 NodeJS 进程 所以 我有以下简单的 NodeJS 文件 var http require http http createServer
  • PowerShell 从具有多个属性的 XML 中获取属性值

    以下 XML 文件是使用 PowerShell 2 从 2008 R2 故障转移群集运行 Get ClusterGroup 命令的输出的一个对象节点
  • Spyder3 - AttributeError:“SpyderKernel”对象没有属性“_show_mpl_backend_errors”

    我的 Spyder3 有问题 当我打开它时 控制台上会出现此警告 Python 3 8 5 default Jul 28 2020 12 59 40 Type copyright credits or license for more in
  • 检测 IE11 及其内置内存泄漏何时耗尽内存(1.5GB 可回收池)

    IE11 有一个有据可查的 iframe 内存泄漏问题 在 SPA 中 如果您使用 iframe 内存将增长到大约 1 5GB 之后速度会变慢直至崩溃 我的任务是检测浏览器何时即将崩溃并尽快重新启动页面 该应用程序是嵌入在 ASP NET
  • 保持fork最新

    我想将一些东西提交到 github 存储库 但我 显然 没有任何权利这样做 我对该存储库进行了分叉 提交了更改并提交了拉取请求 现在的问题是 过了一段时间 其他人已经提交了原始存储库 这意味着我的分叉不再是最新的 现在应该如何更新我的 fo
  • 在 Windows 中以编程方式更改自定义鼠标光标?

    我正在尝试将 Windows 光标 默认为 Windows 自定义方案 更改为我的自定义光标 名为 割绳子 有没有办法将所有光标 箭头 忙碌 帮助选择 链接选择 更改为我的 割绳子 如果您想更改默认的鼠标光标主题 您只需在注册表中更改它即可
  • createprocess默认暂停[关闭]

    这个问题不太可能对任何未来的访客有帮助 它只与一个较小的地理区域 一个特定的时间点或一个非常狭窄的情况相关 通常不适用于全世界的互联网受众 为了帮助使这个问题更广泛地适用 访问帮助中心 help reopen questions 我在 dl
  • 如何调整 JavaFX 3D 子场景的大小?

    这段代码 http docs oracle com javase 8 javafx graphics tutorial camera htm CJAHFAHB将创建一个 300x300 大的 3D 场景 当我调整包含窗口 舞台的大小时 视口
  • mui 使用入口点插入作用域影子 DOM 样式时选择未设置样式的下拉选项

    请注意 这是针对 MUI v5 mui material 且NOT使用 v4 material ui core 最终弄清楚如何在使用情感入口点插入作用域阴影 DOM 样式时显示 mui material 样式 请参阅这篇文章如何在React
  • Android M:带有英雄元素的场景转换抛出 java.lang.IllegalStateException

    我有一个场景转换 但遇到了一些问题 带有英雄元素的场景转换抛出层超过最大值 GPU支持的尺寸 https stackoverflow com questions 26626344 scene transition with hero ele
  • 从 SiriKit 中的 INExtension 启动应用程序

    我想使用 SiriKit 开始锻炼 开始锻炼需要从应用程序扩展打开主应用程序 Apple 提供的样板文件INStartWorkoutIntentHandling处理程序是 func handle startWorkout startWork
  • 获取 Play 中当前循环的索引! 2 Scala 模板

    游戏中 1 可以在循环中获取当前索引 代码如下 list items myItems as item li Item item index is item li list Play2 中有类似的功能吗 for item lt myItems
  • 'pathutil' ruby​​ gem 与 jekyll (v3.9.0) 和 ruby​​ (v3.0.0) 兼容吗?

    我的问题 我有一个基于 jekyll 的静态网站 跑步后bundle exec jekyll serve 按照 jekyll 文档的指示 我得到下面的堆栈跟踪 我在堆栈跟踪中为该博客文章文件创建的 Markdown 文件完全是标准语法 我已
  • CollectionView 嵌套在 CollectionView 中

    我见过将集合视图嵌套在表视图中的解决方案 但对于我的应用程序 我需要有 2 个集合视图 因为这样可以更轻松地执行其他操作 所以我们调用根集合视图垂直集合视图仅垂直滚动和嵌套集合视图水平集合视图仅水平滚动 我使用故事板创建了它们 下面你会看到
  • Java 中的广度优先搜索

    我必须在 Java 中运行广度优先搜索来查找作业 我有一个 5x5 的图块网格 总共 24 个图块 1 个图块留为 空白 搜索的重点是通过向上 下 左或右移动 空白 来重新排列图块 最终将图块重新排列成正确的顺序 为了进行此搜索 我创建了一