C#，K中心问题（K-centers Problem）的算法与源代码

本文主要是介绍C#，K中心问题（K-centers Problem）的算法与源代码，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

k-centers problem: 寻找k个半径越小越好的center以覆盖所有的点。

比如：给定n个城市和每对城市之间的距离，选择k个城市放置仓库（或ATM或云服务器），以使城市到仓库（或ATM或云服务器）的最大距离最小化。

再如：考虑以下四个城市，0、1、2和3，以及它们之间的距离，如何在这四个城市中放置两台ATM，以使城市到ATM的最大距离最小化。

using System;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
   public class K_Centers
   {
       private static int MaxIndex(int[] dist, int n)
       {
           int mi = 0;
           for (int i = 0; i < n; i++)
           {
               if (dist[i] > dist[mi])
               {
                   mi = i;
               }
           }
           return mi;
       }

       public static List<int> Select_K_Cities(int[,] weights, int k)
       {
           int n = weights.GetLength(0);
           int[] dist = new int[n];
           List<int> centers = new List<int>();
           for (int i = 0; i < n; i++)
           {
               dist[i] = Int32.MaxValue;
           }

           int max = 0;
           for (int i = 0; i < k; i++)
           {
               centers.Add(max);
               for (int j = 0; j < n; j++)
               {
                   dist[j] = Math.Min(dist[j], weights[max, j]);
               }
               max = MaxIndex(dist, n);
           }

           List<int> list = new List<int>();
           list.Add(dist[max]);
           for (int i = 0; i < centers.Count; i++)
           {
               list.Add(centers[i]);
           }
           return list;
       }
   }
}