解题思路
本题要求实现二分 K-means (Bi-Kmeans) 算法来解决网络子网分割问题。该算法是对传统 K-means 算法的优化，能够有效避免陷入局部最优解。
算法的核心思想是采用自顶向下的分裂策略，每次选择一个簇进行二分，直到达到目标簇数量。具体流程如下：
首先，将所有网络站点作为一个整体，使用标准 K-means 算法（K=2）将其分割成两个子网。在进行 K-means 聚类时，选取子网中 x 坐标最小和最大的两个站点作为初始簇心，然后迭代更新簇心（使用簇内所有站点的平均坐标），直到簇心变化小于阈值或达到最大迭代次数。
接下来，算法进入主循环，每次迭代都需要从现有的所有簇中选择一个进行进一步划分。选择的标准是基于 SSE（误差平方和）最小化原则：计算每个簇被划分前后的 SSE 差值，选择能够最大程度降低全局 SSE 的簇进行划分。SSE 的计算方式是以簇的平均坐标为簇心，计算簇内所有站点到簇心的欧氏距离平方和。
P4228.第3题-基于二分Kmeans算法的子网分割问题
题目内容
背景：在网络规划中，经常涉及子网分割问题，子网分割的目的是将距离相近的网络站点划分为一个子网，从而便于管理。
问题：聚类算法可以很好的解决子网分割问题，但是，聚类问题容易陷入局部最优。因此，本题期望采用优化版的聚类算法二分 Kmeans 算法（Bi−Kmeans）进行子网分割。
方案概述：Bi−Kmeans 算法首先将全网按照常规的 Kmeans 算法聚类成两个子网（也就是 K=2，两簇），然后，Bi−Kmeans 算法会基于 SSE（Sum of Squared Error）最小化原理，每次迭代只选择一个子网进一步划分，选择子网的原则是对该子网的进一步划分能够最大程度的降低全局 SSE，划分方法依旧是常规的 Kmeans 算法（K=2），直到子网个数达到预期数量时，停止 Bi−Kmeans 算法的迭代（算法实现细节参见下述备注 1/2/3）。
备注 1-初始值选取：在进行常规 Kmeans 聚类（K=2）二分子网时，选取子网中 x 坐标最小和最大的两个站点作为初始簇心进行划分（网络站点拥有不同的 x 坐标，本题中 x 坐标的最小值和最大值唯一）。
备注 2-算法迭代：在进行常规 Kmeans 聚类（K=2）二分子网时，以簇中全部站点的平均坐标作为更新簇心；如果相邻的两次迭代聚类结果相同（各簇心迭代前后之间的距离小于 1e−6 则视为结果相同），则停止迭代，或者当迭代次数达到 1000 次时停止迭代。
备注 3−SSE 计算：以子网中全部站点的平均坐标为簇心，SSE 的计算方式是簇内所有站点到簇心距离的平方之和。
输入描述
输入包括三部分信息：
1）第一行数据表示期望分割的子网数量，用 N 表示，也就是聚类结果中簇的数量；N 是整数，范围 1<=N<=100 。
2）第二行数据表示全网站点总数，用 M 表示；M 是整数，范围 1<=M<=1000 。
3）从第三行开始的数据表示网络站点坐标，每一行代表一个站点的二维坐标，用空格分隔 x 轴坐标和 y 轴坐标； x 轴坐标和 y 轴坐标均为整数，0<=x 轴坐标 <=1000，0<=y 轴坐标 <=1000 。
输出描述
输出用二维数组记录划分的最终结果和划分过程，其中，第 k 行记录第 k 次划分后的结果，结果包含第 k 次划分后每个子网的站点数量，用空格分隔，并按照降序排列。
样例1
输入
3
3
0 0
2 2
5 5
输出
2 1
1 1 1
说明
输入表示我们期望将坐标分别为 (0,0)、(2,2)、(5,5) 的 3 个网络站点划分为 3 个子网。
按照题目要求，需要经过两次划分，第一次划分的结果为：
簇 1 1=[(0,0),(2,2)]
簇 1 2=[(5,5)]
因此，期望输出的第一行是 2 1，其中，2 表示划分结果簇 1 1 有 2 个站点，1 表示划分结果簇 1 2 有 1 个站点，降序排列。
第二次划分的结果为：
簇 2 1=[(0,0)]
簇 2 2=[(2,2)]
簇 2 3=[(5,5)]
因此，期望输出的第二行是 1 1 1，其中，第一个 1 表示划分结果簇 2 1 有 1 个站点，第二个 1 表示划分结果簇 2 2 有 1 个站点，第三个 1 表示划分结果簇 2 3 有 1 个站点，降序排列。
样例2
输入
2
3
0 0
2 2
5 5
输出
2 1
说明
输入表示我们期望将坐标分别为 (0,0)、(2,2)、(5,5) 的 3 个网络站点划分为 2 个子网。
按照题目要求，需要经过一次划分，划分的结果为：
簇 1=[(0,0),(2,2)]
簇 2=[(5,5)]
因此，期望输出是 2 1，其中，2 表示划分结果簇 1 有 2 个站点，1 表示划分结果簇 2 有 1 个站点，降序排列。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
