本题核心分为两部分:K-Means 聚类 + 路径距离计算。
首先使用 K-Means 算法对所有包裹进行聚类:
初始化:
某快递员负责一个片区的快递配送业务。假设他手头有 N 个快递包裹需要派送,每个包裹对应一个具体的收货坐标(xi,yi)(单位:公里)。
为了提高效率,公司要求快递员先利用聚类算法将这 N 个包裹自动划分为 K 个簇(代表 K 个社区),快递员只需要将快递送到社区中心(类的中心点)即可。快递员从起始位置出发,按照每个社区中心与起点之间的距离由近到远排序,依次送完所有社区的快递,最后返回起始位置。已知快递员的平均行驶速度为 speed km/h。
快递员初始坐标为 (0,0)。请编写程序,计算完成所有配送并返回起点所需的总时间(单位:秒,向下取整)。
将所有点按到起点的距离从小到大排序,如果距离相同的点,按照输入坐标点的先后顺 序从小到大排序
选择排序后的前 K个点作为初始聚类中心。
将每个点 pi分配到距离最近的聚类中心 ck
labeli=argminkdist(pi,ck)
重新计算每个聚类的中心点(nk 表示分配到第k 个聚类中心的坐标点个数),移动聚类中心
ck=(nk1∑inkxi, nk1∑inkyi)
如果所有聚类中心的移动距离之和小于 1e-4,则停止迭代 如果达到了预设的最大迭代轮次,也停止迭代 否则返回第二步继续进行迭代优化
第一行输入 3 个由空格分隔的整数,分别为 K(社区个数)、N(快递包裹总数)、speed(快递员平均行驶速度,单位 km/h)。
接下来的 N 行分别表示每个包裹的 x和y 坐标(单位:公里),用空格分割。
输出快递员送完所有快递所需的时间,保留整数,向下取整,单位 s。
输入
3 10 30
1.2 1.5
1.8 1.2
5.0 5.2
5.5 4.8
4.9 5.5
-2.0 3.0
-2.5 3.5
-1.8 2.8
1.5 1.8
5.2 5.0
输出
2502
说明
第一行输入,3 个社区,10 个快递包,快递员配送速度 30 km/h 第二行及以后表示,10 个快递包的具体坐标位置,x,y 坐标值,共有 10 行,代表 10 个包裹 聚类后的 3 个聚类中心按照距离起点的位置远近排序分别为:(1.5, 1.5),(-2.1, 3.1),(5.15, 5.125) 可算出快递员配送总时间约为 2502 秒
输入
5 3 10
1.00 1.00
2.00 2.00
3.00 3.00
输出
3054
说明
第一行输入,5 个社区,3 个包裹,快递员配送速度 10 km/h 第二行及以后表示,3 个快递包的具体坐标位置,x,y 坐标值,共有 3 行,代表 3 个包裹
由于 5 > 3,3 个包裹本身分别构成了 3 个聚类中心,按照距离起点位置的排序配送的路径为:
总距离为:62 km,配送速度为 10 km/h,总耗时为
3600×62÷10≈3054.70秒,向下取整后为 3054 秒,故输出 3054。
解题约束及提示
1.1 使用欧式距离:dist=(x1−x2)2+(y1−y2)2
1.2 种子点的选择:对距离信息 dist 进行升序排序,选择前 K 个点进行初始化
1.3 k-Means 终止条件,设定常数
const int max_iters = 50;
const double tol = 1e-4;
1.4 用例数值范围
1<=K<=10
1<=N<=100
1<=speed<=100