差分マップアルゴリズム

差分マップ アルゴリズムは、一般的な制約充足問題のための検索アルゴリズムです。制約セットへの投影を実行するより基本的なアルゴリズムから構築されているという意味で、メタアルゴリズムです。数学的な観点から見ると、差分マップ アルゴリズムはユークリッド空間のマッピングに基づく動的システムです。ソリューションはマッピングの 固定点としてエンコードされます。

差分マップアルゴリズムは、もともと位相問題を解くための一般的な方法として考え出されましたが、ブール充足問題、タンパク質構造予測、ラムゼー数、ディオファントス方程式、数独^[1]のほか、球詰め問題や円盤詰め問題^[2]にも使用されています。これらの応用にはNP完全問題が含まれるため、差分マップの範囲は不完全なアルゴリズムの範囲です。不完全なアルゴリズムは、（候補が見つかったら）解を効率的に検証できますが、解が存在しないことを証明することはできません。

差分マップアルゴリズムは、位相回復のためのフィナップのハイブリッド入力出力（HIO）アルゴリズム^[3]と凸最適化のためのダグラス-ラチフォードアルゴリズム^{[4]という2つの}反復法を一般化したものです。反復法は一般に、位相回復と凸最適化において長い歴史を持っています。このスタイルのアルゴリズムを困難な非凸問題に使用するのは、比較的最近の開発です。

解決すべき問題は、まずユークリッド空間における集合交差問題として定式化されなければなりません。集合との交差においてを見つけます。もう 1 つの前提条件は、任意の入力点 が与えられたときに、制約集合または の中で に最も近い点を返す射影およびの実装です。アルゴリズムの 1 回の反復は、マッピングによって与えられます。 ${\displaystyle x}$${\displaystyle A}$${\displaystyle B}$${\displaystyle P_{A}}$${\displaystyle P_{B}}$${\displaystyle x}$${\displaystyle A}$${\displaystyle B}$${\displaystyle x}$

${\displaystyle {\begin{aligned}x\mapsto D(x)&=x+\beta \left[P_{A}\left(f_{B}(x)\right)-P_{B}\left(f_{A}(x)\right)\right],\\f_{A}(x)&=P_{A}(x)-{\frac {1}{\beta }}\left(P_{A}(x)-x\right),\\f_{B}(x)&=P_{B}(x)+{\frac {1}{\beta }}\left(P_{B}(x)-x\right)\end{aligned}}}$

実パラメータは0 であってはなりませんが、どちらの符号でもかまいません。最適な値はアプリケーションによって異なり、実験によって決定されます。最初の推測としては、反復ごとの投影計算の回数を減らすため、 (または) を選択することをお勧めします。${\displaystyle \beta}$${\displaystyle \beta =1}$${\displaystyle \beta =-1}$

${\displaystyle D(x)=x+P_{A}\left(2P_{B}(x)-x\right)-P_{B}(x)}$

点が マップの不動点となるのは、まさに の場合です。左辺は の要素で右辺は の要素なので、この等式は 2 つの制約セットに共通の要素が見つかったことを意味します。不動点自体はまたは のどちらかに属する必要はないことに注意してください。不動点の集合は、通常、解の集合よりもはるかに高い次元を持ちます。 ${\displaystyle x}$${\displaystyle x\mapsto D(x)}$${\displaystyle P_{A}\left(f_{B}(x)\right)=P_{B}\left(f_{A}(x)\right)}$${\displaystyle A}$${\displaystyle B}$${\displaystyle x}$${\displaystyle A}$${\displaystyle B}$

アルゴリズムの進行状況は、2 つの投影の差のノルムを調べることで監視できます。

${\displaystyle \Delta =\left|P_{A}\left(f_{B}(x)\right)-P_{B}\left(f_{A}(x)\right)\right|}$。

これが消えると、両方の制約セットに共通する点が見つかったことになり、アルゴリズムを終了できます。

確率的局所探索などの不完全なアルゴリズムは、ブール式に対する満足のいく真理値の割り当てを見つけるために広く使用されています。 差分マップ アルゴリズムを使用して2-SATのインスタンスを解決する例として、次の式を考えます (~ は NOT を示します)。

( q ₁またはq ₂ ) かつ (~ q ₁またはq ₃ ) かつ (~ q ₂または ~ q ₃ ) かつ ( q ₁または ~ q ₂ )

この式の 8 つのリテラルのそれぞれに、8 次元ユークリッド空間内の実変数を 1 つ割り当てます。これらの変数を表に並べると、2-SAT 式の構造を復元できます。

