algorithm - Flood It ゲーム アルゴリズム

Question

ゲームのリンクはこちら: http://floodit.appspot.com/

ルールは簡単です。隣接する色から 1 つを選択する必要があります。開始点は左上隅です。その後、色が変わり、さらに多くの領域があふれます。目標は、グリッド全体をフラッディングすることです。

このゲームに関するスタックオーバーフローのトピックがいくつかありますが、私の質問に対する答えが見つかりません。私の目標は、グリッド全体をフラッディングする最適な方法を取得することです。今、私はこの立場にいます：

この問題を A* で解決しようとしています。私のヒューリスティックは、最も遠いコンポーネントまでの距離を最小化する色を選択することです（この場合、画像上の赤い色の2,4,1,3は最も遠いものです）。いくつかの色が最も遠いコンポーネントの1つまでの距離を最小化する場合、私はその中に最も多くのポイントがある色を選択します（この場合、私のアルゴリズムは「0」を選択します。これは、最も遠いすべてのノードへの距離を最小化し、より多くのポイントを含むため、「2」になります）。

私の先生は私たちに最適な解決策を教えてくれました。この場合、彼の最良の方法は次のとおりです。これはさらに7ユニットです。しかし、私のヒューリスティックによると、私は「0」を選択します。最良の方法は、0、2、4、5、3、1、0、2、4 です。さらに9ユニット。この位置で「0」ではなく「2」を選択する必要があるのはどのヒューリスティックですか？前もって感謝します。

Answer 1

A* アルゴリズムを、現在の状態から目標の状態までのコスト (または距離) を何らかの方法で推定するヒューリスティックを計算する単純な貪欲なベストファースト検索と混同していると思います。h(n)

f(n) = g(n) + h(n)A*では、g(n) が開始点から現在の状態までの (パス) コストを提供する関数を最小化するノードを展開しています(また、A*は最適な方向を見つける前に、状態グラフで複数の方向を探索できることを思い出してください)。 1つ）。

あなたの場合g(n)、最短パスに関心があるため、ルート状態からのパスの長さに等しいと想像できます（そして、新しい状態ごとにコストが1になります）。最適なパスを見つけるために、A*'sh(n) は決して最適解を過大評価してはなりません。このため、テーブル内の残りの色の数を使用して計算することも考えられます (実際、完全な色の最終状態に到達するには、常に少なくともその数の移動が必要になります)。

このヒューリスティックはそれほど有益ではないことに注意してください。つまり、解に収束する前に多くの状態を展開する必要があります。