如何实现分组内所有点间的最大曼哈顿距离约束？

问题背景 #

现有一个10×10的二维数组，需划分为互不相交的分组，要求每组内所有点两两之间的曼哈顿距离不超过设定的最大值。示例数组如下：

[[ 67  97  72  35  73  77  80  48  21  34]
 [ 11  30  16   1  71  68  72   1  81  23]
 [ 85  31  94  10  50  85  63  11  61  69]
 [ 64  36   8  37  36  72  96  20  91  19]
 [ 99  54  84  56   3  80  41  45   1   8]
 [ 97  88  21   8  54  55  88  45  63  82]
 [ 13  53   1  90  39  28  48  15  86   8]
 [ 26  63  36  36   3  29  33  26  54  58]
 [ 74  40  53  12  21  17   4  87  14  22]
 [ 23  98   3 100  85  12  65  21  83  97]]

现有实现的缺陷 #

当前已实现possible_munips筛选候选点（仅校验点与起始点的曼哈顿距离）、temp_array标记已分组点、munipIsValid校验单点与起始点的距离，再通过贪心策略逐个添加候选点至分组长度k，最后用groupIsValid校验有效性。但这种逻辑存在核心问题：

• possible_munips仅筛选与起始点距离达标的点，这些点之间可能互相超出距离限制，导致后续groupIsValid校验失败
• 贪心取第一个候选点的策略容易陷入"局部可行但全局无效"的死胡同，简单的分组内点交换无法从根本上解决候选池本身不符合两两距离约束的问题

现有核心代码 #

候选点筛选函数

def possible_munips(x, y, munip, dist_manhattan_max, temp_array):
    list = []
    for i in range(y):
        for j in range(x):
            if (j, i) != munip and munipIsValid(j, i, munip, dist_manhattan_max) and temp_array[i][j] != -1:
                list.append((j, i, temp_array[i][j]))

分组构建逻辑

munips = possible_munips(x, y, munip, dist_manhattan_max, temp_array)

while len(new_group) < k:
    point = munips[0]
    new_group.append(point)
    if not groupIsValid(new_group, distManhattanMax, len(new_group)):
        new_group.remove(point)
    munips.remove(point)
    current_sol.append(new_group)

for groups in current_sol:
    for munip in groups:
        temp_array[munip[1], munip[0]] = -1

解决方案 #

1. 重构候选池：确保候选点两两符合距离约束 #

修改候选点筛选逻辑，不仅校验与起始点的距离，还要保证候选池内任意两点的曼哈顿距离都达标，从根源避免无效分组：

def get_valid_candidate_set(start_point, dist_max, temp_array):
    # 先收集所有与起始点距离达标且未分组的点
    candidates = []
    y_len, x_len = len(temp_array), len(temp_array[0])
    start_x, start_y = start_point
    for i in range(y_len):
        for j in range(x_len):
            if temp_array[i][j] == -1:
                continue
            if abs(j - start_x) + abs(i - start_y) <= dist_max:
                candidates.append((j, i, temp_array[i][j]))
    
    # 筛选出两两之间距离都达标的子集
    valid_set = [start_point + (temp_array[start_y][start_x],)]
    for candidate in candidates:
        cand_x, cand_y, _ = candidate
        valid = True
        for point in valid_set:
            p_x, p_y, _ = point
            if abs(cand_x - p_x) + abs(cand_y - p_y) > dist_max:
                valid = False
                break
        if valid:
            valid_set.append(candidate)
    return valid_set

2. 回溯法构建固定长度分组（必须凑齐k个点时） #

如果要求每组恰好包含k个点，贪心策略容易失败，改用回溯法遍历所有可能的有效组合：

def backtrack_group(candidates, k, dist_max, current_group, result):
    if len(current_group) == k:
        result.append(current_group.copy())
        return True
    for i in range(len(candidates)):
        point = candidates[i]
        # 校验当前点与组内所有点的距离
        valid = True
        for p in current_group:
            if abs(point[0] - p[0]) + abs(point[1] - p[1]) > dist_max:
                valid = False
                break
        if valid:
            current_group.append(point)
            # 找到有效分组就提前返回
            if backtrack_group(candidates[i+1:], k, dist_max, current_group, result):
                return True
            current_group.pop()
    return False

# 使用示例
start_point = (0, 0)
candidates = get_valid_candidate_set(start_point, dist_manhattan_max, temp_array)
group_result = []
backtrack_group(candidates, k, dist_manhattan_max, [start_point + (temp_array[0][0],)], group_result)
if group_result:
    # 标记已分组点
    for p in group_result[0]:
        temp_array[p[1]][p[0]] = -1

3. 灵活分组长度（允许分组小于等于k个点） #

如果不需要严格凑齐k个点，直接从有效候选集中取最多k个点即可，高效且不会出现无效分组：

def build_group(start_point, dist_max, temp_array, k):
    valid_set = get_valid_candidate_set(start_point, dist_max, temp_array)
    # 取前k个点（或全部有效点，取数量较少的）
    group = valid_set[:k]
    # 标记已分组
    for p in group:
        temp_array[p[1]][p[0]] = -1
    return group

4. 全局分组规划 #

遍历所有未分组点，逐个构建有效分组，完成整个数组的划分：

def full_array_grouping(arr, dist_max, k):
    temp_array = [row.copy() for row in arr]
    all_groups = []
    y_len, x_len = len(temp_array), len(temp_array[0])
    for i in range(y_len):
        for j in range(x_len):
            if temp_array[i][j] != -1:
                group = build_group((j, i), dist_max, temp_array, k)
                all_groups.append(group)
    return all_groups

关键总结 #

• 核心要求是分组内任意两点的曼哈顿距离都符合约束，而非仅与起始点达标
• 回溯法适合必须凑齐固定长度分组的场景，10×10的数组规模完全适用
• 灵活分组长度的方案效率最高，能快速完成有效分组

内容的提问来源于stack exchange，提问作者Antoine Descombes