7

タワー ソリティア、トライピークス、またはフェアウェイ ソリティアのようなカード ゲームを考えてみましょう。テーブルは、すぐに利用できる数枚のカードで構成されており、それぞれがその下にある他のカードを覆っている可能性があります (それらがプレイされるのをブロックしています)。あなたは「基礎」カードを 1 枚持っており、それがあなたの基礎カードのちょうど 1 ランク上または下にある場合、そのカードをテーブルから取り除くことができ、その時点でそれがあなたの新しい基礎カードになります。テーブルからカードをプレイできない場合に引き換えるカードの数は限られているため、通常は可能な限り長い順番でカードをプレイしたいと考えます。

まず、解決策を見つけやすくするために、取締役会をどのように代表しますか? 次に、再生可能な最長のシーケンスを見つけるためにどのアルゴリズムを使用しますか?

例：

  -4a- -5-
-3- -2- -4b-

一番下のカードは、一番上のカードが取り除かれるのを防ぎます。3 と 2 の両方がなくなるまで、4a を取り除くことはできません。開始カードがエースであると仮定すると、ここでの最適なプレイは 2、3、4b、5、4a になります。(代わりに 2、3、4a をプレイすることもできますが、それはあまり良くありません。)

これはある種の有向グラフとして表現されるべきだと思います。3 と 2 から 4a へ、および 2 と 4b から 5 へのエッジがありますが、3 と 2 の間、および 4a と 5 の間のエッジもあるでしょうか。もしそうなら、それらがいずれかの順序 (3 の次に 2、または 2 の次に 3) で再生できるという事実は、効率的な「最長パス」アルゴリズムを使用することを妨げるグラフ内のサイクルを形成しますか? （グラフにサイクルが含まれている場合、グラフ内の最長パスを見つけることはNP完全であると私は信じています。）

4

2 に答える 2

2

これをゲーム状態のグラフとして表すとどうなりますか（潜在的な次の状態がオンザフライで計算されます）-ループはありません。つまり、ゲームの潜在的な状態（まだかなり多くなる可能性があります）のストレートDFSです。開始点。

于 2010-01-05T03:44:02.487 に答える
1

重要なのは、ノードが問題の状態空間を完全にキャプチャする、可能な限り少ないノードで有向非巡回グラフを作成することです。次に、通常のアルゴリズムを実行できます。

テーブルに残っているカードの構造の形に基づいたエンコーディングを提案します。

状態の最初のデータは、一番左のカード、つまり一番上のカードの一意のIDである可能性があります。（たとえば4aのように、カード4aが1つしかないという意味でユニークです）。残りの形は、利用可能なカード（取る準備ができているカード）ごとに-1,0,1のいずれかで表すことができ、左側の次のカードが同じ「レベル」にあるか、1つのレベルにあるかを示します。より深いまたはより高い。（これは、カードが他の2枚のカードとのみ重なり、構造が例で示したもののように見えるという仮定を利用しています）。

于 2010-01-08T23:18:42.163 に答える