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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/267259.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

c语言经典测试题8

在c语言经典测试题6的第一题&#xff0c;大家是否想过可不可以将递归参数改为s呢&#xff1f;或许有的人已经试过了&#xff0c;但是发现好像不会有结果&#xff0c;其实是因为s为后置&#xff0c;先试用后加1&#xff0c;然而我们这个是在s出了函数之后才会运行加1操作&#x…

sqllabs第五关floor报错注入

实验环境sqllabs第五关 floor()报错注入的原因是group by在向临时表插入数据时&#xff0c;由于rand()多次计算导致插入临时表时主键重复&#xff0c;从而报错&#xff0c;又因为报错前concat()中的SQL语句或函数被执行&#xff0c;所以该语句报错且被抛出的主键是SQL语句或函…

《求生之路2》服务器如何选择合适的内存和CPU核心数,以避免丢包和延迟高?

根据求生之路2服务器的实际案例分析选择合适的内存和CPU核心数以避免丢包和延迟高的问题&#xff0c;首先需要考虑游戏的类型和对服务器配置的具体要求。《求生之路2》作为一款多人在线射击游戏&#xff0c;其服务器和网络优化对于玩家体验至关重要。 首先&#xff0c;考虑到游…

AI时代,我们需要什么能力?

AI 时代&#xff0c;一定会重构很多行业&#xff0c;也会重构人民的生活工作方式&#xff0c;那么 AI 时代&#xff0c;我们需要培养什么能力呢&#xff1f; 我们应该去做那些 AI 做不了的事情&#xff01;让 AI 成为我们的工具&#xff0c;助力我们更高效的解决问题&#xff…

JS利用Worker多线程大文件切片上传

在做前端上传时&#xff0c;会遇到上传大文件&#xff0c;大文件就要进行分片上传&#xff0c;我们整理下思路&#xff0c;实现一个分片上传&#xff0c;最终我们要拿到每一个分片的hash值&#xff0c;index 分片索引&#xff0c;以及分片blob&#xff0c;如下&#xff1a; 一…

曾桂华:车载座舱音频体验探究与思考| 演讲嘉宾公布

智能车载音频 I 分论坛将于3月27日同期举办&#xff01; 我们正站在一个前所未有的科技革新的交汇点上&#xff0c;重塑我们出行体验的变革正在悄然发生。当人工智能的磅礴力量与车载音频相交融&#xff0c;智慧、便捷与未来的探索之旅正式扬帆起航。 在驾驶的旅途中&#xff0…

智慧治水丨计讯物联水利RTU助推小型水库出险加固工程建设与管理

日前&#xff0c;水利部印发《关于健全小型水库除险加固和运行管护机制的意见》&#xff08;以下简称《意见》&#xff09;&#xff0c;健全小型水库除险加固和运行管护常态化机制&#xff0c;提高小型水库安全管理水平。《意见》提出了“十四五”的两大管理机制&#xff0c;通…

基础小白快速入门c语言--

变量&#xff1a; 表面理解&#xff1a;在程序运行期间&#xff0c;可以改变数值的数据&#xff0c; 深层次含义&#xff1a;变量实质上代表了一块儿内存区域&#xff0c;我们可以将变量理解为一块儿内存区域的标识&#xff0c;当我们操作变量时&#xff0c;相当于操作了变量…

ad18学习笔记十六:如何放置精准焊盘到特定位置,捕抓功能的讲解

网上倒是一堆相关的指导 AD软件熟练度提升&#xff0c;如何设置板框捕捉&#xff1f;_哔哩哔哩_bilibili 关于Altium Designer 20 的捕抓功能的讲解_ad捕捉设置-CSDN博客 AD软件捕捉进阶实例&#xff0c;如何精确的放置布局元器件&#xff1f;_哔哩哔哩_bilibili AD绘制PCB…

Redis--持久化机制详解

什么是redis持久化&#xff1f; Redis持久化是将内存的数据持久化到磁盘上&#xff0c;防止Redis宕机或者断点的时候内存中的数据丢失&#xff0c;把内存中的数据写入到磁盘的过程叫持久化。 Redis持久化的方式&#xff1f; RDB&#xff08;Redis DataBase&#xff09;&…

