小红的 AI 配送聚类优化_

小红正在为自研的无人驾驶配送机器人开发一套路径规划系统。为了提高效率，配送系统需要先将分散的包裹坐标通过无监督学习算法进行聚类，确定 $K$ 个核心服务点，然后再由机器人按顺序前往这些点。小红选用了经典的 K-Means 算法。具体聚类与路径规划逻辑如下： 1. 初始化： - 如果服务中心数量 $K$ 大于或等于包裹总数 $N$ ，则每个包裹坐标直接作为最终的服务点坐标。 - 否则，先计算所有包裹到坐标原点 (0,0) 的欧几里得距离，并按距离从小到大排序。若距离相同，保持原始输入顺序。选取排序后的前 $K$ 个包裹坐标作为初始聚类中心，并赋予编号 0 到 $K-1$ 。 2. 聚类迭代（最多迭代 50 次）： - 分配阶段：将每个包裹分配给距离其最近的聚类中心。若某包裹到多个中心的距离相等，则分配给编号最小的中心。 - 更新阶段：将每个中心的位置更新为其所分配的所有包裹坐标的平均值。如果某个中心没有分配到任何包裹，则其坐标保持不变。 - 终止条件：计算所有中心在本次更新中移动的欧几里得距离之和。若该距离之和小于 $10^{-4}$ ，或者已完成 50 次迭代，则停止。 3. 路径规划与耗时计算： - 聚类完成后，将最终得到的 $K$ 个服务点坐标按其到原点 (0,0) 的欧几里得距离进行升序排列。 - 机器人从原点 (0,0) 出发，依次访问这 $K$ 个点，最后返回原点 (0,0)。 - 计算机器人走完这段闭环路径的总长度，并根据平均时速计算总耗时。请帮小红计算完成配送任务所需的总秒数。

第一行包含三个空格分隔的整数，分别是服务中心数量 $K$ 、包裹总数 $N$ （ $1 \leq K \leq 10, 1 \leq N \leq 100$ ），以及配送机器人的平均速度 speed（ $1 \leq speed \leq 100$ ，单位 km/h）。接下来的 $N$ 行，每行包含两个实数 $x_i$ 和 $y_i$ （ $-100.0 \leq x_i, y_i \leq 100.0$ ），表示每个包裹在地图上的公里坐标。

说明

在本样例中，，机器速速度为 36 km/h。
1. 包裹到原点的距离分别为 5.0, 10.0, 5.0。排序后选择坐标 (3,4) 为中心 0，(0,5) 为中心 1。
2. 经过聚类迭代，中心 0 最终更新为 (4.5, 6.0)，中心 1 为 (0.0, 5.0)。
3. 两个服务点到原点距离分别为 7.5 和 5.0。访问顺序为 (0,0) -> (0,5) -> (4.5, 6) -> (0,0)。
4. 总路径长度约为 5 + 4.6098 + 7.5 = 17.1098 km。
5. 总耗时约为  秒，向下取整得 1710。

说明


	For 3 communities, 10 packages, and speed 30 km/h, the 10 packages are clustered into 3 centers. Sorted by distance to the origin, the centers are approximately (1.5, 1.5), (-2.1, 3.1), and (5.15, 5.125). The total distance traversed visiting them in order and returning to the origin takes approximately 2502 seconds (floor applied). Note: if K >= N, all N points become their own cluster centers.

小红的 AI 配送聚类优化

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题