インターバル契約者

数学において、集合に関連付けられた区間コントラクター（または略してコントラクター） ^[1]は、別のボックス内の超長方形に関連付けられ、次の2つの特性が常に満たされる演算子です 。 ${\displaystyle X}$${\displaystyle C}$ ${\displaystyle [x]}$${\displaystyle {\mathbf {R}}^{n}}$${\displaystyle C([x])}$${\displaystyle {\mathbf {R}}^{n}}$

• ${\displaystyle C([x])\subset [x]}$（収縮性）

• ${\displaystyle C([x])\cap X=[x]\cap X}$（完全性特性）

制約（方程式や不等式など）に関連付けられたコントラクタは、制約を満たすすべての集合に関連付けられたコントラクタです。コントラクタを使用すると、区間解析で従来使用されている分岐限定アルゴリズムの効率を向上させることができます。 ${\displaystyle X}$${\displaystyle x}$

請負業者Cが単調であるとは、次の場合 です。 ${\displaystyle [x]\subset [y]\Rightarrow C([x])\subset C([y])}$

すべてのボックス [ x ] に対して が成り立つ場合、 それは最小です。ここで [ A ] は集合Aの区間包、つまりA を囲む最小のボックスです。 ${\displaystyle C([x])=[[x]\cap X]}$

すべての点xに対して、 { x } がx を単一の点として 囲む退化したボックスを表す場合、コントラクターC は薄いです。${\displaystyle C(\{x\})=\{x\}\cap X}$

契約者Cは、すべてのボックス[ x ] に対して、次が成り立つとき冪等である。${\displaystyle C\circ C([x])=C([x]).}$

契約者Cは、xを含む箱のすべてのシーケンス[ x ]( k )に対して、 ${\displaystyle [x](k)\rightarrow x\implies C([x](k))\rightarrow \{x\}\cap X.}$

図 1 は、灰色で塗られたセットXといくつかのボックスを表しており、そのうちのいくつかは退化しています (つまり、シングルトンに対応しています)。図 2 は、収縮後のこれらのボックスを表しています。Xの点は収縮者によって削除されていないことに注意してください。収縮者は、シアンのボックスに対しては最小ですが、緑のボックスに対しては悲観的です。退化したすべての青いボックスは、空のボックスに収縮されます。マゼンタのボックスと赤いボックスは収縮できません。

より複雑なコントラクタを構築するために、コントラクタに対していくつかの操作を実行することができます。 ^[2] 交差、和集合、合成、繰り返しは次のように定義されます。

${\displaystyle (C_{1}\cap C_{2})([x])=C_{1}([x])\cap C_{2}([x])}$

${\displaystyle (C_{1}\cup C_{2})([x])=[C_{1}([x])\cup C_{2}([x])]}$

${\displaystyle (C_{1}\circ C_{2})([x])=C_{1}(C_{2}([x]))}$

${\displaystyle C^{\infty }([x])=C\circ C\circ C\circ \cdots \circ C([x])}$

方程式や不等式、例えばf ( x )in[ y ]に関連するコントラクターを構築するにはさまざまな方法があります。そのほとんどは区間演算に基づいています。最も効率的でシンプルな方法の1つは、前方/後方コントラクター（HC4-reviseとも呼ばれます）です。^{[3] [4]}

原理は、区間演算を使用してf ( x )を評価することです(これが前進ステップです)。 結果として得られる区間は[ y ]と交差します。 次に、 x _iの区間を縮小するためにf ( x )の後退評価が実行されます(これが後退ステップです)。 ここで、簡単な例で原理を説明します。

制約を考慮すると、 2つの中間 変数aとbを導入することで関数f ( x )を次のように 評価できる。${\displaystyle (x_{1}+x_{2})\cdot x_{3}\in [1,2].}$

${\displaystyle a=x_{1}+x_{2}}$

${\displaystyle b=a\cdot x_{3}}$

前の2つの制約は順方向制約と呼ばれます。逆方向制約は 、各順方向制約を逆順に取り、各変数を右側に分離することで 得られます。

${\displaystyle x_{3}={\frac {b}{a}}}$

${\displaystyle a={\frac {b}{x_{3}}}}$

${\displaystyle x_{1}=a-x_{2}}$

${\displaystyle x_{2}=a-x_{1}}$

結果として得られるフォワード/バックワード契約者は、 区間分析を 使用してフォワード制約とバックワード制約を評価することによって得られます。 ${\displaystyle C([x_{1}],[x_{2}],[x_{3}])}$

${\displaystyle [a]=[x_{1}]+[x_{2}]}$

${\displaystyle [b]=[a]\cdot [x_{3}]}$

${\displaystyle [b]=[b]\cap [1,2]}$

${\displaystyle [x_{3}]=[x_{3}]\ \cap \ {\frac {[b]}{[a]}}}$

${\displaystyle [a]=[a]\cap {\frac {[b]}{[x_{3}]}}}$

${\displaystyle [x_{1}]=[x_{1}]\ \cap \ \ [a]-[x_{2}]}$

${\displaystyle [x_{2}]=[x_{2}]\ \cap \ \ [a]-[x_{1}]}$