笔试时间：2025年9月28日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

【背景信息】YOLO系列算法在目标检测领域采用了基于Anchor的机制。Anchor是预定义在图像上的一组固定尺寸和比例的参考框，在特征图的每个位置上预设多个Anchor框作为物体位置和尺寸预测的基准。通过模型预测Anchor与真实框的偏移量(δx,δy,δw,δh)，而非直接输出坐标，避免了直接回归绝对坐标的困难。

【任务目标】基于K-means聚类算法生成YOLO目标检测中的Anchor框：给定N个检测框的宽和高，聚类得到K个Anchor尺寸，并按照面积从大到小的顺序输出Anchor尺寸。

聚类的流程如下：

• 初始化：为保证聚类结果的稳定性，采用稳定初始化策略，直接取前K个框作为初始中心。
• 分配阶段：计算每个框到所有聚类中心的距离，分配最近的中心。
• 更新阶段：计算每个簇中所有框的宽高的均值作为新的聚类中心（在每次迭代计算聚类中心时，都进行向下取整）。
• 终止条件：当达到设定迭代次数T或者新旧聚类中心之间的d值之和小于1e-4时停止迭代。

注：聚类使用d=1-IOU作为距离度量，d和IOU的计算均使用浮点数。

其中IOU的核心公式为交并面积比，即IOU=交集面积/并集面积。对于检测框B1(w1,h1)和B2(w2,h2)，交集面积计算为：intersection=min(w1,w2)min(h1,h2) 并集面积则为两框总面积减去交集：union=w1h1+w2*h2-intersection最终IOU=intersection/(union+1e-16)（加极小值避免除以0）

输入描述

第一行为N、K、T，以空格分开。其中N为训练集中检测框的个数，10<=N<=80。 K为聚类中心个数，3<=K<=9。 T为迭代次数，2<=T<=30 接下来N行为检测框的宽和高，用空格分开。

输出描述

按照聚类中心的面积从大到小的顺序，输出聚类后的中心。（聚类中心的面积=聚类中心的宽*聚类中心的高）

样例输入

12 4 20

12 23

34 21

43 23

199 23

34 23

108 12

200 107

12 78

123 110

34 23

56 48

78 66

样例输出

133 94

121 27

36 22

12 50

样例说明

注：每次迭代的距离度量d和交并比IOU都是用浮点数计算，但每次迭代和最终输出的聚类中心都要做向下取整。

参考题解

解题思路：

1. 初始化：取前K个检测框作为初始聚类中心
2. 距离度量：使用d = 1 - IOU作为距离，IOU越大距离越小
3. K-means迭代： 分配阶段：将每个框分配到距离最近的聚类中心更新阶段：计算每个簇的均值作为新的聚类中心（向下取整）终止判断：达到最大迭代次数或中心变化小于1e-4
4. 输出处理：按面积从大到小排序输出

Python：

import sys
import math

def calculate_iou(box1, box2):
    w1, h1 = box1
    w2, h2 = box2
    
    intersection_w = min(w1, w2)
    intersection_h = min(h1, h2)
    intersection_area = intersection_w * intersection_h
    
    union_area = w1 * h1 + w2 * h2 - intersection_area
    iou = intersection_area / (union_area + 1e-16)
    return iou

def kmeans_distance(box, centroid):
    return 1 - calculate_iou(box, centroid)

def generate_anchors(boxes, k, max_iterations):
    centroids = boxes[:k]
    
    for iteration in range(max_iterations):
        clusters = [[] for _ in range(k)]
        
        for box in boxes:
            distances = [kmeans_distance(box, centroid) for centroid in centroids]
            closest_centroid_index = distances.index(min(distances))
            clusters[closest_centroid_index].append(box)
        
        old_centroids = [c[:] for c in centroids]
        new_centroids = []
        
        for i in range(k):
            if clusters[i]:
                sum_w = sum(box[0] for box in clusters[i])
                sum_h = sum(box[1] for box in clusters[i])
                num_boxes_in_cluster = len(clusters[i])
                new_w = math.floor(sum_w / num_boxes_in_cluster)
                new_h = math.floor(sum_h / num_boxes_in_cluster)
                new_centroids.append([new_w, new_h])
            else:
                new_centroids.append(old_centroids[i])
        
        centroids = new_centroids
        
        distance_sum = 0
        for i in range(k):
            distance_sum += kmeans_distance(old_centroids[i], centroids[i])
        
        if distance_sum < 1e-4:
            break
    
    return centroids

def main():
    n_str, k_str, t_str = sys.stdin.readline().strip().split()
    n = int(