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

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

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

这篇关于C#，K中心问题（K-centers Problem）的算法与源代码的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---