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