首页 > 试题广场 >

二分 K-means子网分割

[编程题]二分 K-means子网分割
  • 热度指数：26 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
在网络规划中，希望把若干二维站点拆分为多个子网，便于运维。给定期望子网数 N 和所有站点坐标，采用“二分 K-means”自顶向下的思路：从一个簇开始，每次只把当前 SSE（簇内点到簇心的平方和）最大的簇再二分为两个簇，直到簇数达到 N。二分时使用标准 K=2 的 K-means：初始两个簇心选该簇中 x 坐标最小点与 x 坐标最大点（如有并列，按 y 再按输入次序打破并列），迭代更新“按欧氏距离最近分配 + 以簇内平均坐标为新簇心”，当簇心总移动量均小于 1e-6 或迭代满 1000 次即认为收敛；若出现某一类空簇，则保持该簇心不变继续迭代。每次二分后输出当前所有簇的规模（站点数），按降序排列；共输出 N−1 行。

输入描述:
第一行：N（目标簇数，整数）
第二行：M（站点数，整数）
接下来 M 行：每行两个整数 x y（0≤x,y≤1000）


输出描述:
共输出 N−1 行。第 k 行为完成第 k 次二分后的各簇规模（降序），以空格分隔
示例1

输入

3
5
0 0
1 0
10 0
11 0
12 0

输出

3 2
2 2 1

说明

首次把点大致按中间位置分成 {0,1} 与 {10,11,12}，规模为 2 与 3；第二次优先二分规模更大且 SSE 更大的簇 {10,11,12} 为 {10} 与 {11,12}，此时三个簇规模降序为 2 2 1。
算法知识视频讲解
开通博客
头像 糊氏佳骏
发表于 2025-10-16 15:12:01
import math # If you need to import additional packages&nbs***bsp;classes, please import here. 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Xin001
发表于 2025-10-17 15:57:32
import numpy as np import math def get_initial_centrals(points): centrals = [] new_points = [[points[i][0], points[i][1], i] for i in range(l 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

难度：
2条回答 33浏览

热门推荐

相关试题

二分 K-means子网分割

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号