日の目を見なかった問題たち その2
はじめに
LAの会誌30号で私は、勝手に『日の目を見なかった問題たち』と銘打った
シリーズ物をはじめました。それはこんな感じで、はじまっています。
とてもオモシロイ、心に響くものがあるにもかかわらず、いろいろな理由から
ついに日の目をみずに終わってしまった問題。みなさんもこうした問題を一つ
くらい持っているのではないでしょうか?(…中略…)そんな下心を抱きながら、
勝手に『日の目を見なかった問題たち』シリーズをはじめることにしました。
本稿では勝手にはじめたこのシリーズの第2回目をやらせてもらいます
(『その3』は、どなたか引き継いで下さい)。
最近、会誌担当の NTT の田中さんが結婚されたそうで、
今回はお祝いを兼ねて『まだ日の目を見てない問題』を紹介することにします。
つまりうまく料理すれば日の目を見られるかもしれない、という問題です。
ここで取り上げるのはパズルの話です。一般化したXXパズルが NP 完全になる、
とか、制限されたグラフ上のXX問題は NP 完全になる、とか言った話が好きな
方、特にこういう証明の gadget 作りがたまらなく好きだ、という方、お楽し
み下さい。
倉庫番
| 図1:倉庫番のゲーム画面 |
|---|
 |
パズルの好きな人、あるいは私と同年代で、かつてパソコン小僧であった人で
あれば『倉庫番』というゲームをご存じだと思います。
人工知能の方で「倉庫番の面白い問題を作る」といった方向からの研究もされ
ている[MMH98j]ので、こうした経路でご存じの方もいらっしゃ
るかもしれません(ついでに WWW で調べてみたら[MMH96]や
[JS98]なんてのもひっかかりました。
人工知能の方ではそれなりにタイムリーなのかもしれません)。
パズルの画面は図1.のような感じです。
(これは私の愛機上で動く、xsok-1.02 on FreeBSD 版で
最初に出てくる問題です。最初の面なのにいきなり難しい…。)
ゲームの目的は、人間を操作して、すべての荷物を与えられたゴールポイント
に移動することです。人間は荷物を一つ、しかも押すことしかできません。
荷物を手前にひっぱったり、二つ以上同時に押すことはできません。
つまりコーナーに押し込んでしまったらその時点で終わりです。
また人間も一つの場所を占めるので、スキマのないところは通れません。
もちろん壁を押してもびくともしません。
本稿ではこの倉庫番を一般化し、n×nの盤面に拡張したゲームを考え
ます。つまり「与えられたn×nの大きさの倉庫番の盤面が解を持つか
どうか判定せよ」という問題を考えます。もちろん図1.の答は
Yes です。これが意外と難しいので、ちょっと考えてみて下さい。
『一般化された一人ゲーム？そりゃぁ、やっぱりNP完全でしょう』
と思ったそこのあなた、アマいです。結末がソレでは、
LA の会誌にはちと役不足です。
実はこのゲームが NP に属するかどうか、まだよくわかりません。
このあたりが本稿の『隠し味』なので、じっくりと堪能して下さい。
一般化倉庫番は NP 完全か??
『NP完全問題』は、文献[GJ79]などを調べればいくらでも見つけること
ができますが、典型的な問題をよく観察すると、ある共通した特徴があります。
それは、端的に言えば『ステップが一つ進むごとに、問題のナニカが単調に
減少する』というものです。例えばグラフの彩色問題であれば、ステップが一
つすすめば、彩色されていない頂点や辺が一つ減ります。
一人ゲームの例をあげれば、
文献[Iwa95,UI90]のHi-Qでは、
ステップが一つ進めば盤面上の石が必ず一つ減ります。
倉庫番はこうした特徴を持ちません。つまり人間をぐるぐる移動させたり、
荷物を一生懸命移動させたりしても、かならずしも盤面上の手数は減りません。
また一度ゴールポイントにおいた荷物を再度どけたりすることも可能です。
こうした特徴を上手に使えば、倉庫番はもっと上位のクラスに関する
完全問題であることが示せそうな気がしています。私自身は
だろう、と確信しています。
『なぜそう思うか』はここではヒミツにしてしまいます。
文献[Kas87]に載っているPSPACE完全問題を眺めると、なんとなく似た構
造をもった問題を見つけることができます、とだけ言っておきましょう…。
ありがちな一人ゲームはたいがい NP 完全で、
ありがちな二人ゲームはたいがい PSPACE 完全であることを考えれば、
この結果はそれなりに味わい深いのではないでしょうか。
蛇足
| 図2:Gadget たち |
|---|
 |
