我正在尝试找到一个名为Twiddle的小益智游戏的最佳解决方案(可以找到带有游戏的小程序 这里)。该游戏具有3x3矩阵,其数字为1到9。目标是使用最小动作量以正确的顺序将数字带入正确的顺序。在每一步,您都可以顺时针或逆时针旋转2x2平方。

即如果您有这个状态

6 3 9
8 7 5
1 2 4

然后您旋转左上2x2平方顺时针方向

8 6 9
7 3 5
1 2 4

我正在使用A*搜索来找到最佳解决方案。我的f()只是所需的旋转数。我的启发式功能已经导致最佳解决方案(如果我修改它,请参见末尾的通知),但我认为这是您可以找到的最好的解决方案。我目前的启发式术都占据每个角,查看角落的数字,并计算到该数字在解决状态下将具有的曼哈顿距离(这给了我将数字带到此帖子所需的旋转次数)并总结了所有这些值。即,您以上述示例为例:

6 3 9
8 7 5
1 2 4

和这个最终状态

1 2 3
4 5 6
7 8 9 

然后启发式言论做以下

6 is currently at index 0 and should by at index 5: 3 rotations needed
9 is currently at index 2 and should by at index 8: 2 rotations needed
1 is currently at index 6 and should by at index 0: 2 rotations needed
4 is currently at index 8 and should by at index 3: 3 rotations needed

h = 3 + 2 + 2 + 3 = 10

另外,如果H为0,但状态不是完全排序的,则比H = 1。

但是存在问题,即您一次旋转4个元素。因此,在极少数情况下,您可以一次进行两(矿石)估计的旋转。这意味着这些启发式的距离高估了与溶液的距离。

我目前的解决方法是,简单地将其中一个角落排除在计算中,这至少解决了我的测试案例。我没有做任何研究 真的 解决该问题,或者这种启发式方法是否仍在某些边缘案例中高估。

所以我的问题是: 您可以提出的最好的启发式方法是什么?

(免责声明:这是针对大学项目的,所以这有点作业。但是,如果可以提出任何资源,我可以自由使用任何资源,所以可以问大家。我还将归功于stackoverflow来帮助我; ))

有帮助吗?

解决方案

简单性通常是最有效的。将九位数字(在行优先)中作为形成单个整数。该解决方案由最小可能的整数I(g)= 123456789表示。因此,我建议以下启发式H(s)= i(s) - i(g)。以您的示例,H(S)= 639875124-123456789。

其他提示

计算距离时,应考虑所有元素,而不仅仅是角元素。想象一下,所有角元素1、3、7、9都在他们的家中,但所有其他元素都不是。

可以说,那些作为最终状态中邻居的元素在每个步骤中都应该越来越近,因此邻居的距离也可能是启发式的一部分,但可能比其最终状态的元素的距离弱的影响力较弱。

您可以通过考虑所有数字,然后将4分开并舍入下一个整数,从您的方法中获得可接受的(即,不高估)启发式。

为了改善启发式,您可以查看成对的数字。如果在左上方的数字1和2换了数字,则至少需要3个旋转来修复它们,这两个旋转都比单独考虑它们要比1+1更好。最后,您仍然需要除以4。

许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top