程序员经验分享-hwhale

如何使用 A-Star 或 Dijkstra 算法解决 15 个难题？

2023-12-22

我在一本人工智能书籍中读到，用于模拟或游戏中寻路的流行算法（A-Star、Dijkstra）也被用来解决著名的“15 谜题”。

谁能给我一些关于如何将 15 个拼图简化为节点和边图的指示，以便我可以应用其中一种算法？

如果我将图中的每个节点视为游戏状态，那么该树不会变得很大吗？或者这只是做到这一点的方法？


对于 15 个拼图的 A-Star 来说，一个很好的启发方法是位于错误位置的方格数量。因为每个错位的方格至少需要 1 次移动，所以错位的方格数量保证小于或等于解决谜题所需的移动次数，这使其成为 A-Star 的合适启发式方法。

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

artificialintelligence

graphtheory

Dijkstra

astar

如何使用 A-Star 或 Dijkstra 算法解决 15 个难题？ 的相关文章

  • 强连通分量有什么用？

    我发现了几种可以解释的算法how在有向图中找到强连通分量 但没有解释why你会想要这样做 强连通分量有哪些应用 您应该查看 Coursera 上 Tim Roughgarden 的算法简介课程 对于他所讨论的每一种算法 他都会解释其一些应用

  • 在 Mathematica 中创建具有不同颜色边的图形

    我想创建一个图 图论 其中某些边具有与其他边不同的颜色 这将用于突出显示图中从一个顶点到另一个顶点的路径 以下是一些具有不同颜色边缘的示例http demonstrations wolfram com AGraphTheoryInterpr

  • 如何在 dijkstra 算法中以 O(log n ) 时间更新优先级队列中的键？

    过去一周我一直在研究 dijkstra 算法 我在 java 中有正确的运行代码 它使用数组来计算标准 findMin 函数 该函数为您提供距离最小的顶点 显然它是 O n 现在我希望使用优先级队列 最小堆 来实现它 我的思考过程是 whi

  • 用于神经网络模型预测的数据的缺失值

    我目前有大量数据将用于训练预测神经网络 美国主要机场的千兆字节天气数据 我几乎每天都有数据 但有些机场的数据中存在缺失值 例如 机场在 1995 年之前可能不存在 因此在此之前我没有该特定位置的数据 此外 有些还缺少整年 可能跨度为 199

  • 如何在 Keras 中将多个数据集与一个模型一起使用？

    我正在尝试使用 LSTM 网络通过 Keras 和 Tensorflow 进行外汇预测 我当然希望它能够在很多天的交易中进行训练 但要做到这一点 我必须给它提供具有大跳跃和无运动阶段的连续数据 当市场收盘时 这并不理想 因为它变得由于这些跳

  • 混合 SOM（带 MLP）

    有人可以提供一些有关如何正确地将自组织映射与多层感知器结合起来的信息吗 我最近读了一些关于这种技术的文章 与常规 MLP 相比 它在预测任务中表现得更好 因此 我想使用 SOM 作为前端 通过对输入数据进行聚类来降维 并将结果传递到 MLP

  • 如何推导出 alpha-beta 剪枝的时间复杂度？

    我了解极小极大和 alpha beta 剪枝的基础知识 在所有文献中 他们谈论最佳情况的时间复杂度是 O b d 2 其中 b 分支因子 d 树的深度 基本情况是所有首选节点都为 O b d 2 首先扩大 在我的 最佳情况 示例中 我有一个

  • 如何在大空间尺度上加速A*算法？

    From http ccl northwestern edu netlogo models community Astardemo http ccl northwestern edu netlogo models community Ast

  • 线性问题和非线性问题之间的区别？点积和核技巧的本质

    核技巧将非线性问题映射为线性问题 我的问题是 1 线性问题和非线性问题的主要区别是什么 这两类问题的差异背后的直觉是什么 核技巧如何帮助在非线性问题上使用线性分类器 2 为什么点积在这两种情况下如此重要 Thanks 当人们说到分类问题的线

  • 如何在Delphi中实现人工神经网络？ [关闭]

    Closed 这个问题需要多问focused help closed questions 目前不接受答案 我想要一个人工神经网络 42 个输入神经元 168 个隐藏神经元 7个输出神经元 这个网络就是玩 连四子 的游戏 每场比赛结束时 网络

  • 在径向（树）网络x图中查找末端节点（叶节点）

    给定下图 是否有一种方便的方法来仅获取末端节点 我所说的端节点是指那些具有一个连接边的到节点 我认为这些有时被称为叶节点 G nx DiGraph fromnodes 0 1 1 1 1 1 2 3 4 5 5 5 7 8 9 10 ton

  • 飞船推进AI：控制飞船在x=0、v=0时着陆的力

    我必须编写 AI 代码来控制游戏中宇宙飞船的许多推进喷气机 为简单起见 令空间为一维 宇宙飞船是一个点 只有 1 架喷气机 规则与问题 Let x v and a是飞船的位置 速度 加速度 Let F是施加在船上的喷射力 我知道质量m宇宙飞

  • Rasa core 和 Rasa nlu 之间的区别

    我试图理解之间的区别拉莎核心 https core rasa ai and Rasa NLU https nlu rasa ai installation html从官方文档看的 但我不太明白 我的理解是Rasa core用于引导对话流程

  • 机器人路径规划 - A*（星级）

    我正在用 C 为我的主要机器人探索行为实现 A 路径规划算法 当机器人移动时 它将自身周围的环境映射为二维图形 从这张图中 我设置了一个 Vector2D 元组 x y 它保存了这个路径点的位置 我希望机器人也能在其中导航 我对 A 所做的

  • 深度学习和传统的人工神经网络机器学习有什么区别？ [关闭]

    Closed 这个问题需要多问focused help closed questions 目前不接受答案 您能否简要解释一下两者之间的差异深度学习 https developer nvidia com deep learning和利用神经网

  • 公交车公共交通算法

    我正在开发一个可以查找公交路线的离线 C 应用程序 我可以提取时间表 巴士 路线数据 我正在寻找适用于基本数据的最简单的解决方案 可以使用什么算法来查找从巴士站 A 到巴士站 B 的路线 是否有适用于 C Java 的开源解决方案 数据库的

  • 单源最短路径，包含每条边的距离和权重

    假设有一个无向图 连接任意两个节点的每条边都有两个权重 即距离和成本 我想要获得最短路径 但也要确保不超出一定的成本 我尝试过实现 Djikstra 如果超出成本 则简单地回溯 由于缺乏更好的术语 直到遍历整个图表 但是 我正在寻找比这更快

  • 以 X-Y 坐标给出的点之间的最短路径距离

    我目前正在开发一个项目 该项目有一个包含大约 800 个点的 X 和 Y 坐标的向量 这些点代表一个电力网络 我的目标是计算 A 点和 B 点之间的最短距离路径 该路径可以或不能沿着包含电力线 X Y 坐标的向量给出的路径定位 我读过有关

  • 智能代理“教程”[关闭]

    Closed 此问题正在寻求书籍 工具 软件库等的推荐 不满足堆栈溢出指南 help closed questions 目前不接受答案 我最近通过阅读这本书遇到了智能代理 链接文本 https rads stackoverflow com

  • 完整无向图的最有效实现

    问题背景 我目前正在开发蚁群系统算法的框架 我想我应该从尝试它们解决的第一个问题开始 旅行商问题 TSP 我将使用 C 来完成该任务 所有 TSP 实例将包含一个完整的无向图 每个边有 2 个不同的权重 Question 到目前为止 我只使

