十文字法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/05/09 09:17 UTC 版)
十文字法（じゅうもんじほう、英: criss-cross alogorithm）とは、数理最適化における線形計画問題に対するアルゴリズムの一種である。十文字法と同様の解法は線形不等式付き非線形の目的関数の問題や、分数計画問題[1][2]、二次計画問題、線形相補性問題に対して適用されている[3]。
ダンツィーグの単体法と同様に、十文字法は線形計画問題に対しては多項式時間アルゴリズムではない。両者のアルゴリズムも（ヴィクター・クレー、ジョージ・ミンティによって提案された）D次元の立方体を巧妙にひずませたKlee-Minty立方体に対しては最適頂点解に到達するまでに 2D 回頂点を訪れることになるため、最悪時間計算量を示す[4][5]。しかしながら、初期の頂点解をランダムな頂点で開始した場合、十文字法は平均反復回数は約D回で終える[6][7][8]。すなわち、3次元の多面体では平均では3頂点を訪れ、最悪の場合では8頂点を訪れることになる。
歴史
十文字法はTamas Terlaky[9]、Zhe-Min Wang[10]のそれぞれが独立して提案した解法である[3]。
線形計画問題に対する単体法との比較
線形計画問題では、十文字法が生成する基底解の列は単体法とは異なっている。単体法は第一段階目として（主）実行可能性を満たす基底解を探索し、二段階目でピボット規則に従って目的関数値を減少させるような点列を生成し、最終的に（双対実行可能性を満たす）最適解を求める[3][11]。
一方、十文字法は一段階のみで完結する解法であるという意味で簡明な解法である。そして十文字法で使用されるピボット規則はBlandの最小添字規則に類似している[12]。 Blandの規則では選択基準として被約費用の係数の符号が負の中から基底に入る変数と出る変数を決める[12][注釈 1]。一方で十文字法はBlandの規則とは異なって完全に組合せ的解法であり、係数の符号のみを考慮して基底に入る変数と出る変数を選択する[3][11]。十文字法は線形代数におけるいくつかの定理（ファルカスの補題など）の建設的な証明にも応用されている[13]。
多くの単体法に類似される解法は目的関数値を改善するような解（非退化仮定の下では厳密に改善される）を生成するのに対し、十文字法に類似される解法は目的関数をより良くする保証がされないため、この面においては不利な解法である。
説明
十文字法は標準的なピボットタブロー（もしくは単体表をその都度求めるような改訂型単体法のように行列表現で実装した場合）上で実行できる。一般的な方法はピボットタブローが（主・双対）実行不可能な場合、ピボット選択規則によって実行不可能な行・列の中から一つををピボット行・列として選択する。十文字法の重要な特性として選択は（主・双対）実行可能性を満たさない添字の集合に対して行われ、（主・双対）単体法のような基底交換に基づく解法での列・行のみの添字などの区別されない点が挙げられる。 行を選択した場合は双対型のピボットによって入れ替える列の位置を特定し、あるいは列を選択した場合は主型のピボットによって入れ替える行の位置を特定する。
計算複雑度: 最悪時間計算量
アルゴリズムの時間計算量とは問題を解くために必要な算術演算の回数のを表したものである。具体例として、ガウスの消去法は高々 D3 に比例した反復を要するため、三次関数の多項式時間計算量に区分される。また多項式時間計算量を有さないアルゴリズムも存在する。具体例として、ガウスの消去法を一般化したアルゴリズムのブッフベルガーのアルゴリズムは問題の入力データ量（多項式の次数・多変数多項式の総変数）に対して指数時間計算量を有するアルゴリズムである。指数関数は多項式関数よりも急速に増大することから、指数時間計算量の解法は規模の大きな問題に対して高い性能を発揮できないことを意味する。
カチヤンの楕円体法、カーマーカーの射影変換法、中心パス追跡法等の線形計画問題に対する解法は（最悪時・平均時間計算量において）多項式時間アルゴリズムである。楕円体法、射影変換法は十文字法より前に提案された解法である。
しかしながらダンツィークの単体法と同様に、線形計画問題に対する十文字法は多項式時間アルゴリズムでない。Terlakyの十文字法は単体法で 2D回の反復を要するKlee–Minty立方体を少し修正し、D次元のひずませた立方体に対して2D個の頂点すべてを訪れることをルーシュによって示された[3][4][5]。単体法と同様に、十文字法は3次元の場合最悪時に立方体の全8頂点訪れることになる。
立方体のランダムな頂点を初期解としたとき、十文字法は平均でD回の頂点を訪れることを1994年福田、並木によって主張された[6][7]。これは容易に確かめることができ、単体法も立方体に対して平均 D 回の反復で終了する[8][注釈 2]。単体法と同様に、十文字法は3次元の立方体の頂点を平均3回訪れる。
類似のアルゴリズム
十文字法は線形計画問題より一般的な最適化問題に対して拡張されている。
他の線形制約付き問題に対する応用
他の問題に対する十文字法の変種解法として線形計画問題、二次計画問題、単調な線形相補性問題が挙げられる[3][6][14][15][16][17]。逆に言えば、十文字法は線形相補性問題において行列が十分行列であるときのみ有限回の反復で終了する[16][17]。十分行列は正定値行列およびP行列を一般化させた行列で、小行列式がすべて正の値をとる[16][17][18]。また十文字法は分数計画問題についても適用することができる[1][2]。
頂点列挙
十文字法は1992年ディビッド・エイビス、福田公明によって多面体の全頂点列挙を求めるアルゴリズムとして提案された[19]。
エイビスと福田は D 次元において非退化な n 個の線形不等式系から構成される多面体に含まれる v 個の頂点を求める（また双対的には D 次元においてファセットを構成する D 個の点を含む n 個の点の凸包のファセットを v 個列挙する）アルゴリズムを提案した。このアルゴリズムは時間計算量が O(nDv)、空間計算量が 
| 一般 | |
|---|---|
| 微分可能 |
| 凸最小化 | |||||||
|---|---|---|---|---|---|---|---|
| 線形 および 二次 |
|
| 系列範例 (Paradigms) | |||||
|---|---|---|---|---|---|
| グラフ理論 |
| ||||
| ネットワークフロー (最大流問題) |
