基于Scipy的Python配对家庭算法优化：最优家庭组合求解

问题分析 #

原实现中同一连通分量内不同节点对应的家庭范围不一致，核心需求是：给每个连通分量分配唯一的最优家庭，优先级规则为：

• 优先选择成员数量最多的家庭
• 若多个家庭规模相同，选取包含最小节点编号的那个家庭

改进后代码实现 #

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

def assign_optimal_families(node_coords, maxdist):
    # 计算节点间欧氏距离矩阵
    dist_matrix = np.sqrt(((node_coords[:, np.newaxis] - node_coords)**2).sum(axis=2))
    n_nodes = len(node_coords)
    
    # 1. 构建连通分量：所有距离≤maxdist的节点对构成连通关系
    adjacency = (dist_matrix <= maxdist).astype(int)
    np.fill_diagonal(adjacency, 1)  # 节点自身属于同一连通分量
    n_components, labels = connected_components(csgraph=csr_matrix(adjacency), directed=False)
    
    # 2. 为每个连通分量生成候选家庭，并选出最优家庭
    family_assignments = [[] for _ in range(n_nodes)]
    for comp_id in range(n_components):
        # 获取当前连通分量的所有节点
        comp_nodes = np.where(labels == comp_id)[0]
        
        # 生成每个节点对应的家庭（所有距离≤maxdist的节点）
        candidate_families = []
        for node in comp_nodes:
            family = np.where(dist_matrix[node] <= maxdist)[0].tolist()
            family.sort()  # 统一排序方便后续比较
            # 用负规模实现降序排序，再绑定最小节点编号
            candidate_families.append((-len(family), min(family), family))
        
        # 按规则排序：先按家庭规模降序，再按最小节点编号升序
        candidate_families.sort()
        optimal_family = candidate_families[0][2]
        
        # 给当前连通分量内所有节点分配最优家庭
        for node in comp_nodes:
            family_assignments[node] = optimal_family
    
    return family_assignments

# 测试示例：5个一维分布的节点
node_coords = np.array([
    [0, 0],    # 节点0
    [1, 0],    # 节点1
    [3, 0],    # 节点2
    [4, 0],    # 节点3
    [6, 0]     # 节点4
])

# 测试maxdist=2的情况
print("maxdist=2时的家庭分配：")
families_2 = assign_optimal_families(node_coords, maxdist=2)
for idx, fam in enumerate(families_2):
    print(f"节点{idx}: {fam}")

# 测试maxdist=3的情况
print("\nmaxdist=3时的家庭分配：")
families_3 = assign_optimal_families(node_coords, maxdist=3)
for idx, fam in enumerate(families_3):
    print(f"节点{idx}: {fam}")

预期输出 #

maxdist=2时

maxdist=2时的家庭分配：
节点0: [0, 1]
节点1: [0, 1]
节点2: [2, 3]
节点3: [2, 3]
节点4: [4]

maxdist=3时

maxdist=3时的家庭分配：
节点0: [0, 1, 2]
节点1: [0, 1, 2]
节点2: [0, 1, 2]
节点3: [2, 3, 4]
节点4: [2, 3, 4]

关键逻辑说明 #

1. 连通分量识别：通过距离矩阵构建邻接矩阵，用connected_components找出所有连通的节点组，确保同一组内的节点属于同一个“可连通范围”。
2. 候选家庭生成：对每个连通分量内的节点，生成其对应的家庭集合（所有距离≤maxdist的节点）。
3. 最优家庭筛选：将候选家庭用(-家庭规模, 家庭最小节点, 家庭集合)的元组存储，排序时会先按家庭规模降序（负号实现），再按最小节点编号升序，取第一个即为最优家庭。
4. 统一分配：给当前连通分量内的所有节点统一赋值最优家庭，确保同一连通分量内家庭完全一致。

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