14

次のようなゲームに関するプログラミング コンテスト ( Andrew Stankevich Contest 21 )の問題にしばらく苦労しました。

Nick と Peter は次のゲームをするのが好きです [...]。彼らは無向二部グラフ G を一枚の紙に描き、その頂点の 1 つにトークンを置きます。その後、彼らは順番に動きます。ニックが先に動く。

移動は、グラフ エッジに沿ってトークンを移動することで構成されます。その後、移動前にトークンがあった頂点とそれに付随するすべてのエッジがグラフから削除されます。有効な動きがないプレイヤーはゲームに負けます。

グラフが与えられ、与えられた開始ノードについて、両方のプレイヤーが最適にプレイした場合に開始プレイヤーが勝つか負けるかを見つけることがタスクになります。要約する

  • 二部グラフ
  • 開始ノードが与えられます (左側にあるとします)。
  • 順番に移動します。移動はエッジをたどることで構成されますが、既にアクセスしたノードにアクセスすることはできません
  • 動けなくなったプレイヤーが負け

グラフは 2 部構成であるため、Nick (最初のプレーヤー) は常に左側からノードを削除し、Peter は常に右側からノードを削除します。

グラフには最大 1000 個のノード (各辺で最大 500 個) と 50000 個のエッジを含めることができるため、優れた多項式時間アルゴリズムが必要です (ここでの制限時間は、すべての開始位置を解決するのに 2 秒ですが、多くのことを共有できると思います)。異なる開始位置間の情報)。

グラフは 2 部構成であるため、これはある種の頂点カバーまたはパッキングの問題に帰着できると確信していますが、これらのいずれかに関連する戦略を見つけることができません。

私は特別な場合の解決策を知っています: 辺にそれぞれn 1とn 2の頂点があるとしましょう。サイズmin(n 1 , n 2 )のマッチングがあり、小さい側のプレイヤーが開始した場合、勝利戦略が存在します。彼はマッチしたエッジをたどるだけで、自動的に勝利します。

何か案は？

4

2 に答える 2

10

命題。Nick (最初のプレイヤー) は、vこの頂点が特定のグラフのすべての可能な最大一致に属している場合、頂点から開始して勝ちます。2段階で証明していきます。

  1. なしで最大一致がある場合v、ニックは負けます。
    実際、マッチングは最大であるため、 からの拡張パスはありませんv。つまり、からのすべての単純な奇数長のパスvは、マッチングのエッジによって延長される可能性があります。私たちの問題に関して言えば、それはニックが動くたびにピーターがゲームを続けることができることを意味します。

  2. なしで最大マッチングがない場合v、ニックが勝ちます。
    可能な最大マッチングを検討してください。このマッチングの端に沿って からvまで移動しuます。ここで、最初のマッチングからエッジu-vを差し引いたものが、 を含まない残りのグラフの最大マッチングですu。ステップ 1 からわかるように、今移動するプレーヤー (Peter) は途方に暮れています。

実装に関しては、最初に単純なアルゴリズムを使用して O(VE) で最大マッチングを構築できます (実装例については、こちらを参照)。一般名は、Kuhn の拡張パス アルゴリズムであることがわかります。

その後、最大一致を維持し、すべての頂点を調べます。頂点vが現在一致していない場合、ニックは負けます。そうである場合、対応するエッジ、たとえばv-uをマッチングから削除し、頂点を一時的に禁止し、O(E)vから拡張パスの検索を実行します。uそのようなパスが見つからない場合、Nick が勝ち、削除したエッジを元に戻す必要があります。それ以外の場合、Nick は再び負け、新しい最大マッチングはそのままにしておくことができます。合計実行時間は O(VE) です。

于 2014-03-24T22:52:56.160 に答える
4

かわいい問題。意図した解決策は、最大マッチングを計算してから、どの左頂点がすべての最大マッチングに属するかを判断することだと思います。これらはプレーヤー 1 の勝利です。

勝利戦略は、最大マッチングに属するエッジを選択することです。開始頂点 v がすべての最大一致に属している場合、プレーヤー one によって選択されたエッジ e のもう一方の端点 w は、グラフマイナス v のすべての最大一致に属していません (v はすべての最大一致に属しているため、最大値のカーディナリティ一致は削除後に 1 減少するため、e はある最大一致 M に属しているため、新しいグラフでは M - e が最大であり、e のもう一方の端点は一致しません)。逆に、v が属さない最大マッチングが存在する場合、その近傍 w はすべて、グラフから v を引いたすべての最大マッチングに属します (そうでない場合は、w を含まない最大マッチングを見つけ、v から w へのエッジを追加し、矛盾するv) を削除しても、マッチングの最大カーディナリティが減少しないという仮定。

于 2014-03-24T22:37:16.673 に答える