algorithm - 最短距離

Question

9 人の生徒と 3 つの学校のセットがあります。各学校には最大 3 人の生徒を割り当てることができます。すべての学校と生徒には座標があります。すべての生徒から学校までの距離の合計が最小限にする必要があります。

私はインタビューでこの質問をされました.誰かがこれのためのアルゴリズムを提案できますか?

最初は貪欲なアプローチを試みましたが、うまくいきませんでした。その後、動的計画法のアプローチを適用しようとしましたが、最適なサブ構造を思い付くことができませんでした。

Answer 1

どの学校にも 3 か所あり、3 校すべてに 9 か所あります。そして、9 つの場所と 9 人の学生の間でベスト マッチを見つける必要があります。

この割り当ての問題は、ハンガリーのアルゴリズムで解決できる可能性があります。

Answer 2

問題のサイズが十分に小さいので、網羅的な検索はどうでしょうか。

• 最初の学校は、9 人から 3 人の生徒を選んで開始します。
• 2 番目の学校は、残りの 6 人から 3 人の生徒を選びます。
• 最後の学校は生徒が 3 人残っている状態で行き詰まります。

そう(9 choose 3) * (6 choose 3) = 1680