1

ハンガリーリングパズルの許容可能なヒューリスティックを見つけるのに苦労しています。IDA *アルゴリズムを使用して解決することを計画しており、VisualBasicでプログラムを作成しています。私に欠けているのは、パズルの実際の解決を実装する方法だけです。左と右の両方のリングを独自の配列に実装し、各リングを時計回りと反時計回りに回転させる関数を使用しました。私はコードを求めているのではなく、どこかで始めるだけです。

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

各リングの「エラー」を個別にカウントすることをお勧めします。リングを解決するには、何個のボールを交換する必要がありますか (9 色 1 個、10 色 1 個、9 色の 1 個のボール)。回転を使用して最大 2 つのボールを固定できます。その後、別の 2 つのボールを固定するには、別の回転が必要です。各リングの距離を個別に計算します = 2n-1 ここで、n は悪い位置の量の半分であり、大きい方を取ります。エラーの量が最も少ない位置を探すときは、20 の位置すべてを反復処理できますが、このメトリックを計算するより良い方法があると思います (単純な剪定は別として)。

更新: Gareth Reed との議論では、次のヒューリスティックが指摘されています。

リングごとに、次の数を数えます。

  1. 色の変化の数。目標量はリングごとに 3 つの色の変更であり、最大 4 つの色の変更を一度に削除できます。クレジットは、このメトリックの Gareth に送られます。
  2. それらの位置を無視して、さまざまな色の数。10色のボールが10個、9色のボールが9個、もう1つの9色のボールが1個あるはずです。一度に変更できる色は最大 2 色です。

2 番目のヒューリスティックは、次の 3 つの部分に分けることができます。

  1. 10 ボール 10 個と 9 ボール 10 個が必要です。10 個以上のボールは交換が必要です。
  2. 10 ボールの色は 1 つだけにする必要があります。マイナーカラーのボールは交換する必要があります。
  3. 9色のボールは1つだけでなければなりません。他の色のボールは交換する必要があります。すべてが同じ色で、9 色が不足していない場合は、追加のボールを 1 つ交換する必要があります。

両方の見積もりの​​大きい方を取ります。リングを交互にする必要があることに注意してください。実際には、n回の交換には2n-1回の移動が必要です。両方の推定値が等しい場合、または大きい方が最後に移動したリングのものである場合は、さらに 1 つ追加します。リングの 1 つは、最初の手で改善されません。

同じリングを 2 回回転させるすべての移動を削除します (移動メトリクスが大きな回転を許可すると仮定します)。これらはすでに調査済みです。

これにより、すべての大きな局所最小値が回避されます。

于 2012-09-17T21:21:54.750 に答える