滑动瓷砖问题的启发式

Question

这个想法是将所有右侧元素移到左侧，将左侧元素移到右侧，中间留出一个空白空间。元素可以跳过一个或两个块进入空白区域。

LLL[ ]RRR

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

Answer 1

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

粗略的定义是“简化的假设”或“合理的猜测”

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

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

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

Answer 2

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

Answer 3

启发式通常是<！> quot; hint <！> quot;通常（但不总是）将指导您的程序到正确的方向。使用启发式扫描可以加快您的程序（您的算法），通常，但并非总是如此。它就像一个<！> quot; advice <！> quot;对于经常更正的算法。

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

您还可以看到，当前位置与您想要达到的目标（您想要的最终位置）相近有多接近。因此，而不是计算从初始状态到所有可能的路径。如果找到最终状态，您可以根据启发式<！>指引您的算法;当前状态与所需状态的接近程度如何<！>并且只遍历树的一部分。