これで終わってしまっては、なんとなく尻つぼみなので NP困難であること
くらいは証明しておきましょう。
こうした gadget を上手に組み合わせれば、そのうち
PSPACE 完全であることも証明できるかもしれません。
ここでは以下のNP完全問題を倉庫番に還元することにします
[Iwa95,Ple79]。
- 入力:
- すべての頂点の次数が3の有向平面グラフG
- 問題:
- Gはハミルトン閉路をもつか？
この問題は非常に扱いやすく、グラフはたった2種類の頂点、つまり
(入次数1,出次数2)の頂点(タイプA)と、
(入次数2,出次数1)の頂点(タイプB)だけを含むとして一般性を失いません。
つまり頂点に対する gadget を2種類と、辺に対する gadget と、
それ以外のおまけの gadget を作ればよいことになります。
実際の gadget を図2.に示します。還元の方法は以下の通りです。
- 各頂点をタイプにあわせて gadget でおきかえる
- タイプBから出てタイプAに入る辺に『一方通行』のパターンを
入れる(曲がっているところは適当に『方向転換』のパターンを入れ
る)
- 上記以外の辺は普通につなぐ(曲がっているところは適当に『方向転換』
のパターンを入れる)
- 一方通行のパターンの入っている辺を一つ適当に選び、
『スタート』のパターンを埋め込む
普通ならこのあたりで、入力グラフの例と、それから作成されたゲームのパター
ンを示すものですが、ここでは力尽きて省略します。
与えられたグラフがハミルトン閉路を持つときは、
以下の方法に従うと、倉庫番も解を持つことが証明できます。
- スタート地点の人間は、隣の荷物を押しながら閉路にそって進む
- タイプBの頂点に来たら、荷物を押し付けて、もう一方の荷物を
中央の通路に押し込んで、そのまま中央の通路を先に進む
- タイプAの頂点に来たら
- 荷物をゴールポイントに置く
- 閉路ではない方の辺を手ぶらで進み、
その先のタイプBの頂点(ここはタイプBしかありえません)の中央付近
にある荷物を押しながら、この頂点にもう一度戻ってくる
- 押してきた荷物を、今度は閉路の方の辺に押し込んで、
先に進む
- すべての頂点を通過したら、スタート地点の隣にあるゴールポイントに
荷物をおいて終了
一方、ハミルトン閉路を持たない場合は、倉庫番の方も、
どうやってもすぐ手詰まりになってしまいます。
これは、よ〜く見て考えるとわかります。
かなりの手抜きではありますが、以上で NP 困難であることは証明できました。
蛇足の爪
倉庫番が PSPACE 完全であることは、どうすれば証明できるのでしょう。
ここではいいかげんな観測を書いて終わりにすることにします。
本稿の前の方では、文献[Kas87]に載っているPSPACE完全問題を眺めると、
なんとなく似た構造をもった問題を見つけることができます、と書いてありま
すが、これは実は7.2章の『一人石置きゲーム問題』をさしています。
石置きゲームでは、一つの共通の石を踏み台にして、
他の石が次々とこれを飛び越えていくようなルールを作ることができます。
これを倉庫番で実現しようとすると『一つの荷物をずぅっと押していくと、そ
の連鎖反応で、他の荷物をどんどん運び出せるような gadget』が上手に作れ
れば、なんとかなりそうです。
私の場合は、この部分がボトルネックになって、
とりあえずペンディングして、それっきりになっています。
蛇足の爪の垢
もし『倉庫番がXX完全である』ことが証明できたらどうかご一報下さい。
「共著にしろ」とか「謝辞に書け」とか、そんなケチ臭いことはいいません。
もしXXがPSPACE 以外だったら、何かおごらせて下さい。
- [MMH98j]
- 村瀬 芳生, 松原 仁, 平賀 譲.「倉庫番」の問題の自動作成.
情報処理学会論文誌, 39(3), 1998.
- [Kas87]
- 笠井琢美.計算量の理論.近代科学社, 1987.
- [Iwa95]
- 岩田茂樹.NP完全問題入門.共立出版, 1995.
- [GJ79]
- M.R. Garey and D.S. Johnson.
Computers and Intractability --- A Guide to the Theory of
NP-Completeness. Freeman, 1979.
- [JS98]
- A. Junghanns and J. Schaeffer.
Sokoban: Evaluating Standard Single-Agent Search Techniques in the
Presence of Deadlock.
In AI-98, pages 1-15. LNAI Vol. 1418, Springer-Verlag, 1998.
- [MMH96]
- Y. Murase, H. Matsubara, and Y. Hiraga.
Automatic Making of Sokoban Problems.
In PRICAI-96, pages 592-600. LNAI Vol. 1114,
Springer-Verlag, 1996.
- [Ple79]
- J. Plesník.
The NP-completeness of the Hamiltonian Cycle Problem in Planar
Digraphs with Degree Bound Two.
Information Processing Letters, 8(4):199-201, 1979.
- [UI90]
- R. Uehara and S. Iwata.
Generalized Hi-Q is NP-Complete.
The Transactions of the IEICE, E73(2):270-273, 1990.
