それぞれn個の要素を持つ3つのセットA、B、Cが与えられます。これらのセットには重複が含まれている可能性があります（セットが正しい用語であるかどうかは不明です）。
今、私はn個の要素（たとえばD1からDn）で集合Dを形成しようとしています。各要素Diには、Aから、Bから、Cからの3つの要素が含まれています。
私の目的は、Diの要素の積の合計を最小化する集合Dを見つけることです。
ここではブルートフォースはかなり悪い考えのようです。n>5の場合でも、アルゴリズムの速度がかなり遅くなるためです。誰かがより良いアプローチを提案できますか？線形計画法はこの問題に適していますか？
したがって、平均積（a_i * b_j * c_k）が最小化されるように、ABとBCの要素の一致を作成する2つの2部グラフを作成する必要があります。
残念ながら、これはNP困難な問題だと思います。（一致する数n = 3を変数として取る場合）
2つのマッチングを別々に行うことはできないと思います。
A = {1、10}、B = {1、10}を考えてみましょう
単独でのA、Bのマッチングは、1 x 10=10および1x10 = 10（合計20）です。
ただし、C = {1、10000}を考慮してください
A、BとCの貪欲な一致をとると、10 x 1=10および10x10000 = 100000（合計100010）になります。
ただし、最適ではないマッチングA、Bを1 x 1=1および10x10 = 100（合計101）と見なした場合
次に、1 x 10000=10000および100x10 = 1000（合計11000）としてCと一致させることができます。
したがって、考えられるすべての組み合わせを検討する必要があることがわかります。
これは、それがNP困難であることを証明するものではありませんが、直感を伝えることを願っています。