Google と Stack Overflow の両方で問題の解決策を検索しましたが、見つかりません。
都市の電力ネットワークの最適な分配を見つける必要があります。都市は接続されたグラフで表されます。送電網内のすべてのノードをカバーするために、これらのノードのいくつかに発電所を分散させたいと考えています。問題は、すべての発電所に特定の「範囲」があることです (たとえば、2 つのノードの「半径」でしかカバーできません)。私のプログラムは、都市全体をカバーするために、最小数の発電所とその場所を見つける必要があります。
私の検索から、それは MST (最小スパニング ツリー) に関連しているはずですが、問題は発電所の限られた範囲にあります。
私は、都市のすべてのノードを調べて、そのノードの発電所の範囲内にあるすべてのノードを含むサブグラフを計算し、最もカバーされていないノードをカバーするものを見つけてから、全体になるまでそれを続けることを考えました。市はカバーされていますが（基本的にはブルートフォースで問題を解決しています）、それは非常に非現実的であり、この問題を解決するための他のより効果的な方法があるかどうか疑問に思っていました.
ありがとう。