2

プログラミング チャレンジを手に入れて、ヤッツィーを見つけました。私が単純化する問題：

  • 13の採点カテゴリがあります
  • プレーヤーによる 13 のロールがあります (プレーを構成します)。
  • 各ロールは異なるカテゴリに収まる必要があります
  • 目標は、プレイの最大スコア (カテゴリ内のロールの最適な配置) を見つけることです。score(play) はプレイのスコアを返します

最大プレイ スコアを見つけるためのブルート フォースには 13 が必要です。(= 6,227,020,800) score() 呼び出し。

私はシミュレーテッド アニーリングを選択して、最高スコアに近いものをより速く見つけます。決定論的ではありませんが、それで十分です。次のような 5 つのサイコロの 13 ロールのリストがあります。

((1,2,3,4,5) #1
 (1,2,6,3,4),#2
    ...
 (1,4,3,2,2) #13
)

また、(1,5,6,7,2,3,4,8,9,10,13,12,11)score() に渡されたプレイは、そのプレイの順列のスコアを返します。

適切な「隣接する州」を選択するにはどうすればよいですか? ランダム再起動の場合、番号のランダムな順列を選択するだけです。1 ～ 13 をベクトルに配置し、スコアを付けます。巡回セールスマン問題で、良好な隣接状態の例を次に示します。

「特定の順列の隣人は、たとえば隣接する都市のペアを交換することによって生成される順列です。」

次のように、2 つのランダムなベクトル位置を単純に交換することに嫌な予感がします。

(1,5,6,7, 2 , 3,4,8,9,10, 13, 12,11) # switch 2 and 13
(1,5,6,7, 13, 3,4,8,9,10, 2 , 12,11) # now score this one

しかし、私には証拠がなく、良い近隣州を選択する方法がわかりません。良い近隣州を選ぶ方法について何か考えがある人はいますか?

4

2 に答える 2

1

コツは、複数の種類の動きを持つことです。したがって、SA には、小さくて統一的な動きと、大きくて多様化する動きの両方を提供してください。ただし、最初に提供する可能性が高くなります。小さな動きは簡単です: 変更 1 またはスイッチ 2.

drools plannerで看護師の勤務表の例を見てみましょう。Java でのオープン ソース。

于 2011-01-11T09:18:09.110 に答える
1

ペアスワップ戦略は私には悪く聞こえません。それは確かに - 理論的には - すべての順列を訪問します。主なポイントは、あなたのケースで「隣人」が本当に「似ている」かどうか、つまり、ペアの交換だけが異なる2つの配置がスコアがかなり似ているかどうかを確認することだと思います。あなたの「ゲーム」のルールが私にははっきりしないので、私はこれを決めることができません。

于 2011-01-11T01:11:51.430 に答える