algorithm - 匈牙利戒指拼图

Question

我很难为匈牙利环谜题找到可接受的启发式算法。我计划使用 IDA* 算法来解决并在 Visual Basic 中编写程序。我所缺少的只是如何实现拼图的实际解决。我已经将左环和右环实现到它们自己的数组中，并具有顺时针和逆时针旋转每个环的功能。我不是在要求代码，只是在某个地方开始。

这是 2 个环形阵列:

Dim leftRing(19) As Integer 
' leftRing(16) is bottom intersection and leftRing(19) is top intersection
Dim rightRing(19) As Integer
' rightRing(4) is top intersection and rightRing(19) is bottom intersection

在数组中，我将以下内容存储为每种颜色的值: 红色值 = 1 黄色 = 2 蓝色 = 3 黑色 = 4

Answer 1

我建议分别计算每个圆环中的“错误”——需要更换多少球才能完成圆环(1 个 9 色球，1 个 10 色球，9 色球中的一个球)。一次旋转最多可以固定两个球，然后需要另一个旋转来固定另外两个球。分别计算每个环的距离 = 2n-1，其中 n 是坏位置数量的一半，取其中较大的一个。在寻找错误最少的位置时，您可以遍历所有 20 个位置，但我认为有更好的方法来计算这个指标(除了简单的修剪)。

更新: 与 Gareth Reed 的讨论指出了以下启发式:

分别对每个环数:

1. 颜色变化的次数。目标数量是每个环三个颜色变化，一次最多可以消除四个颜色变化。此指标归功于 Gareth。
2. 不同颜色的计数，忽略它们的位置。应该有:10 个 10 色球，9 个 9 色球和 1 个 9 色球。一次最多可以更改 2 种颜色。

第二个启发式可以分为三个部分:

1. 应该有 10 个 10 球和 10 个 9 球。超过 10 个的球需要更换。
2. 10 球应该只有一种颜色。次要颜色的球需要更换。
3. 应该只有一个 9 色球。需要更换其他颜色的球。如果都是同色，且9色不缺，则需要再换一个球。

取两个估计值中较大的一个。请注意，您将需要交替环，因此 n 次更换实际上需要 2n-1 次移动。如果两个估计值相等，或者较大的估计值用于最新移动的环，则添加一个额外的估计值。其中一个环不会被第一步提升。

修剪所有旋转同一个环两次的移动(假设移动度量允许大旋转)。这些已经被探索过。

这应该避免所有大的局部最小值。