随机推荐

  • 硒点击坐标没有点击预期的位置

    我需要屏幕抓取使用 ActiveX 控件进行导航的网页 这不是用于用户界面测试目的 而是用于从遗留应用程序下载数据 我遇到的问题是顶部导航是带有 javascript 的完整 ActiveX 不可能通过任何方式获取元素 所以我试图在坐标上单

  • 使用 iOS 6.0 SDK 并针对 iOS 5 Target 进行构建会导致 UIScrollView setMinimumZoomScale 在 iOS 5 模拟器上运行时失败

    i upgraded to Xcode 4 5 and have started using the iOS SDK 6 0 我有一个使用 Xcode 4 4 和 iOS SDK 5 1 开发的通用应用程序 它已经在所有经过测试的设备和模拟

  • 获取 EC2 实例 Java API 的状态

    我正在尝试在 AWS 上自动化一些东西 并且我正在使用 Java API 来执行此操作 我能够启动我想要的实例数量 但我无法找到正确的类或方法来获取实例的当前状态 如运行 停止等 我试过这个 DescribeInstanceStatusRe

  • Java 中的 KDTree 实现

    我正在寻找 Java 中的 KDTree 实现 我已经进行了谷歌搜索 结果似乎很随意 实际上有很多结果 但它们大多只是一次性的小实现 我宁愿找到具有更多 生产价值 的东西 类似于 apache 集合或适用于 NET 的优秀 C5 集合库 我

  • PHP：将 preg_replace 与 htmlentities 一起使用

    我正在写一个RSS to JSON parser作为其中的一部分 我需要使用htmlentities 在描述标签内找到的任何标签上 目前 我正在尝试使用preg replace 但我有点挣扎 我当前的 非工作 代码如下所示 pattern

  • IE10 中的 LinkBut​​tons 不执行回发

    我正在尝试添加一个简单的LinkButton到 ASP NET 4 页面 但它没有调用postback在 IE10 中 代码如下所示 HTML

  • mysql返回更新结果

    我想从 mysql 数据库中选择一堆行并更新这些行的查看属性 这是一种 我已阅读这些 标志 最初我做了这样的事情 update select a b c from mytable where viewed 0 set viewed 1 这可

  • PostgreSQL 与 Postgres Plus

    有谁知道两者之间有什么实质性差异常规 PostgreSQL http www postgresql org and Postgres Plus http www enterprisedb com products postgres plus

  • 如何在 Django/Python 中自动填充 PDF 表单？ [关闭]

    Closed 此问题正在寻求书籍 工具 软件库等的推荐 不满足堆栈溢出指南 help closed questions 目前不接受答案 我有 PDF 表单 我想使用 Django Web 应用程序中的数据自动填充这些表单 然后提供给用户下载

  • config 文件夹中的 main.php 和 main-local.php 之间的区别？

    谁能解释一下两者之间的区别main php and main local php在配置文件夹中 为什么一个人拥有 local 而另一个则没有 你可以阅读配置和环境 https github com yiisoft yii2 app adva

  • Aspectj 覆盖方法的参数

    我正在开发一个方面 用于检查 setter 方法的参数并用 null 值覆盖空字符串 这是我到目前为止的状态 Before execution de foo entity set args java lang String public v

  • 在 VBA 中使用 .NET HashTable 返回类型

    我在 VB NET 中创建了一个 NET 库 并且有一个函数返回一个对象HashTable 我一直在寻找如何在 Excel VBA 中访问 HashTable 对象中的元素 但找不到解决方案 我是 VBA 新手 请原谅我 我已经寻找过 但找

  • Rails 5 Carrierwave 没有与图像匹配的路线

    我需要一些帮助 我正在使用 Rails 5 和 Carrierwave 上传图像 我遇到的问题是图像已保存但不会显示 我得到一个没有路由匹配的 GET 我将图像存储在 Rails root 的上传文件夹中 因为我不希望它们保存在公共环境中目

  • python pandas dataframe按日期条件切片

    我可以使用 python datetime 对象读取和切片 pandas 数据帧 但是我被迫只使用现有日期在索引中 例如 这有效 gt gt gt data

  • Android SQLITE非法状态异常[重复]

    这个问题在这里已经有答案了 我使用以下代码将项目添加到数据库 public static void insertQuestion Context c JSONArray jarr String search throws JSONExcep

  • 通过随机点绘制好看的贝塞尔曲线

    我使用 javascript 和 RaphaelJS 来通过随机点绘制一条平滑的线 并输出到 SVG 该线严格水平移动 不会沿 X 轴返回 目前 我正在使用三次贝塞尔曲线来绘制从一点到另一点的线 问题是 这条线看起来不够好 两条曲线在一个点

  • 在 Android Studio 3.2 中看不到 find-sample-code 选项

    In 文档 https developer android com studio write sample code inline他们讲述查找代码示例选项 导入示例 但我在 Android Studio 3 2 中看不到它们 在代码中 突出

  • 如何计算 QueryDSL 中结果组的数量？

    如何在 QueryDSL Java 中 中实现组计数 背景 我正在表上实现分页搜索 我想在返回结果之前对结果进行分组 除了平常的LIMIT x OFFSET y查询时 我还想接收总行数 这是一页的 简化的 SQL 查询 SELECT x y

  • const char[] 和 const char* 之间的区别

    So 本文 https glandium org blog p 2361正在讨论声明字符串文字的用法 例如const char foo foo 它以以下声明结束 const char foo foo 几乎从来都不是你想要的 相反 您想使用以

  • 如何使用 A-Star 或 Dijkstra 算法解决 15 个难题？

    我在一本人工智能书籍中读到 用于模拟或游戏中寻路的流行算法 A Star Dijkstra 也被用来解决著名的 15 谜题 谁能给我一些关于如何将 15 个拼图简化为节点和边图的指示 以便我可以应用其中一种算法 如果我将图中的每个节点视为游

热门标签