ネットワーク内の多数のマシンに負荷を分散するという次の問題に遭遇しました。問題は面接の質問です。受験者は、この問題に最適なアルゴリズムとデータ構造を指定する必要があります。
ネットワーク内に N 台のマシンがあります。各マシンは、最大 5 単位の負荷を受け入れることができます。要求されたアルゴリズムは、現在の負荷 (0 ～ 5 の範囲)、マシン間の距離行列、およびネットワーク上で分散させたい新しい負荷 M を含むマシンのリストを入力として受け取ります。
このアルゴリズムは、M 単位の負荷を処理でき、集合距離が最小のマシンのリストを返します。集合距離は、結果リスト内のマシン間の距離の合計です。
たとえば、結果のリストに 3 台のマシン A、B、および C が含まれている場合、これらのマシンは M 単位の負荷 (M=5 の場合、A は 3、B は 1、C は 1) と距離の合計をまとめて処理できます。 SUM = AB + BC は、M 単位の負荷をまとめて処理できる最小のパスです。
それにアプローチする方法について何か提案はありますか？
すべてのマシンが同じ量の負荷、つまり 5 ユニットを処理できるようです。そして、あなたが述べたコスト測定は、ゼロ以外の負荷を持つマシンのセットにのみ依存します(つまり、すでにゼロ以外の負荷を持つマシンにさらに負荷を追加しても、コストは増加しません)。したがって、問題は次のように分解できます。
(1) は単純なビン パッキング問題です。この問題は NP 困難ですが、優れたヒューリスティックが存在し、実際にはほぼすべてのインスタンスを最適化するためにすばやく解決できます。
（2）をより迅速に解決するための線形代数法があるかもしれません（誰かがそれを知っている場合は、自由に編集またはコメントで提案してください）が、あまり考えなくても、いつでもbranch and boundを使用できます。これには n の指数関数的な時間がかかる可能性がありますが、n が十分に小さい場合、または探索空間の大部分を制限するまともなヒューリスティック ソリューションを取得できる場合は問題ありません。
(マシン 1、...、j の中から i 台のマシンを選択する最小コストの方法である f(i, j) を計算する DP を考えてみましたが、これは、 j 番目のマシンから f(i - 1, j - 1) まで、新しいマシンから既存のすべてのマシンまでのエッジの総コストは、f(i - 1, j - 1) の解に含まれるマシンによって異なります。このソリューションのコストだけでなく、最適な下部構造に違反しています。)