C#,K中心问题(K-centers Problem)的算法与源代码

2024-03-02 07:20

本文主要是介绍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)的算法与源代码的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

C#解析JSON数据全攻略指南

《C#解析JSON数据全攻略指南》这篇文章主要为大家详细介绍了使用C#解析JSON数据全攻略指南,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、为什么jsON是C#开发必修课?二、四步搞定网络JSON数据1. 获取数据 - HttpClient最佳实践2. 动态解析 - 快速

Python错误AttributeError: 'NoneType' object has no attribute问题的彻底解决方法

《Python错误AttributeError:NoneTypeobjecthasnoattribute问题的彻底解决方法》在Python项目开发和调试过程中,经常会碰到这样一个异常信息... 目录问题背景与概述错误解读:AttributeError: 'NoneType' object has no at

Spring的RedisTemplate的json反序列泛型丢失问题解决

《Spring的RedisTemplate的json反序列泛型丢失问题解决》本文主要介绍了SpringRedisTemplate中使用JSON序列化时泛型信息丢失的问题及其提出三种解决方案,可以根据性... 目录背景解决方案方案一方案二方案三总结背景在使用RedisTemplate操作redis时我们针对

Kotlin Map映射转换问题小结

《KotlinMap映射转换问题小结》文章介绍了Kotlin集合转换的多种方法,包括map(一对一转换)、mapIndexed(带索引)、mapNotNull(过滤null)、mapKeys/map... 目录Kotlin 集合转换:map、mapIndexed、mapNotNull、mapKeys、map

nginx中端口无权限的问题解决

《nginx中端口无权限的问题解决》当Nginx日志报错bind()to80failed(13:Permissiondenied)时,这通常是由于权限不足导致Nginx无法绑定到80端口,下面就来... 目录一、问题原因分析二、解决方案1. 以 root 权限运行 Nginx(不推荐)2. 为 Nginx

解决1093 - You can‘t specify target table报错问题及原因分析

《解决1093-Youcan‘tspecifytargettable报错问题及原因分析》MySQL1093错误因UPDATE/DELETE语句的FROM子句直接引用目标表或嵌套子查询导致,... 目录报js错原因分析具体原因解决办法方法一:使用临时表方法二:使用JOIN方法三:使用EXISTS示例总结报错原

Windows环境下解决Matplotlib中文字体显示问题的详细教程

《Windows环境下解决Matplotlib中文字体显示问题的详细教程》本文详细介绍了在Windows下解决Matplotlib中文显示问题的方法,包括安装字体、更新缓存、配置文件设置及编码調整,并... 目录引言问题分析解决方案详解1. 检查系统已安装字体2. 手动添加中文字体(以SimHei为例)步骤

SpringSecurity整合redission序列化问题小结(最新整理)

《SpringSecurity整合redission序列化问题小结(最新整理)》文章详解SpringSecurity整合Redisson时的序列化问题,指出需排除官方Jackson依赖,通过自定义反序... 目录1. 前言2. Redission配置2.1 RedissonProperties2.2 Red

nginx 负载均衡配置及如何解决重复登录问题

《nginx负载均衡配置及如何解决重复登录问题》文章详解Nginx源码安装与Docker部署,介绍四层/七层代理区别及负载均衡策略,通过ip_hash解决重复登录问题,对nginx负载均衡配置及如何... 目录一:源码安装:1.配置编译参数2.编译3.编译安装 二,四层代理和七层代理区别1.二者混合使用举例

C#连接SQL server数据库命令的基本步骤

《C#连接SQLserver数据库命令的基本步骤》文章讲解了连接SQLServer数据库的步骤,包括引入命名空间、构建连接字符串、使用SqlConnection和SqlCommand执行SQL操作,... 目录建议配合使用:如何下载和安装SQL server数据库-CSDN博客1. 引入必要的命名空间2.