行は 2-SAT 式の節で、同じブール変数に対応するリテラルは列に配置され、否定は括弧で示されます。たとえば、実変数x ₁₁、x ₂₁、x _{41 は}同じブール変数 ( q ₁ ) またはその否定に対応し、レプリカと呼ばれます。値 1 と -1 を、従来の 1 と 0 ではなく、 TRUEとFALSEに関連付けると便利です。この規則により、レプリカ間の互換性は次の線形方程式の形になります。

x ₁₁ = - x ₂₁ = x ₄₁

× ₁₂ = - × ₃₁ = - × ₄₂

× ₂₂ = - × ₃₂

これらの方程式が満たされる線形部分空間は、差分マップで使用される制約空間の 1 つ (たとえばA ) です。この制約に投影するには、各レプリカを符号付きレプリカ平均、またはその負の数に置き換えます。

1 = ( x _{11 -} x ₂₁ + x ₄₁ ) / 3

x ₁₁ → 1 x _{21 →} - 1 x ₄₁ → 1_{​   ​}  

2 番目の差分マップ制約は、表の行、つまり節に適用されます。 満足のいく割り当てでは、各行の 2 つの変数に値 (1, 1)、(1, -1)、または (-1, 1) を割り当てる必要があります。 対応する制約セットBは、したがって 3 ⁴ = 81 点のセットになります。 この制約に投影すると、各行に次の操作が適用されます。 まず、2 つの実数値が 1 または -1 に丸められます。 次に、結果が (-1, -1) の場合、2 つの元の値のうち大きい方が 1 に置き換えられます。 例:

(-.2, 1.2) → (-1, 1)

(-.2, -.8) → (1, -1)

説明した両方の射影演算が入力値と出力値の間のユークリッド距離を最小化することを確認するのは簡単な作業です。さらに、アルゴリズムが両方の制約セット内にある点x を見つけることに成功した場合、(i) xに関連付けられた句がすべてTRUEであり、(ii) レプリカへの割り当てが元のブール変数への真の割り当てと一致していることがわかります。

アルゴリズムを実行するには、まず初期点x ₀を生成する。

β = 1 の場合、次のステップはP _B ( x ₀ ) を計算することです。

これに続いて2 P _B ( x ₀ ) - x ₀、

そして、他の制約P _A (2 P _B ( x ₀ ) - x ₀ )に投影されます。

2つの投影の差だけx _{0 を}増やすと、差分マップの最初の反復D ( x ₀ ) = x ₁が得られます 。

2回目の反復D ( x ₁ ) = x ₂は次のようになります 。

これは固定点です: D ( x ₂ ) = x ₂。2つの射影が一致するため、反復は変更されません。P _B ( x ₂ ) から、

満足な真理値の割り当てを読み取ることができます: q ₁ = TRUE、q ₂ = FALSE、q ₃ = TRUE。

上記の単純な 2-SAT の例では、差分マップの増分Δのノルムは、3 回の反復で単調に 0 に減少しました。これは、差分マップに3-SATのハードインスタンスが与えられたときのΔの動作とは対照的です。このハードインスタンスでは、固定点の発見前に Δ が大きく変動します。動的システムとして、差分マップはカオス的であり、検索されている空間はストレンジ アトラクターであると考えられています。

位相回復では、信号または画像は、その離散フーリエ変換の係数（絶対値、大きさ）から再構成されます。たとえば、係数データのソースは、物体がコヒーレント光で照らされたときに形成されるフラウンホーファー回折パターンである可能性があります。

フーリエ係数制約への投影、たとえばP _{A は}、最初に信号または画像の離散フーリエ変換を計算し、データと一致するように係数を再スケーリングし、次に結果を逆変換することによって実現されます。これは、制約までのユークリッド距離が最小化されるという意味で投影です。これは、(i) 離散フーリエ変換はユニタリ変換として距離を維持し、(ii) 係数の再スケーリング (位相を変更せずに) が係数制約を実現する最小の変更であるためです。

フーリエ変換の未知の位相を回復するために、差分マップは別の制約P _Bへの投影に依存します。再構成されるオブジェクトが正であること、境界付きサポートを持つことなどがわかっている場合、これはいくつかの形式を取ることができます。たとえば、表面画像の再構成では、投影P _Bの効果は、長方形のサポートの外側のすべての値をゼロにし、サポート内のすべての負の値もゼロにすることでした。

• 数独ソルバー - 差分マップ アルゴリズムに基づく数独ソルバー。