artificial-intelligence - 滑动瓷砖问题的启发式

Question

这个想法是将所有右侧元素移动到左侧，将左侧移动到右侧，中间有一个空白空间。元素可以跳过一个或两个部分进入一个空白空间。

LLL[ ]RRR

我正在尝试为这项任务考虑启发式方法。启发式是为了帮助找到可能的解决方案，还是实际上返回一些移动作为解决方案？我将如何表达这样的启发式？

Answer 1

听起来你对什么是启发式有点困惑。

粗略的定义是“一个简化的假设”或“一个体面的猜测”

例如，假设您必须组建一支篮球队，并且您有关于想参加比赛的人的情况说明书，其中列出了他们的联系信息、出生日期和身高。您可以举行选拔赛，测试每个候选人的特定技能；不过，这需要引入所有候选人，而且可能需要很长时间。您使用启发式方法来缩小搜索范围——只调用至少 6 英尺 2 英寸高的人。这可能会忽略一些伟大的篮球运动员，但这是一个相当不错的猜测。

另一个启发式示例：您尝试使用最少数量的硬币来支付账单。启发式（一种简化的方法）是首先挑选价值最大的硬币（小于剩余的钞票），然后从钞票中减去价值，然后重复。这不能保证每次都有效，但它会在大多数情况下将您带到正确的社区。

您的问题的启发式方法可能是“永远不要将 Ls 向右移动，也永远不要将 Rs 向左移动”——它通过从一开始就消除一些可能性来缩小所有可能移动的“搜索空间”。

Answer 2

您在寻找启发式还是算法？启发式可能会也可能不会解决给定的问题。它实际上只是为了向您指出解决方案可能所在的方向。算法确实应该解决给定的问题。

Answer 3

启发式通常是一种“提示”，通常（但不总是）会引导您的程序朝着正确的方向前进。使用启发式方法可以加速你的程序（你的算法），通常，但并非总是如此。这就像对算法的“建议”，通常是正确的。

我不确定您在寻找什么，因为描述有点模糊。如果您想要该算法，您将需要研究特定移动对当前情况的影响以及每次向前推进所有可能移动的方法，实际上是遍历状态树（即，如果你做了一个特定的动作序列）。

您还可以看到，当前位置与您想要达到的目标（您想要的最终位置）的接近程度可能很重要。因此，与其计算从初始状态到找到最终状态的所有可能路径，您可以指导您的基于启发式“当前状态与所需状态的接近程度”的算法，并且只遍历树的一部分。