1

我很难为匈牙利指环谜题找到一个可接受的启发式方法。我计划使用 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

4

1 回答 1

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 球。超过十个的球需要更换。
  2. 应该只有一种颜色的 10 球。次要颜色的球需要更换。
  3. 应该只有一个 9 色球。其他颜色的球需要更换。如果都是同色，且9色不缺，则需多换一球。

取两者中较大的一个。请注意，您将需要交替使用环，因此实际上需要 2n-1 次移动来进行 n 次替换。如果两个估计值相等，或者较大的一个是最新移动的环，则添加一个额外的。第一步不会改善其中一个戒指。

修剪所有旋转相同环两次的移动（假设移动度量允许大旋转）。这些已经被探索过了。

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

于 2012-09-17T21:21:54.750 回答