A*搜索算法启发式函数
我正在尝试使用 A* 算法找到任何长度的滑动块拼图的最佳解决方案。
滑动积木拼图是一种游戏，白色（W）和黑色（B）的瓷砖排列在一个线性游戏板上，有一个单一的空白空间（-）。给定棋盘的初始状态，游戏的目的是将瓷砖排列成目标模式。
例如，我目前在董事会上的状态是BBW-WWB，我必须达到BBB-WWW状态。瓷砖可以通过以下方式移动：1.滑入相邻的空白空间，成本为1。2. 跳过另一个瓷砖进入空白区域，费用为 1。3. 将 2 个格子跳到空白处，费用为 2。
我已经实现了所有内容，但我不确定启发式函数。它计算当前状态下错放的磁贴与目标状态下最接近放置的相同颜色磁贴的最短距离（最小成本）。
考虑到当前状态BWB-W和目标状态BB-WW的给定问题，启发式函数给出了3的结果。（根据最小距离：B=0 W=2 B=1 W=0）。但是达到目标的实际成本不是3（移动错位的W=
我的问题是：我应该用这种方式计算最小距离，而不关心高估，还是应该把它除以2？根据瓷砖移动的方式，一个瓷砖可以以相同的成本克服两倍（见移动1和2）。
我尝试了两个版本。虽然划分的距离为已实现的目标提供了更好的最终路径成本，但它访问了更多的节点=
共有2个答案
你的试探法是不可接受的，所以你的A*不能保证每次都能找到最优答案。一个可接受的启发决不能高估成本。
比将启发式成本除以 3 更好的启发式方法是：不要将每个字母的距离 D 添加到其最终位置，而是添加 ceil（D/2）。这样，一个字母 1 或 2 得到一个值，3 或 4 得到一个值，得到一个 2 值，依此类推。
对我来说，这个问题的可接受启发式函数是什么样的并不明显，所以我不会promise说，“使用除以二的函数。”但是我要告诉你，你想出的朴素函数是不可接受的，因此不会给你很好的性能。为了让A*正常工作，所使用的启发式必须是可接受的；为了被接受，启发式必须绝对总是给出乐观的估计。这个没有，正是你在例子中强调的原因。
（虽然现在我考虑了一下，但除以二似乎是强制可接受性的合理方式。我只是不打算promise。）
-
A*算法是启发式搜索算法，是根据Dijkstra算法改进而来。 一、定义：是一种在图形平面上，对于有多个节点的路径求出最低通过成本的算法。它属于图遍历和最佳优先搜索算法，亦是BFS 的改进。 二、如何更好的理解A*算法？ 如下图所示，S为起始（start）节点，G为目标（goal）节点。 （1）节点之间连线是两点的路径长度，如A到E的路径长度c(A,E) = 9。 （2）节点旁的h值时当前节点到达
-
本篇将会结合实例解析启发式搜索，帮助大家更好理解。 启发式搜索（英文：heuristic search）是一种改进的搜索算法。它在普通搜索算法的基础上引入了启发式函数，该函数的作用是基于已有的信息对搜索的每一个分支选择都做估价，进而选择分支。简单来说，启发式搜索就是对取和不取都做分析，从中选取更优解或删去无效解。 （1）贪婪最佳优先 在Dijkstra算法中，我已经发现了其最终要的缺陷，搜索存在盲
-
主要内容：纯启发式搜索在前面章节中，我们已经讨论了不知情搜索算法，该搜索算法通过搜索空间查找问题的所有可能解决方案，而无需任何关于搜索空间的额外知识。但是，知情搜索(Informed Search)算法包含一系列知识，例如我们离目标有多远，路径成本，如何到达目标节点等。这些知识有助于代理人更少地探索搜索空间并更有效地找到目标节点。 知情搜索算法对于大型搜索空间更有用。知情搜索算法使用启发式思想，因此也称为启发式搜索。
-
说到搜索算法，它是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。搜索算法在路径规划、行为决策、语句识别、语义分析等多个领域都发挥着非常重要的作用，下面会给大家做一些介绍，便于大家学习和理解。 一、搜索算法介绍 搜索算法就是穷举出一个问题的部分或所有可能情况，从中找出求解
-
启用搜索 Docusaurus 支持使用 Algolia DocSearch 进行搜索。 一旦你建立了你的网站，输入你的网站信息 来让 Algolia 抓取你网站的文档页面。 Algolia 会向您发送您的网站的 API 密钥和索引名称。 启用搜索栏 在 algolia 部分的 siteConfig.js 中输入您的搜索 API 密钥和索引名称，以启用您的网站搜索。 const siteConfi
-
主要内容：1. 广度优先搜索,2. 深度优先搜索,3. 深度有限搜索算法,4. 统一成本搜索算法,5. 迭代深化深度搜索,6. 双向搜索算法不知情的搜索是一类通用搜索算法，它以强力方式运行。除了如何遍历树之外，不知情的搜索算法没有关于状态或搜索空间的附加信息，因此它也称为盲搜索。 以下是各种类型的无知搜索算法： 广度优先搜索 深度优先搜索 深度限制搜索 迭代加深深度优先搜索 统一成本搜索 双向搜索 1. 广度优先搜索 广度优先搜索是遍历树或图的最常见搜索策略。此算法在树或图中搜索横向，因此称为广