劣モジュラな2次擬似ブール関数の最小化問題 #3
劣モジュラな2次擬似ブール関数の最小化問題は、フローネットワークの最大フロー問題を介して効率的に解けるそうです。専門用語だらけでぎょっとしますが、概要をいくつかの記事で解説したいと思います。
解説記事のラインアップ
「劣モジュラな2次擬似ブール関数の最小化問題は、フローネットワークの最大フロー問題を介して効率的に解ける」ことの概要を下記の順で記事にする予定です。
①2次疑似ブール関数とその劣モジュラ性
②劣モジュラな2次疑似ブール関数が持つ特徴
③劣モジュラな2次疑似ブール関数を表すフローネットワーク
④劣モジュラな2次疑似ブール関数を表すフローネットワークの最大フローと、元の関数の最小値の対応
この記事では、「③劣モジュラな2次疑似ブール関数を表すフローネットワーク」を解説します。
フローネットワーク
まずはフローネットワークとは何かを説明したいと思います。フローネットワークとはモノの流れを抽象的に表したものです。例えば、以下がフローネットワークです。
この例を用いて説明します。まず例に登場する要素ですが、円がノードと呼ばれる、モノが集められたり出ていく所です。「○にS」のノードはモノの出発点、「○にT」は到達点で、その他のノードは中継点を表しています。矢印はエッジと呼ばれノードの間の道を表します。エッジの近くに書かれた数値はキャパシティと呼ばれ、矢印方向へのモノの流れの許容量を表します。例えば、ノードB(「○にB」のノード)から、ノードAに、2と書かれたエッジがありますが、これはノードBからノードAは2の量のモノが流せることを意味します。
次に、フローネットワークの動き(のようなもの)を説明します。このフローネットワークの、ノードSからノードTまで最大どれくらいの量のモノが流せるかを考えてみましょう。ルールとして、ノードSには非常に多くのモノが置いてあり、(エッジのキャパ以内であれば)それらを送ることができるとします。ノードTには大量にモノが置けるとします。そして、中継地のノードは受け取ったものをすぐに送るので、中継地へ入ってくるモノの合計流量と出て行くモノの合計流量は同じとします。(因みに、フローネットワークのノードSからノードTへの最大流量を求める問題を、フローネットワークの最大フロー問題と呼びます。)
このルールに則り、ノードSからTへの流量を最大にするモノの流れは例えば下図になります。
エッジの近くに「数値/数値」とありますが、左側の数値は流量を表し、右側の数値はキャパシティを表します。上図は、ノードS→ノードA→ノードC→ノードTへ、それぞれ1の量のモノを送る流れを表しています。他にも色々な流れが考えられますが、ノードAからノードCへのキャパシティ1のエッジがボトルネックとなり、1より大きな量はノードSからノードTへ流すことができません。よって、このフローネットワークのノードSからTへの流量の最大値は1となります。
劣モジュラな2次疑似ブール関数からフローネットワークを構成する方法
このフローネットワークを、劣モジュラな2次疑似ブール関数から構成する手順を紹介します。天下り的ですが、大まかな手順を説明しますと、まずⓐ劣モジュラな2次疑似ブール関数の式変形を行い、ⓑ関数の変数に対応するノードを置き、ⓒ変形後の式の項に対応するエッジを追加します。
ⓐ劣モジュラな2次疑似ブール関数の式変形
フローネットワークへ変換しやすいように劣モジュラな2次疑似ブール関数を式変形します。おさらいですが、2次疑似ブール関数は以下の形をしています。
$$
f(X)=\sum_{i j} a_{i j}x_i x_j + c
$$
ここで、$${X=x_1, \dots, x_n}$$は0か1をとる変数で、$${a_{i j}}$$と$${c}$$は整数とします。そして、$${f}$$が劣モジュラな時は、異なる変数の積の係数すべてが0以下(つまり$${\forall_{i,j : i\not=j}\; a_{i j}\le 0}$$)となります。
式変形の目的は、関数内の「変数がある項の係数」の全てを正にすることです。では式変形の詳細を説明します。
まず異なる変数の積の項(e.g., $${a_{i j} x_i x_j}$$)に対する式変形として以下を行います。
$$
\begin{array}{l}
a_{i j} x_i x_j + a_{j i}x_j x_i \\
\;\;\;\Rightarrow -(a_{i j}+a_{j i})x_i (1-x_j) + (a_{i j}+a_{j i})x_i x_i
\end{array}
$$
ここで$${i < j}$$とします。次に、この式変形でできた同じ変数の積の項(e.g., $${a_{i i} x_i x_i}$$)と、もともと関数$${f}$$にあった同じ変数の積の項を足します。ここで足した結果を$${b_i x_i x_i}$$と書きます。次に以下の式変形を同じ変数の積でできた項に行います。
$$
\begin{array}{lc}
b_{i}x_i x_i\Rightarrow -b_{i}(1-x_i) + b_{i}&\;\;\;\;\;\;\;\;\; (b_{i}\le 0)\\
b_{i}x_i x_i \Rightarrow b_{i}x_i &\;\;\;\;\;\;\;\;\;(b_{i}> 0)
\end{array}
$$
最後に変数の無い項同士(e.g., $${b_{i}}$$,$${c}$$)を足せば終わりです。
この式変形の妥当性について少し触れます。式変更前と後で関数は等しくなります。いずれの式変形も、矢印の左側と右側は等しいからです。そしてこれら式変形で関数$${f}$$内の「変数がある項の係数」はすべて正となります。1つ目の式変形で異なる変数の積でできた項の係数は正となりますし、2つ目3つ目の式変形で同じ変数の積でできた項の係数も正となります。
ⓑノードを置く
次にフローネットワークに現れるノードを置きます。まず関数$${f}$$に現れる変数と同じ数のノードを置きます。それぞれは関数$${f}$$に現れる変数を表します。次にノードSとノードTを置きます。(詳細は次回の記事で説明しますが、ノードSは数字の1を表し、ノードTは数字の0を表します。)
例として、$${(1-x_1)+(1-x_2)+2x_3+2x_1(1-x_2)+x_2(1-x_3)}$$のフローネットワークを作りましょう。関数は既にⓐの式変形済みです。因みに変形前は$${x_1 x_1+2x_3 x_3 - 2x_1 x_2 - x_2 x_3 +2 }$$です。
ⓑのステップを実行しますと以下ようにノードが置かれます。(ノードの場所は適当にしています。)
ⓒエッジを追加
最後に式変形後の関数$${f}$$に合わせ、先程置いたノードにエッジを足し、フローネットワークを完成させます。以下ルールでエッジを足していきます。
式変形後の関数$${f}$$に$${b_{i} x_i}$$の項があるとき、$${x_i}$$を表すノードからノードTへ、キャパシティ$${b_{i}}$$のエッジを足す。
式変形後の関数$${f}$$に$${-b_{j} (1-x_j)}$$の項があるとき、ノードSから$${x_j}$$を表すノードへ、キャパシティ$${-b_{j}}$$のエッジを足す。
式変形後の関数$${f}$$に$${-(a_{i j}+a_{j i})x_i (1-x_j)}$$の項があるとき、$${x_i}$$を表すノードから$${x_j}$$を表すノードへ、キャパシティ$${-(a_{i j}+a_{j i})}$$のエッジを足す。
関数内の定数項に対しては、グラフに何もしません。先程の例$${(1-x_1)+(1-x_2)+2x_3+2x_1(1-x_2)+x_2(1-x_3)}$$にステップ③の処理をしてみますと、以下のようにエッジが足されます。
変数がある項の数だけ正のキャパシティがついたエッジが足されているのがわかります。このように、関数の項と正のキャパシティを持つエッジをうまく対応させるために、項の係数を正にする式変形を行いました。
次回の記事で説明しますが、このフローネットワークの最大流が、関数$${f}$$の最小値となっています。この例ですと、1が最小値となります。
まとめ
この記事では、フローネットワークを紹介し、劣モジュラな2次疑似ブール関数を表すフローネットワークの構成方法を紹介しました。
次回は、この劣モジュラな2次疑似ブール関数から構成されたフローネットワークと元の関数の最小値が対応することを紹介します。
次の記事
この記事が気に入ったらサポートをしてみませんか？