# 変数の置き換え :::{container} prog-cpp QUBO++ には、**式内の変数の値を固定する**ために使用できる次の `replace` 関数が用意されています。 ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` この関数は、`ml` に指定されたマッピングに従って、式 `f` 内の変数の値を**置き換え（固定）**します。
## replace 関数を用いた変数値の固定 ここでは、**分割問題（partitioning problem）** の QUBO++ プログラムを使って `qbpp::replace()` 関数を説明します。 このプログラムは、次のベクトル `w` に含まれる数値を 2 つの部分集合 $P$ と $Q$（$P \cap Q = \varnothing$）に分割し、それぞれの**合計値の差が最小**になるような分割を求めます: ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` ここでは、この分割問題を次のように**変更**します。 - 64 は必ず $P$ に属する - 27 は必ず $Q$ に属する つまり、この 2 つの値が**異なる部分集合に入ることを保証**します。この制約を実現するために、`qbpp::replace()` 関数を使って `x[0]` と `x[1]` の値をそれぞれ 1 と 0 に固定します。 完全な Hi-QUBO プログラムを以下に示します。 ```{literalinclude} ../../programFiles/cppPrograms/advanced/replace-functions-program1.cpp :language: cpp :caption: replace-functions-program1.cpp ``` まず、変数 `x[0]` と `x[1]` の固定値を指定する `qbpp::MapList` オブジェクト `ml` を定義します。分割問題の元の式 `f` と `qbpp::MapList` オブジェクト `ml` が与えられると、`qbpp::replace()` 関数を使用して、`f` 内の `x[0]` と `x[1]` をそれぞれ定数 1 と 0 に置き換えます。その結果得られる式は `g` に格納されます。 次に、`Exhaustive Solver` を `g` に適用して最適解を求め、その結果を `sol` に格納します。ここで、式 `g` にはもはや `x[0]` と `x[1]` が含まれていないため、`sol` にもこれらの変数に対する割り当ては含まれていない点に注意してください。 すべての変数を含む完全な解を構築するために、まず `f` に対して 0 で初期化された `qbpp::Sol` オブジェクトを作成します。その後、`set()` を使用して `sol` と `ml` を用いて二値の値を設定します。 以下の出力から、64 が $P$ に配置され、27 が $Q$ に配置されていることが、意図どおりであると確認できます。 ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` ## 変数を式で置き換えるための replace 関数の使用 `replace()` 関数は、定数値だけでなく、変数を式で置き換えることもできます。 ここでは、先に紹介した分割問題において、64 と 27 が必ず異なる部分集合に配置されるようにする、より洗練された方法を示します。 重要なアイデアは、式 `f` に含まれる変数 `x[0]` を、式 `~x[1]` に置き換えることです。これにより、`x[0]` と `x[1]` が常に反対の値を取るという制約が課され、対応する要素（64 と 27）が必ず異なる部分集合に属することが保証されます。 次の Hi-QUBO プログラムは、このアイデアを実装したものです: ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` このプログラムでは、変数 `x[0]` を式 `~x[1]` に置き換えるように、`qbpp::MapList` オブジェクト `ml` が定義されています。 `qbpp::replace()` 関数は、この置換を元の式 `f` に適用し、その結果の式は `g` に格納されます。その結果、`g` にはもはや変数 `x[0]` は含まれず、`x[0]` のすべての出現箇所が式 `~x[1]` に置き換えられます。 その後、Exhaustive Solver を使用して `g` の最適解を求め、その結果は `sol` に格納されます。`g` には `x[0]` が現れないため、解 `sol` にも `x[0]` に対する割り当ては含まれません。 元の式 `f` に含まれる変数に対する完全な解を構成するために、まず 0 で初期化された `qbpp::Sol(f)` を作成し、その後 `set(sol, ml)` を呼び出して値を設定します。ここで `set()` には `sol` と `ml` を同時に渡す必要がある点に注意してください。なぜなら、`ml` に含まれるマッピング（例：`x[0] = ~x[1]`）が、`sol` に含まれる変数の値に依存する可能性があるためです。 このプログラムは、次の出力を生成します: ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` 次のことを確認できます： - 解 `sol` には `x[0]` が含まれていないこと - `x[0]` と `x[1]` が反対の値を取っていること - 64 と 27 が意図どおり異なる部分集合に配置されていること ## 整数変数に対する replace 関数 整数変数は、`replace()` 関数を使用して固定の整数値に置き換えることができます。 ここでは、この機能を簡単な**乗算式**を用いて説明します。 $p,q,r$ を整数変数とし、次の制約を考えます： $$ p \times q-r=0 $$ この式は、いくつかの異なる解釈が可能であり、それぞれ異なる種類の問題になります： - **乗算 (Multiplication)**: $p$ と $q$ の値が固定されているとき、この式を満たす $r$ を求める。 - **因数分解 (Factorization)**: $r$ の値が固定されているとき、この式を満たす $p$ と $q$ を求める。 - **除算 (Division)**: $p$ と $r$ の値が固定されているとき、この式を満たす $q$ を求める。 `qbpp::replace()` 関数を使用すると、整数変数を定数値に固定することができます。 ここでは、`qbpp::replace()` を用いてこれらの問題を解く QUBO++ プログラムを示します。 ## 乗算 次のプログラムでは、$p=5$ と $q=7$ を固定し、その積 $r=35$ を求めます： ```{literalinclude} ../../programFiles/cppPrograms/advanced/replace-functions-program2.cpp :language: cpp :caption: replace-functions-program2.cpp ``` このプログラムでは、元の式 `f` に含まれる整数変数 `p` と `q` の値を固定するために、`qbpp::MapList` オブジェクト `ml` が使用されています。`qbpp::replace(f, ml)` を適用することで、`f` に含まれる変数 `p` と `q` は、それぞれ定数 `5` と `7` に置き換えられます。その結果の式は `g` に格納され、この式には変数 `r` のみが含まれるようになります。 その後、Easy Solver が `g` に適用され、その結果の解は `sol` に格納されます。すべての変数を含む完全な解を構築するために、まず `f` に対して 0 で初期化された `qbpp::Sol` オブジェクトを作成し、その後 `sol` と `ml` を用いて `set()` を呼び出し、バイナリ値を設定します。最後に、`p`、`q`、`r` の値が出力されます。 このプログラムは次の出力を生成し、乗算の結果が正しく得られていることを確認できます: ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` ## 因数分解 $r=35$ の因数分解を行うために、QUBO++ プログラム内の `qbpp::MapList` オブジェクト `ml` は次のように変更されます。 ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` $r$ の値を固定することで、ソルバーは次の制約を満たす整数値 $p$ と $q$ を探索します。 $$ p \times q = 35 $$ このプログラムは次の出力を生成します。 ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` ## 除算 $r=35$ と $p=5$ を使った除算 $r/p$ を計算するために、Hi-QUBO プログラム内の `qbpp::MapList` オブジェクト `ml` を次のように変更します。 ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` このプログラムは次の出力を生成します。 ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` これにより、除算の結果 $q=r/p=7$ が正しく得られることが確認できます。 **補足:** Hi-QUBO は、式に対するメンバ関数版の `replace()` も提供しています。つまり: - `f.replace(ml)` は、`ml` に指定された置換を適用して、式 `f` をその場で更新します。 - `qbpp::replace(f, ml)` は、元の式 `f` を変更せずに、置換を適用した新しい式を返します。既存の式を永久的に変更したい場合は `f.replace(ml)` を使用し、元の式を保持したい場合は `qbpp::replace(f, ml)` を使用します。 **注意**: `Term` に対する `replace()` フリー関数 `qbpp::replace()` は `Term` 引数も受け付けます。 `Term` は暗黙的に `Expr` に変換され、置換が適用されます: ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` なお、`Term` にはメンバ関数版の `replace()` はありません（ヘッダ内で `Term` は `Expr` より先に定義されるため）。 注意: 否定リテラルと `replace()` 関数は `x` と `~x` を独立したキーとして扱います。 `MapList` に `{x, 0}` を指定しても、`~x` が自動的に `1` に置換されるわけではありません。 式に `~x` のような否定リテラルが含まれている場合、両方のマッピングを明示的に指定してください: ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` ::: :::{container} prog-python PyQBPP には、**式内の変数の値を固定する**ために使用できる次の `replace` 関数が用意されています。 - `qbpp.replace(f, ml)`: `ml` で指定されたマッピングに従って `f` 中の変数を置換した新しい式を返します。 - `f.replace(ml)`: 式 `f` の変数をその場で置換します（ `f` を変更します）。 ここで `ml` は Python の辞書 `{変数: 値, ...}` もしくは `(変数, 値)` のタプルのリストです。値は整数、`Var`、`Term`、`Expr` のいずれも指定できます（例: `{x: 0, y: ~z}` や `[(x, 0), (y, ~z)]`）。
## replace 関数を用いた変数値の固定 ここでは、**分割問題（partitioning problem）** の PyQBPP プログラムを使って `replace()` 関数を説明します。 このプログラムは、次のベクトル `w` に含まれる数値を 2 つの部分集合 $P$ と $Q$（$P \cap Q = \varnothing$）に分割し、それぞれの**合計値の差が最小**になるような分割を求めます: ここでは、この分割問題を次のように**変更**します。 - 64 は必ず $P$ に属する - 27 は必ず $Q$ に属する つまり、この 2 つの値が**異なる部分集合に入ることを保証**します。 この制約を実現するために、`replace()` 関数を使って `x[0]` と `x[1]` の値をそれぞれ 1 と 0 に固定します。 完全な PyQBPP プログラムを以下に示します。 ```{literalinclude} ../../programFiles/pythonPrograms/advanced/replace-functions-program1.py :language: python :caption: replace-functions-program1.py ``` まず、変数 `x[0]` と `x[1]` の固定値を指定するリスト `ml` を定義します。 `replace()` 関数を使用して、`f` 内の `x[0]` と `x[1]` をそれぞれ定数 1 と 0 に置き換えます。 その結果得られる式は `g` に格納されます。 次に、`Exhaustive Solver` を `g` に適用して最適解を求め、その結果を `sol` に格納します。 ここで、式 `g` にはもはや `x[0]` と `x[1]` が含まれていないため、`sol` にもこれらの変数に対する割り当ては含まれていない点に注意してください。 すべての変数を含む完全な解を構築するために、まず `f` に対して 0 で初期化された `Sol` オブジェクトを作成します。 その後、`set()` を使用して `sol` と `ml` を用いて二値の値を設定します。 以下の出力から、64 が $P$ に配置され、27 が $Q$ に配置されていることが、意図どおりであると確認できます。 ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` ## 変数を式で置き換えるための replace 関数の使用 `replace()` 関数は、定数値だけでなく、変数を式で置き換えることもできます。 ここでは、先に紹介した分割問題において、64 と 27 が必ず異なる部分集合に配置されるようにする、より洗練された方法を示します。 重要なアイデアは、式 `f` に含まれる変数 `x[0]` を、式 `~x[1]` に置き換えることです。これにより、`x[0]` と `x[1]` が常に反対の値を取るという制約が課され、対応する要素（64 と 27）が必ず異なる部分集合に属することが保証されます。 次の pyQBPP プログラムは、このアイデアを実装したものです: ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` このプログラムでは、変数 `x[0]` を式 `~x[1]` に置き換えるように、辞書 `ml` が定義されています。 `qbpp.replace()` 関数は、この置換を元の式 `f` に適用し、その結果の式は `g` に格納されます。その結果、`g` にはもはや変数 `x[0]` は含まれず、`x[0]` のすべての出現箇所が式 `~x[1]` に置き換えられます。 その後、Exhaustive Solver を使用して `g` の最適解を求め、その結果は `sol` に格納されます。`g` には `x[0]` が現れないため、解 `sol` にも `x[0]` に対する割り当ては含まれません。 元の式 `f` に含まれる変数に対する完全な解を構成するために、まず 0 で初期化された `Sol(f)` を作成し、その後 `set([sol, ml])` を呼び出して値を設定します。ここで `set()` には `sol` と `ml` を同時に渡す必要がある点に注意してください。なぜなら、`ml` に含まれるマッピング（例：`x[0] = ~x[1]`）が、`sol` に含まれる変数の値に依存する可能性があるためです。 このプログラムは、次の出力を生成します: ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` 次のことを確認できます： - 解 `sol` には `x[0]` が含まれていないこと - `x[0]` と `x[1]` が反対の値を取っていること - 64 と 27 が意図どおり異なる部分集合に配置されていること ## 整数変数に対する replace 関数 整数変数は、`replace()` 関数を使用して固定の整数値に置き換えることができます。 ここでは、この機能を簡単な**乗算式**を用いて説明します。 $p,q,r$ を整数変数とし、次の制約を考えます： $$ p \times q-r=0 $$ この式は、いくつかの異なる解釈が可能であり、それぞれ異なる種類の問題になります： - **乗算 (Multiplication)**: $p$ と $q$ の値が固定されているとき、この式を満たす $r$ を求める。 - **因数分解 (Factorization)**: $r$ の値が固定されているとき、この式を満たす $p$ と $q$ を求める。 - **除算 (Division)**: $p$ と $r$ の値が固定されているとき、この式を満たす $q$ を求める。 `replace()` 関数を使用すると、整数変数を定数値に固定することができます。 ここでは、`replace()` を用いてこれらの問題を解く QUBO++ プログラムを示します。 ## 乗算 次のプログラムでは、$p=5$ と $q=7$ を固定し、その積 $r=35$ を求めます： ```{literalinclude} ../../programFiles/pythonPrograms/advanced/replace-functions-program2.py :language: python :caption: replace-functions-program2.py ``` このプログラムでは、元の式 `f` に含まれる整数変数 `p` と `q` の値を固定するために、辞書 `ml` が使用されています。`qbpp.replace(f, ml)` を適用することで、`f` に含まれる変数 `p` と `q` は、それぞれ定数 `5` と `7` に置き換えられます。その結果の式は `g` に格納され、この式には変数 `r` のみが含まれるようになります。 その後、Easy Solver が `g` に適用され、その結果の解は `sol` に格納されます。すべての変数を含む完全な解を構築するために、まず `f` に対して 0 で初期化された `Sol` オブジェクトを作成し、その後 `sol` と `ml` を用いて `set()` を呼び出し、バイナリ値を設定します。最後に、`p`、`q`、`r` の値が出力されます。 このプログラムは次の出力を生成し、乗算の結果が正しく得られていることを確認できます: ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` ## 因数分解 $r=35$ の因数分解を行うために、PyQBPP プログラム内の辞書 `ml` は次のように変更されます。 ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` $r$ の値を固定することで、ソルバーは次の制約を満たす整数値 $p$ と $q$ を探索します。 $$ p \times q = 35 $$ このプログラムは次の出力を生成します。 ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` ## 除算 $r=35$ と $p=5$ を使った除算 $r/p$ を計算するために、PyQBPP プログラム内の辞書 `ml` は次のように変更されます。 ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` このプログラムは次の出力を生成します。 ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` これにより、除算の結果 $q=r/p=7$ が正しく得られることが確認できます。 **補足:** PyQBPP は、式に対するメンバ関数版の `replace()` も提供しています。つまり: - `f.replace(ml)` は、`ml` に指定された置換を適用して、式 `f` をその場で更新します。 - `qbpp.replace(f, ml)` は、元の式 `f` を変更せずに、置換を適用した新しい式を返します。 既存の式を変更したい場合は `f.replace(ml)` を、元の式を変更せずに保持したい場合は `qbpp.replace(f, ml)` を使用してください。 > **注意**: `Term` に対する `replace()` > `qbpp.replace(t, ml)` と `t.replace(ml)` の両方が項に対して動作します。 項は式に昇格され、新しい式が返されます： ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` > **注意**: 制約式に対する `replace()` > メンバ関数の replace() は制約式では利用できません。 代わりにフリー関数形式を使用してください： ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` > **注意**: タプルのリストによるマッピング > マッピング `ml` は辞書の代わりに `(変数, 値)` のタプルのリストとして渡すこともできます： ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` > **注意**: 否定リテラルと `replace()` > `replace()` 関数は `x` と `~x` を独立したキーとして扱います。 辞書に `{x: 0}` を指定しても、`~x` が自動的に `1` に置換されるわけではありません。 式に `~x` のような否定リテラルが含まれている場合、両方のマッピングを明示的に指定してください： > ```{include} ../../programFiles/markDown/advanced/replace-functions-program.md :start-after: :end-before: ``` :::