再構成

離散数学と理論計算機科学において、再構成問題は状態空間の到達可能性または接続性を伴う計算問題です。

問題の種類

ここで、状態空間とは、状態と呼ばれるシステムの構成または組み合わせ問題の解の離散的な集合と、ある状態を別の状態にリンクする一連の許容される動きの集合です。再構成問題では、次のようなことが問われることがあります。

特定の問題クラスでは、状態空間は常に接続されていますか? つまり、一連の動作ですべての状態のペアを相互に変換できますか? そうでない場合、特定の問題の状態空間が接続されているかどうかを判断する計算の複雑さはどの程度ですか?
状態空間の直径、つまり、2 つの状態を最大 $D 回$ の移動で相互に変換できる最小の数 $D$ はいくらですか?
2 つの状態が与えられた場合、それらを相互に変換できるかどうかを判断すること、または一方を他方に変換するための最短の動作シーケンスを見つけることの複雑さはどの程度でしょうか。
慎重に選択された確率分布でランダムに動きが選択され、結果として得られるマルコフ連鎖が離散一様分布に収束する場合、ランダムウォークの最後の状態がほぼ一様分布になるようにするには、ランダムウォークに何回の動きが必要ですか? つまり、マルコフ連鎖の混合時間はどれくらいですか?

例

再構成で研究される問題の例には次のものがあります。

15パズルやルービックキューブなどのゲームやパズル。このタイプのパズルは、多くの場合、順列群の理論を使用して数学的にモデル化することができ、状態が接続されているかどうかを判断するための高速アルゴリズムにつながります。ただし、状態空間の直径、つまり2つの状態間の最短経路を見つけることは難しい場合があります。たとえば、ルービックキューブのバージョンの場合、状態空間の直径はであり、最短解を見つける複雑さは不明ですが、パズルの一般化バージョン（一部のキューブ面がラベル付けされていない）の場合、NP困難です。^[1]Sokobanなどの他の再構成パズルは、トークン再構成としてモデル化できますが、群論的構造がありません。このような問題の場合、複雑さはより高くなる可能性があります。特に、Sokobanの到達可能性のテストはPSPACE完全です。^[2] $n\times n\times n$ $\Theta (n^{2}/\log n)$
二分木の回転距離と、フリップグラフの反転距離に関連する問題。回転は、二分木の構造を、ノードの左から右への順序付けに影響を与えずに変更する操作であり、二分探索木のバランス調整によく使用されます。回転距離は、ある木を別の木に変換するために必要な回転の最小回数です。同じ状態空間は、凸多角形の三角形分割もモデル化し、多角形の対角線を 1 つ削除して別の対角線に置き換えることで、ある三角形分割を別の三角形分割に「反転」します。同様の問題は、他の種類の三角形分割でも研究されています。特定の数のノードを持つ 2 つの木間の最大回転距離はわかっていますが^{[3] 、任意の 2 つの木間の回転距離を}多項式時間で見つけることができるかどうかは未解決の問題です^[4]。点集合または非凸多角形の三角形分割間の反転距離に関する類似の問題は、NP 困難です^[5]^{[6] 。}
グラフ彩色の再構成。彩色の再構成のために考えられてきた動きには、単一頂点の色の変更や、ケンペ連鎖の色を入れ替えることなどがある。色の数が少なくとも 2プラスグラフの退化である場合、単一頂点の彩色状態空間は連結しており、セレセダの予想によれば、多項式直径を持つ。色数が少ない場合、一部のグラフは連結されていない状態空間を持つ。3 彩色の場合、単一頂点の彩色状態空間の大域的連結性をテストすることは、共 NP 完全である^[7]が、2 つの彩色を互いに再構成できる場合、最短の再構成シーケンスは多項式時間で見つけることができる。^[8] 3 色以上の場合、単一頂点の再構成は PSPACE 完全である。^[9]
非決定性制約論理は、赤と青のエッジを持つ立方体グラフの向きに関する組み合わせ問題です。システムの有効な状態では、各頂点には少なくとも 1 つの青いエッジ、または少なくとも 2 つのエッジが入らなければなりません。この状態空間での移動は、これらの制約を維持しながら、1 つのエッジの向きを反転します。基になるグラフの帯域幅が制限されている場合でも、結果の状態空間が接続されているかどうか、または 2 つの状態が互いに到達可能かどうかをテストすることはPSPACE 完全です。^[10]これらの困難性の結果は、ゲームやパズルから生じる問題など、他の再構成問題も困難であることを証明する縮小の基礎としてよく使用されます。 ^[11]

