パーティションの細分化

アルゴリズム設計において、パーティション細分化とは、集合の分割を、その集合をより多くの小さな集合に分割することで細分化できるデータ構造として表現する手法である。この点において、パーティション細分化は、互いに素な集合への分割を維持するものの、操作によって集合のペアをマージするユニオンファインドデータ構造と双対関係にある。辞書式幅優先探索などのパーティション細分化の応用例では、データ構造は分割内の集合の順序も維持する。

パーティションの細分化は、 DFA 最小化、並列スケジューリングのためのCoffman–Graham アルゴリズム、グラフの辞書式幅優先探索など、グラフや有限オートマトン上のいくつかの効率的なアルゴリズムの重要な構成要素を形成します。^[¹^]^[²^]^[³^]

データ構造

分割細分化アルゴリズムは、互いに素な集合の族 $S i$ を維持します。アルゴリズムの開始時、この族はデータ構造内のすべての要素の単一の集合を含みます。アルゴリズムの各ステップで、集合 $X が$ アルゴリズムに提示され、 $X$ の要素を含む族内の各集合 $S i$ は、共通部分 $S$ $i$ $\cap$ $X$ と差分 $S$ $i$ $\$ $X$ の 2 つの集合に分割されます。

このようなアルゴリズムは、以下の情報を表すデータ構造を維持することによって効率的に実装できます。 ^{[ 4 ]}^{[ 5 ]}

ファミリー内の集合 $S i$ の順序付きシーケンス。新しい集合をシーケンスの途中に挿入できる二重リンクリストなどの形式で表される。
各集合 $S i$ には、その集合 $S$ $i$ の要素の集合が、二重リンクリストや配列データ構造などの形式で関連付けられ、集合から個々の要素を迅速に削除できるようになっている。あるいは、このデータ構造の構成要素は、すべての集合のすべての要素を、それらが属する集合の識別子でソートして単一の配列に格納し、任意の集合 $S$ $i$ の要素の集合を、この配列における開始位置と終了位置で表すことによって表現することもできる。
各要素には、それが属する集合が関連付けられています。

細分化操作を実行するために、アルゴリズムは与えられた集合 $Xの要素をループ処理します。各要素$ $x$ について、 $x$ を含む集合 $S i$ を見つけ、 $S$ $i$ $\cap$ $X$ の 2 番目の集合が既に開始されているかどうかを確認します。開始されていない場合は、2 番目の集合を作成し、 $S$ $i$ を操作によって分割された集合のリスト $L$ に追加します。次に、新しい集合が形成されたかどうかに関わらず、アルゴリズムは $x を$ $S$ $i$ から削除し、 $S$ $i$ $\cap$ $X$ に追加します。すべての要素が単一の配列に格納されている表現では、 $x$ をある集合から別の集合に移動するには、 $xを$ $S$ $i$ の最後の要素と交換し、 $S$ $i$ の終了インデックスと新しい集合の開始インデックスをデクリメントします。最後に、このようにして $X$ のすべての要素が処理された後、アルゴリズムは $L$ をループ処理し、現在の各集合 $S$ $i$ を、そこから分割された 2 番目の集合から分離し、これらの両方の集合が細分化操作によって新たに形成されたことを報告します。

このように単一の改良操作を実行するのにかかる時間は $O (| X |)であり、$ 集合族の要素数にも、データ構造内の集合の総数にも依存しません。したがって、一連の改良にかかる時間は、各改良ステップでアルゴリズムに渡される集合の総サイズに比例します。

アプリケーション

