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;
		}
	}
}