参考文献

^ Demaine, Erik D. ; Demaine, Martin L. ; Eisenstat, Sarah; Lubiw, Anna ; Winslow, Andrew (2011)、「ルービックキューブを解くアルゴリズム」、アルゴリズム – ESA 2011: 第 19 回欧州シンポジウム、ザールブリュッケン、ドイツ、2011 年 9 月 5 ～ 9 日、議事録、Lecture Notes in Computer Science、vol. 6942、Springer、ハイデルベルク、pp. 689 ～ 700、arXiv : 1106.5736、doi :10.1007/978-3-642-23719-5_58、ISBN 978-3-642-23718-8、MR 2893242、S2CID 664306
^ Culberson, Joseph (1997)、Sokoban は PSPACE 完全です、技術レポート TR97-02、アルバータ大学、コンピューティング科学部、doi :10.7939/R3JM23K33、hdl : 10048/27119
^ Pournin, Lionel (2014)、「連想面体の直径」、Advances in Mathematics、259 : 13–42、arXiv : 1207.6296、doi : 10.1016/j.aim.2014.02.035、MR 3197650
^ Kanj, Iyad; Sedgwick, Eric; Xia, Ge (2017)、「三角形分割間の反転距離の計算」、Discrete & Computational Geometry、58 (2): 313–344、arXiv : 1407.1525、doi :10.1007/s00454-017-9867-x、MR 3679938、S2CID 254033552
^ Lubiw, Anna ; Pathak, Vinayak (2015)、「点集合の 2 つの三角形分割間の反転距離は NP 完全である」、計算幾何学、49 : 17–23、arXiv : 1205.2425、doi : 10.1016/j.comgeo.2014.11.001、MR 3399985
^ Aichholzer, Oswin; Mulzer, Wolfgang; Pilz, Alexander (2015)、「単純な多角形の三角形分割間の反転距離は NP 完全である」、Discrete & Computational Geometry、54 (2): 368–389、arXiv : 1209.0579、doi :10.1007/s00454-015-9709-7、MR 3372115、S2CID 254037222
^ Cereceda, Luis (2007)、グラフカラーリングの混合、博士論文、ロンドン・スクール・オブ・エコノミクス特に109ページを参照してください。
^ ジョンソン、マシュー;クラッチュ、ディーター。クラッチ、ステファン。パテル、ヴィレシュ。 Paulusma、Daniël (2016)、「グラフの色分け間の最短パスの検索」(PDF)、Algorithmica、75 (2): 295–321、doi :10.1007/s00453-015-0009-7、MR 3506195、S2CID 253974066
^ Bonsma, Paul; Cereceda, Luis (2009)、「グラフカラーリング間のパスの検索: PSPACE 完全性と超多項式距離」、理論計算機科学、410 (50): 5215–5226、doi :10.1016/j.tcs.2009.08.023、MR 2573973
^ van der Zanden, Tom C. (2015)、「グラフ制約ロジックのパラメータ化された複雑さ」、第 10 回パラメータ化および正確な計算に関する国際シンポジウム、LIPIcs. Leibniz Int. Proc. Inform.、vol. 43、Schloss Dagstuhl. Leibniz-Zent. Inform.、Wadern、pp. 282–293、arXiv : 1509.02683、doi : 10.4230/LIPIcs.IPEC.2015.282、MR 3452428、S2CID 15959029
^ Hearn, Robert A. ; Demaine, Erik D. (2005)、「非決定論的制約論理計算モデルによるスライディングブロックパズルおよびその他の問題の PSPACE 完全性」、理論計算機科学、343 (1–2): 72–96、arXiv : cs/0205005、doi :10.1016/j.tcs.2005.05.008、MR 2168845、S2CID 656067