分割細分化の初期の応用例は、DFA 最小化のためのHopcroft (1971)のアルゴリズムである。この問題では、入力として決定性有限オートマトンが与えられ、可能な限り少ない状態を持つ同等のオートマトンを見つける必要がある。Hopcroft のアルゴリズムは、入力オートマトンの状態を部分集合に分割し、異なる部分集合内の任意の 2 つの状態が出力オートマトン内の異なる状態にマッピングされるという性質を維持する。最初は、オートマトンのすべての受理状態を含む部分集合と、残りの状態を含む部分集合の 2 つがある。各ステップで、部分集合 $S$ $i$ の 1 つとオートマトンの入力記号 $x$ の 1 つが選択され、状態の部分集合は、ラベル $xの遷移が$ $S$ $i$ につながる状態と、 $x$ 遷移が他の場所につながる状態に細分化される。既に選択された集合 $S$ $i が$ 精緻化によって分割される場合、結果として生じる 2 つの集合のうち (小さい方の集合) の 1 つだけを再度選択する必要があります。このようにして、各状態は $O$ $($ $s$ $log$ $n$ $)$ 回の精緻化ステップで集合 $X$ に参加し、アルゴリズム全体の処理時間は $O$ $($ $ns$ $log$ $n$ $)$ となります。ここで、 $n$ は初期状態の数、 $s$ はアルファベットのサイズです。^[⁶^]

パーティションの精緻化は、並列スケジューリングのためのコフマン・グラハムアルゴリズムの効率的な実装において、セティ (1976)によって適用されました。セティは、この手法を用いて、与えられた有向非巡回グラフの辞書式順序のトポロジカルソートを線形時間で構築できることを示しました。この辞書式順序のトポロジカルソートは、コフマン・グラハムアルゴリズムの重要なステップの 1 つです。このアプリケーションでは、互いに素な集合の要素は入力グラフの頂点であり、パーティションの精緻化に使用される集合 $X$ は頂点の近傍の集合です。すべての頂点の近傍の総数はグラフのエッジの数に等しいため、このアルゴリズムはエッジの数、つまり入力サイズに比例した時間で実行されます。^[⁷^]

パーティションの精緻化は、弦グラフやその他の重要なグラフクラスの認識に応用されるグラフ検索アルゴリズムである辞書式幅優先探索の重要なステップでもあります。ここでも、互いに素な集合の要素は頂点であり、集合 $X は$ 近傍の集合を表すため、アルゴリズムは線形時間で実行されます。^[⁸^]^[⁹^]

参考文献

↑ Paige, Robert; Tarjan, Robert E. (1987), "3つの分割細分化アルゴリズム", SIAM Journal on Computing , 16 (6): 973–989 , doi : 10.1137/0216062 , MR 0917035 。
↑ Habib, Michel; Paul, Christophe; Viennot, Laurent (1999)、「パーティション細分化手法：興味深いアルゴリズムツールキット」、International Journal of Foundations of Computer Science、10 (2): 147–170、doi : 10.1142/S0129054199000125、MR 1759929 。
↑ Habib, Michel; Paul, Christophe; Viennot, Laurent (1998), "A synthesis on partition refinement: a useful routine for strings, graphs, Boolean matrices and automata", in Morvan, Michel; Meinel, Christoph; Krob, Daniel (eds.), STACS 98: 15th Annual Symposium on Theoretical Aspects of Computer Science Paris, France, February 25–27, 1998, Proceedings (PDF) , Lecture Notes in Computer Science , vol. 1373, Springer-Verlag, pp. 25–38 , doi : 10.1007/BFb0028546 , ISBN 978-3-540-64230-5MR 1650757 。
↑ Valmari, Antti; Lehtinen, Petri (2008), "部分遷移関数を持つ DFA の効率的な最小化", Albers, Susanne ; Weil, Pascal (eds.), 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008) , Leibniz International Proceedings in Informatics (LIPIcs), vol. 1, Dagstuhl, Germany: Schloss Dagstuhl: Leibniz-Zentrum fuer Informatik, pp. 645– 656, arXiv : 0802.2826 , doi : 10.4230/LIPIcs.STACS.2008.1328 , ISBN 978-3-939897-06-4MR 2873773
↑ Knuutila, Timo (2001), "Hopcroftによるアルゴリズムの再記述", Theoretical Computer Science , 250 ( 1–2 ): 333–363 , doi : 10.1016/S0304-3975(99)00150-4 , ISSN 0304-3975
↑ホップクロフト、ジョン（1971）「有限オートマトンにおける状態を最小化するための $n$ $log$ $n$ アルゴリズム」、機械と計算の理論（国際シンポジウム議事録、テクニオン、ハイファ、1971年）、ニューヨーク：アカデミックプレス、pp. 189–196、MR 0403320 。
↑ Sethi, Ravi (1976)、「2つのプロセッサ上でのグラフのスケジューリング」、SIAM Journal on Computing、5 (1): 73–82、doi : 10.1137/0205005、MR 0398156 。
↑ Rose, DJ; Tarjan, RE ; Lueker, GS (1976)、「グラフ上の頂点除去のアルゴリズム的側面」、SIAM Journal on Computing、5 (2): 266– 283、doi : 10.1137/0205021。
↑ Corneil, Derek G. (2004), "辞書式幅優先探索 ― 概説", Hromkovič, Juraj; Nagl, Manfred; Westfechtel, Bernhard (編), Graph-Theoretic Methods in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers , Lecture Notes in Computer Science , vol. 3353, Springer-Verlag, pp. 1– 19, doi : 10.1007/978-3-540-30559-0_1 , ISBN 978-3-540-24132-4。

