Python案例如何用Networkx做匹配问题

本文目录导读：

1. 基本概念
2. 基础案例：二分图最大匹配
3. 带权重的匹配问题
4. 实际应用：课程时间表安排
5. 完整示例：相亲匹配系统
6. 注意事项

我来帮你了解如何使用NetworkX解决匹配问题，我会从基础到进阶,给出几个实用的案例。

基本概念

NetworkX中的匹配主要分为：

• 最大匹配：找到最多数量的匹配边
• 最大权匹配：找到权重和最大的匹配

基础案例：二分图最大匹配

示例：工人-任务分配

import networkx as nx
import matplotlib.pyplot as plt
# 创建二分图
G = nx.Graph()
# 添加工人节点（左侧）
workers = ['W1', 'W2', 'W3', 'W4']
# 添加任务节点（右侧）
tasks = ['T1', 'T2', 'T3']
# 添加所有节点并标记二分属性
G.add_nodes_from(workers, bipartite=0)  # 工人属于左侧
G.add_nodes_from(tasks, bipartite=1)     # 任务属于右侧
# 添加可行的匹配边（工人可以做的任务）
edges = [
    ('W1', 'T1'), ('W1', 'T2'),
    ('W2', 'T1'), ('W2', 'T3'),
    ('W3', 'T2'), ('W3', 'T3'),
    ('W4', 'T1')
]
G.add_edges_from(edges)
# 求最大匹配
matching = nx.maximal_matching(G)
print("最大匹配结果:")
for edge in matching:
    print(f"  {edge[0]} -> {edge[1]}")
# 可视化
pos = nx.bipartite_layout(G, workers)
plt.figure(figsize=(10, 6))
nx.draw(G, pos, with_labels=True, node_color='lightblue', 
        node_size=2000, font_size=12, font_weight='bold')
# 高亮匹配边
nx.draw_networkx_edges(G, pos, edgelist=matching, 
                      edge_color='red', width=3)"工人-任务匹配")
plt.show()

带权重的匹配问题

示例：最优任务分配

import networkx as nx
import numpy as np
# 创建带权重的二分图
G = nx.Graph()
workers = ['张三', '李四', '王五', '赵六']
tasks = ['设计', '开发', '测试']
# 添加节点
G.add_nodes_from(workers, bipartite=0)
G.add_nodes_from(tasks, bipartite=1)
# 添加带权重的边（表示匹配的得分或效率）
weighted_edges = [
    ('张三', '设计', 0.9), ('张三', '开发', 0.3), ('张三', '测试', 0.6),
    ('李四', '设计', 0.4), ('李四', '开发', 0.8), ('李四', '测试', 0.5),
    ('王五', '设计', 0.7), ('王五', '开发', 0.6), ('王五', '测试', 0.8),
    ('赵六', '设计', 0.2), ('赵六', '开发', 0.5), ('赵六', '测试', 0.3),
]
for w, t, score in weighted_edges:
    G.add_edge(w, t, weight=score)
# 计算最大权重匹配
matching = nx.max_weight_matching(G, maxcardinality=True)
print("最优匹配结果:")
total_score = 0
for w, t in matching:
    score = G[w][t]['weight']
    total_score += score
    print(f"  {w} -> {t} (得分: {score})")
print(f"总得分: {total_score:.2f}")

实际应用：课程时间表安排

import networkx as nx
from collections import defaultdict
def schedule_courses(teachers, courses, time_slots):
    """安排课程时间表"""
    G = nx.Graph()
    # 添加节点
    G.add_nodes_from(teachers, bipartite=0)
    G.add_nodes_from(courses, bipartite=1)
    # 构建可行性矩阵
    availability = {
        '张老师': {'数学': [1,2], '物理': [2,3]},
        '李老师': {'数学': [2,3], '化学': [1,3]},
        '王老师': {'物理': [1,2], '化学': [1,2]},
    }
    # 添加可能的匹配
    for teacher, courses_dict in availability.items():
        for course, slots in courses_dict.items():
            # 权重表示可用时间段的优先级
            weight = len(slots) / len(time_slots)
            G.add_edge(teacher, course, weight=weight)
    # 求最大匹配
    matching = nx.max_weight_matching(G)
    # 输出结果
    schedule = defaultdict(list)
    for teacher, course in matching:
        slots = availability[teacher][course]
        schedule[course].append((teacher, slots[0]))
    return schedule
