滑动瓦片问题的启发式算法

我们的想法是将所有正确的元素向左和向左移动到右侧,中间有一个空的空间.元素可以跳过一个或两个部分进入空白区域.

LLL[ ]RRR

我正在尝试为这项任务考虑一种启发式方法.启发式是否有助于找到可能的解决方案,或实际上返回一些移动作为解决方案？我该如何表达这样的启发式？

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

粗略定义是"简化假设"或"体面猜测"

例如,假设您必须组建一个篮球队,并且您有关于想要列出其联系信息,出生日期和身高的人的情况说明书.您可以在测试每个候选人的特定技能时进行试训; 但是,这需要引入所有候选人,这可能需要很长时间.你使用启发式来缩小搜索范围 - 只调用至少6英尺2英寸高的人.这可能会忽略一些伟大的篮球运动员,但这是一个相当不错的猜测.

另一个启发式示例:您正在尝试使用最少数量的硬币来支付账单.启发式(简化方法)是首先选择具有最大值(小于剩余账单)的硬币,从账单中减去该值,然后重复.这并不能保证每次都能正常工作,但它会让你在大多数时间都能到达正确的社区.

您的问题的启发式可能是"永远不会向右移动Ls,并且永远不会将Rs移动到左侧" - 它通过从一开始就消除一些可能性来缩小所有可能移动的"搜索空间".