[1] Paige, Robert; Tarjan, Robert E. (1987), "3つの分割細分化アルゴリズム", SIAM Journal on Computing , 16 (6): 973–989 , doi : 10.1137/0216062 , MR 0917035 。

[2] Habib, Michel; Paul, Christophe; Viennot, Laurent (1999)、「パーティション細分化手法：興味深いアルゴリズムツールキット」、International Journal of Foundations of Computer Science、10 (2): 147–170、doi : 10.1142/S0129054199000125、MR 1759929 。

[3] Habib, Michel; Paul, Christophe; Viennot, Laurent (1998), "A synthesis on partition refinement: a useful routine for strings, graphs, Boolean matrices and automata", in Morvan, Michel; Meinel, Christoph; Krob, Daniel (eds.), STACS 98: 15th Annual Symposium on Theoretical Aspects of Computer Science Paris, France, February 25–27, 1998, Proceedings (PDF) , Lecture Notes in Computer Science , vol. 1373, Springer-Verlag, pp. 25–38 , doi : 10.1007/BFb0028546 , ISBN 978-3-540-64230-5MR 1650757 。

[4] Valmari, Antti; Lehtinen, Petri (2008), "部分遷移関数を持つ DFA の効率的な最小化", Albers, Susanne ; Weil, Pascal (eds.), 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008) , Leibniz International Proceedings in Informatics (LIPIcs), vol. 1, Dagstuhl, Germany: Schloss Dagstuhl: Leibniz-Zentrum fuer Informatik, pp. 645– 656, arXiv : 0802.2826 , doi : 10.4230/LIPIcs.STACS.2008.1328 , ISBN 978-3-939897-06-4MR 2873773

[5] Knuutila, Timo (2001), "Hopcroftによるアルゴリズムの再記述", Theoretical Computer Science , 250 ( 1–2 ): 333–363 , doi : 10.1016/S0304-3975(99)00150-4 , ISSN 0304-3975

[6] ホップクロフト、ジョン（1971）「有限オートマトンにおける状態を最小化するための $n$ $log$ $n$ アルゴリズム」、機械と計算の理論（国際シンポジウム議事録、テクニオン、ハイファ、1971年）、ニューヨーク：アカデミックプレス、pp. 189–196、MR 0403320 。

[7] Sethi, Ravi (1976)、「2つのプロセッサ上でのグラフのスケジューリング」、SIAM Journal on Computing、5 (1): 73–82、doi : 10.1137/0205005、MR 0398156 。

[8] Rose, DJ; Tarjan, RE ; Lueker, GS (1976)、「グラフ上の頂点除去のアルゴリズム的側面」、SIAM Journal on Computing、5 (2): 266– 283、doi : 10.1137/0205021。

[9] Corneil, Derek G. (2004), "辞書式幅優先探索 ― 概説", Hromkovič, Juraj; Nagl, Manfred; Westfechtel, Bernhard (編), Graph-Theoretic Methods in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers , Lecture Notes in Computer Science , vol. 3353, Springer-Verlag, pp. 1– 19, doi : 10.1007/978-3-540-30559-0_1 , ISBN 978-3-540-24132-4。

[

[

[

[ 4 ]

[ 5 ]

[

[

[

[