次の問題を解決しようとしています。
連結グラフ G = (V, E) と頂点 t ∈ V が与えられた場合、t ∈ V' である部分グラフ G'= (V', E ') を見つける必要があります。G' は、いくつかの目的関数を最大化し、それに含まれる頂点の数を最小化する必要があります。
Max f(G')
Min |V'|
この多目的最適化問題では、頂点の数を最小化することよりも、f (G') を最大化することが重要です。
同様の問題で実際の状況を確認してみましょう。
クライアント デバイスが固定された場所にあり、有線ネットワークに接続されている AP が 1 つしかない建物内に、アドホック ワイヤレス ネットワークを設計する必要があるとします。最初に、すべての部屋に AP を配置し、伝播モデルを使用して、接続できる AP と、それらがカバレッジを提供するクライアント デバイスを計算します。この最初の配布では、おそらく複数の AP が同じクライアント デバイスにカバレッジを提供するため、最適化する必要があります。
図 1. 赤い点は有線ネットワークに接続された AP を表し、黒い点は残りの AP を表します。AP 間の実線は、それらがどのように接続されているかを示しています。
図 1 の AP の接続を形成するグラフは、問題の接続グラフ G を表し、有線ネットワークに接続されている AP はノード t です。この初期ネットワーク設計を表すグラフを最適化すると、有線ネットワークに接続された AP を含むサブグラフを見つけ、対象となるクライアント デバイスの割合 (最大 f(G') ) を最大化し、AP の数を最小化します (最小 |V'| ）。問題のように、対象となるクライアント デバイスの割合を最大化することが主な目標です。
図 2. 考えられる解決策。
ブルートフォースアルゴリズムを使用すると、NP完全性の問題のように見えます。最適な解を見つけるには、すべての潜在的なサブグラフ (すべてノード t を含む) を調べ、可能な解も証明する必要があります。についてどう思いますか？