MySQL 用了哪种默认隔离级别,实现原理是什么?

MySQL 的默认隔离级别是 RR - 可重复读&#xff0c;可以通过命令来查看 MySQL 中的默认隔离级别。 RR - 可重复读是基于多版本并发控制&#xff08;Multi-Version Concurrency Control&#xff0c;MVCC &#xff09;实现的。MVCC&#xff0c;在读取数据时通过一种类似快照的方…

特斯拉一面算法原题

来自太空的 X 帖子 埃隆马斯克&#xff08;Elon Musk&#xff09;旗下太空探索技术公司 SpaceX 于 2 月 26 号&#xff0c;从太空往社交平台 X&#xff08;前身为推特&#xff0c;已被马斯克全资收购并改名&#xff09;发布帖子。 这是 SpaceX 官号首次通过星链来发送 X 帖子&a…

在线上传解压PHP文件代码,压缩/压缩(网站一键打包)支持密码登录

在线上传解压PHP文件代码&#xff0c;压缩/压缩(网站一键打包)支持密码登录 资源宝分享&#xff1a;www.httple.net 如果你没有主机控制面板这个是最好选择&#xff0c;不需要数据库&#xff0c;上传当控制面板使用&#xff0c;无需安装任何扩展&#xff0c;安全高&#xff0c;…

在 Rust 中实现 TCP : 1. 联通内核与用户空间的桥梁

内核-用户空间鸿沟 构建自己的 TCP栈是一项极具挑战的任务。通常&#xff0c;当用户空间应用程序需要互联网连接时&#xff0c;它们会调用操作系统内核提供的高级 API。这些 API 帮助应用程序 连接网络创建、发送和接收数据&#xff0c;从而消除了直接处理原始数据包的复杂性。…

pyspark分布式部署随机森林算法

前言 分布式算法的文章我早就想写了&#xff0c;但是一直比较忙&#xff0c;没有写&#xff0c;最近一个项目又用到了&#xff0c;就记录一下运用Spark部署机器学习分类算法-随机森林的记录过程&#xff0c;写了一个demo。 基于pyspark的随机森林算法预测客户 本次实验采用的…

前端sql条件拼接js工具

因为项目原因&#xff0c;需要前端写sql&#xff0c;所以弄了一套sql条件拼接的js工具 ​ /*常量 LT : " < ", LE : " < ", GT : " > ", GE : " > ", NE : " ! ", EQ : " ", LIKE : " like &qu…

2024有哪些免费的mac苹果电脑深度清理工具?CleanMyMac X

苹果电脑用户们&#xff0c;你们是否经常感到你们的Mac变得不再像刚拆封时那样迅速、流畅&#xff1f;可能是时候对你的苹果电脑进行一次深度清理了。在这个时刻&#xff0c;拥有一些高效的深度清理工具就显得尤为重要。今天&#xff0c;我将介绍几款优秀的苹果电脑深度清理工具…

浅谈 Linux 孤儿进程和僵尸进程

文章目录 前言孤儿进程僵尸进程 前言 本文介绍 Linux 中的 孤儿进程 和 僵尸进程。 孤儿进程 在 Linux 中&#xff0c;就是父进程已经结束了&#xff0c;但是子进程还在运行&#xff0c;这个子进程就被称作 孤儿进程。 需要注意两点&#xff1a; 孤儿进程最终会进入孤儿院…

数据结构-带头双向循环链表

文章目录 一.头结点二.双链表1双链表的概念与结构2.与单链表相比 三.循环链表1.关于循环链表2.循环链表的优点 四.带头双向循环链表1.带头双向循环链表2.结构图3.实现 五.代码一览 一.头结点 在链表中设置头结点的作用是什么 标识链表:头结点是链表的特殊节点,它的存在能够明确…

springboot基于web的网上摄影工作室的开发与实现论文

网上摄影工作室 摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了网上摄影工作室的开发全过程。通过分析网上摄影工作室管理的不足&#xff0c;创建了一个计算机管理网上摄影工作室的方案。文章介绍了网上摄影工…