# 使用示例
teachers = ['张老师', '李老师', '王老师']
courses = ['数学', '物理', '化学']
time_slots = [1, 2, 3]
result = schedule_courses(teachers, courses, time_slots)
print("课程安排结果:")
for course, assignments in result.items():
    print(f"\n{course}:")
    for teacher, slot in assignments:
        print(f"  - {teacher} 在时段 {slot}")

完整示例：相亲匹配系统

import networkx as nx
import matplotlib.pyplot as plt
import random
class MatchMaker:
    """相亲匹配系统"""
    def __init__(self):
        self.graph = nx.Graph()
        self.men = []
        self.women = []
    def add_person(self, name, gender, interests, preferences):
        """添加人员"""
        if gender == '男':
            self.men.append(name)
            self.graph.add_node(name, bipartite=0, interests=interests)
        else:
            self.women.append(name)
            self.graph.add_node(name, bipartite=1, interests=interests)
        # 存储偏好
        self.graph.nodes[name]['preferences'] = preferences
    def calculate_compatibility(self, person1, person2):
        """计算兼容性分数"""
        inter1 = set(self.graph.nodes[person1]['interests'])
        inter2 = set(self.graph.nodes[person2]['interests'])
        # 共同兴趣数
        common = len(inter1 & inter2)
        total = len(inter1 | inter2)
        if total == 0:
            return 0
        interest_score = common / total
        # 偏好匹配
        pref1 = self.graph.nodes[person1]['preferences']
        pref2 = self.graph.nodes[person2]['preferences']
        pref_score = 0
        if person2 in pref1 and person1 in pref2:
            pref_score = 1.0
        return 0.6 * interest_score + 0.4 * pref_score
    def find_best_matches(self):
        """找到最佳匹配"""
        # 计算所有可能的配对兼容性
        for man in self.men:
            for woman in self.women:
                score = self.calculate_compatibility(man, woman)
                if score > 0:
                    self.graph.add_edge(man, woman, weight=score)
        # 求最大权重匹配
        matching = nx.max_weight_matching(self.graph, maxcardinality=True)
        return matching
    def visualize_matching(self, matching):
        """可视化匹配结果"""
        pos = nx.bipartite_layout(self.graph, self.men)
        plt.figure(figsize=(12, 8))
        # 绘制所有边
        nx.draw(self.graph, pos, with_labels=True, 
                node_color='lightgray', node_size=2000,
                font_size=10, alpha=0.3)
        # 高亮匹配边
        nx.draw_networkx_edges(self.graph, pos, edgelist=matching,
                              edge_color='red', width=2)
        # 添加兼容性分数标签
        for man, woman in matching:
            score = self.graph[man][woman]['weight']
            x = (pos[man][0] + pos[woman][0]) / 2
            y = (pos[man][1] + pos[woman][1]) / 2
            plt.text(x, y, f'{score:.2f}', fontsize=12, 
                    color='blue', fontweight='bold')
        plt.title("相亲匹配结果")
        plt.show()
# 使用示例
match_system = MatchMaker()
# 添加参与者
match_system.add_person('小明', '男', 
                        ['运动', '音乐', '旅行'],
                        ['小红', '小芳'])
match_system.add_person('小强', '男', 
                        ['游戏', '电影', '美食'],
                        ['小芳', '小丽'])
match_system.add_person('大伟', '男', 
                        ['读书', '运动', '摄影'],
                        ['小红', '小丽'])
match_system.add_person('小红', '女', 
                        ['旅行', '读书', '运动'],
                        ['小明', '大伟'])
match_system.add_person('小芳', '女', 
                        ['音乐', '美食', '电影'],
                        ['小明', '小强'])
match_system.add_person('小丽', '女', 
                        ['摄影', '旅行', '游戏'],
                        ['小强', '大伟'])
# 找到最佳匹配
matches = match_system.find_best_matches()
print("最佳匹配结果:")
for man, woman in matches:
    score = match_system.graph[man][woman]['weight']
    print(f"  {man} <-> {woman} (兼容性: {score:.2f})")
# 可视化
match_system.visualize_matching(matches)

注意事项

1. 数据类型：确保节点可哈希（字符串、元组等）
2. 二分图：使用nx.bipartite_layout时需正确设置节点属性
3. 权重处理：权重值应为数值类型，越大表示越优
4. 性能优化：大规模图建议使用max_weight_matching的maxcardinality参数

这些案例覆盖了NetworkX解决匹配问题的主要场景，根据你的具体需求,可以选择相应的实现方式。