东莞网站建设网页推广,怎么弄一个自己的链接,手机ui设计网站,个人网站可以备案了吗1 K中心问题#xff08;K-centers Problem#xff09;
k-centers problem: 寻找k个半径越小越好的center以覆盖所有的点。
比如#xff1a;给定n个城市和每对城市之间的距离#xff0c;选择k个城市放置仓库#xff08;或ATM或云服务器#xff09;#xff0c;以使城市…
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 Listint Select_K_Cities(int[,] weights, int k) { int n weights.GetLength(0); int[] dist new int[n]; Listint centers new Listint(); 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); } Listint list new Listint(); 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 Listint Select_K_Cities(int[,] weights, int k){int n weights.GetLength(0);int[] dist new int[n];Listint centers new Listint();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);}Listint list new Listint();list.Add(dist[max]);for (int i 0; i centers.Count; i){list.Add(centers[i]);}return list;}}
}