外部リンク

組み合わせ再構成リソース（網羅的ではない参考文献を含む）

[rubik-1] Demaine, Erik D. ; Demaine, Martin L. ; Eisenstat, Sarah; Lubiw, Anna ; Winslow, Andrew (2011)、「ルービックキューブを解くアルゴリズム」、アルゴリズム – ESA 2011: 第 19 回欧州シンポジウム、ザールブリュッケン、ドイツ、2011 年 9 月 5 ～ 9 日、議事録、Lecture Notes in Computer Science、vol. 6942、Springer、ハイデルベルク、pp. 689 ～ 700、arXiv : 1106.5736、doi :10.1007/978-3-642-23719-5_58、ISBN 978-3-642-23718-8、MR 2893242、S2CID 664306

[sokoban-2] Culberson, Joseph (1997)、Sokoban は PSPACE 完全です、技術レポート TR97-02、アルバータ大学、コンピューティング科学部、doi :10.7939/R3JM23K33、hdl : 10048/27119

[pournin-3] Pournin, Lionel (2014)、「連想面体の直径」、Advances in Mathematics、259 : 13–42、arXiv : 1207.6296、doi : 10.1016/j.aim.2014.02.035、MR 3197650

[ksx-4] Kanj, Iyad; Sedgwick, Eric; Xia, Ge (2017)、「三角形分割間の反転距離の計算」、Discrete & Computational Geometry、58 (2): 313–344、arXiv : 1407.1525、doi :10.1007/s00454-017-9867-x、MR 3679938、S2CID 254033552

[pointflip-5] Lubiw, Anna ; Pathak, Vinayak (2015)、「点集合の 2 つの三角形分割間の反転距離は NP 完全である」、計算幾何学、49 : 17–23、arXiv : 1205.2425、doi : 10.1016/j.comgeo.2014.11.001、MR 3399985

[polyflip-6] Aichholzer, Oswin; Mulzer, Wolfgang; Pilz, Alexander (2015)、「単純な多角形の三角形分割間の反転距離は NP 完全である」、Discrete & Computational Geometry、54 (2): 368–389、arXiv : 1209.0579、doi :10.1007/s00454-015-9709-7、MR 3372115、S2CID 254037222

[cereceda-7] Cereceda, Luis (2007)、グラフカラーリングの混合、博士論文、ロンドン・スクール・オブ・エコノミクス特に109ページを参照してください。

[jkkpp-8] ジョンソン、マシュー;クラッチュ、ディーター。クラッチ、ステファン。パテル、ヴィレシュ。 Paulusma、Daniël (2016)、「グラフの色分け間の最短パスの検索」(PDF)、Algorithmica、75 (2): 295–321、doi :10.1007/s00453-015-0009-7、MR 3506195、S2CID 253974066

[boncer-9] Bonsma, Paul; Cereceda, Luis (2009)、「グラフカラーリング間のパスの検索: PSPACE 完全性と超多項式距離」、理論計算機科学、410 (50): 5215–5226、doi :10.1016/j.tcs.2009.08.023、MR 2573973

[nclband-10] van der Zanden, Tom C. (2015)、「グラフ制約ロジックのパラメータ化された複雑さ」、第 10 回パラメータ化および正確な計算に関する国際シンポジウム、LIPIcs. Leibniz Int. Proc. Inform.、vol. 43、Schloss Dagstuhl. Leibniz-Zent. Inform.、Wadern、pp. 282–293、arXiv : 1509.02683、doi : 10.4230/LIPIcs.IPEC.2015.282、MR 3452428、S2CID 15959029

[nclpuzzle-11] Hearn, Robert A. ; Demaine, Erik D. (2005)、「非決定論的制約論理計算モデルによるスライディングブロックパズルおよびその他の問題の PSPACE 完全性」、理論計算機科学、343 (1–2): 72–96、arXiv : cs/0205005、doi :10.1016/j.tcs.2005.05.008、MR 2168845、S2CID 656067