1 K中心问题（K-centers Problem）

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

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

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

2 源程序

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

3 源代码

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