如何实现从集合R中为集合P各子列表查找最近的两个节点？

需求描述 #

需要实现论文中步骤2的要求：从集合R中，找到与集合P中每个车辆对应的节点子列表最接近的两个节点，最近的称为i，次近的称为j。

数据定义 #

• R：图中的有序节点集合，示例：R = [1,5,6,9]（长度可变化）
• P：各车辆对应的节点子列表集合，示例：P = [[4],[7,3,8],[2]]（子列表长度可变化）
• dist：存储节点间距离的字典，键为元组(R节点, P节点)，值为两点间距离，示例如下：

dist = {
    (1,4): 52.35456045083369,
    (5,4): 37.48332962798263,
    (6,4): 52.92447448959697,
    (9,4): 76.83749084919418,
    (1,7): 94.89467845985885,
    (1,3): 58.9406481131655,
    (1,8): 11.180339887498949,
    (5,7): 54.817880294662984,
    (5,3): 51.478150704935004,
    (5,8): 45.044422518220834,
    (6,7): 27.80287754891569,
    (6,3): 60.74537019394976,
    (6,8): 72.3671196055225,
    (9,7): 99.68951800465283,
    (9,3): 44.68780594300866,
    (9,8): 15.811388300841896,
    (1,2): 102.44998779892558,
    (5,2): 65.60487786742691,
    (6,2): 42.37924020083418,
    (9,2): 102.55242561733974
}

问题 #

现有代码仅支持P中子列表长度为1的情况，需要编写通用函数，输入R和P，输出每个子列表对应的i（最近节点）和j（次近节点）。对于子列表长度大于1的情况，采用R节点到子列表中所有节点的平均距离作为衡量接近程度的标准。

现有代码 #

主循环代码 #

for k in range(2):    
    all_nodes_dict = {}
    for i in range(len(R)):
                    all_nodes_dict[(R[i],P[k][0])] = dist[(R[i], P[k][0])]
                    min_list = sorted(list(all_nodes_dict.values()), key = lambda x:float(x))
                    min_vals = min_list[:2]

    two_closest_nodes = []
    for i in range(len(min_vals)):
        two_closest_nodes += [return_key(min_vals[i], all_nodes_dict)[0]]

    i = two_closest_nodes[0]
    j = two_closest_nodes[1]

    # do something with i and j before resetting them for new iteration

辅助函数return_key #

# 根据值返回字典对应的键
def return_key(val, my_dict):
    for key, value in my_dict.items():
        if val == value:
            return key

    return "key doesn't exist"

距离字典生成代码 #

import random
import math

n = 10

random.seed(1)
# 创建n个随机点
points = [(0, 0)]
points += [(random.randint(0, 100), random.randint(0, 100)) for i in range(n - 1)]

# 生成所有点对的距离字典
dist = {
    (i, j): math.sqrt(sum((points[i][p] - points[j][p]) ** 2 for p in range(2)))
    for i in range(n)
    for j in range(n)
    if i != j
}

解决方案 #

实现思路 #

1. 遍历P中的每个子列表，对每个子列表：
   • 计算R中每个节点到该子列表所有节点的平均距离
   • 根据平均距离对R节点排序，取前两个即为最近的i和次近的j
2. 优化浮点数精度判断，避免因精度问题导致的键值匹配错误

完整代码 #

import random
import math

# 根据值返回字典对应的键（优化浮点数精度判断）
def return_key(val, my_dict):
    for key, value in my_dict.items():
        if abs(val - value) < 1e-9:
            return key
    return "key doesn't exist"

# 生成距离字典的函数
def generate_dist(n=10, seed=1):
    random.seed(seed)
    points = [(0, 0)]
    points += [(random.randint(0, 100), random.randint(0, 100)) for _ in range(n - 1)]
    dist = {
        (i, j): math.sqrt(sum((points[i][p] - points[j][p]) ** 2 for p in range(2)))
        for i in range(n)
        for j in range(n)
        if i != j
    }
    return dist

# 核心函数：找到每个P子列表对应的最近和次近R节点
def find_closest_nodes(R, P, dist):
    result = []
    for sublist in P:
        # 计算每个R节点到当前子列表的平均距离
        avg_distances = []
        for r_node in R:
            total_dist = 0.0
            for p_node in sublist:
                total_dist += dist[(r_node, p_node)]
            avg_dist = total_dist / len(sublist)
            avg_distances.append((avg_dist, r_node))
        
        # 按平均距离升序排序，取前两个节点
        avg_distances.sort(key=lambda x: x[0])
        i_node = avg_distances[0][1]
        j_node = avg_distances[1][1]
        result.append((i_node, j_node))
    return result

# 示例测试
if __name__ == "__main__":
    R = [1,5,6,9]
    P = [[4],[7,3,8],[2]]
    dist = generate_dist(n=10, seed=1)
    
    closest_pairs = find_closest_nodes(R, P, dist)
    for idx, (i, j) in enumerate(closest_pairs):
        print(f"车辆{idx}对应的最近节点i={i}，次近节点j={j}")

输出结果 #

车辆0对应的最近节点i=5，次近节点j=1
车辆1对应的最近节点i=5，次近节点j=9
车辆2对应的最近节点i=6，次近节点j=5

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