Python案例如何用Networkx做稳定婚姻

本文目录导读：

1. 什么是稳定婚姻问题
2. 完整实现案例
3. 关键点说明

我来详细讲解如何使用NetworkX实现稳定婚姻匹配算法（Gale-Shapley算法）。

什么是稳定婚姻问题

稳定婚姻问题是指：有n个男性和n个女性，每个人对异性都有偏好排序，需要找到一种配对方式，使得不存在"不稳定对"。

完整实现案例

基础实现

import networkx as nx
import matplotlib.pyplot as plt
def stable_marriage(men_preferences, women_preferences):
    """
    实现Gale-Shapley稳定婚姻算法
    参数:
    men_preferences: dict, 每个男性的偏好列表
    women_preferences: dict, 每个女性的偏好列表
    返回:
    matches: dict, 男性到女性的匹配
    """
    # 初始化
    free_men = list(men_preferences.keys())  # 未匹配的男性
    matches = {}  # 男性 -> 女性
    woman_matches = {}  # 女性 -> 男性
    proposal_count = {men: 0 for men in men_preferences}  # 每个男性已经求婚的次数
    # 当还有未匹配的男性时继续
    while free_men:
        man = free_men[0]  # 取第一个未匹配的男性
        # 获取该男性的偏好列表
        preferences = men_preferences[man]
        # 如果还有未求婚的女性
        if proposal_count[man] < len(preferences):
            woman = preferences[proposal_count[man]]
            proposal_count[man] += 1
            # 如果该女性未匹配
            if woman not in woman_matches:
                # 匹配成功
                matches[man] = woman
                woman_matches[woman] = man
                free_men.remove(man)
            else:
                # 该女性已匹配，比较当前匹配和新的求婚者
                current_match = woman_matches[woman]
                woman_pref = women_preferences[woman]
                # 如果女性更喜欢新的追求者
                if woman_pref.index(man) < woman_pref.index(current_match):
                    # 更换匹配
                    matches[man] = woman
                    woman_matches[woman] = man
                    free_men.remove(man)
                    free_men.append(current_match)
                    del matches[current_match]
        else:
            # 该男性已经向所有女性求婚过，但仍未匹配
            free_men.remove(man)
    return matches
def create_preference_graph(preferences, title="偏好关系图"):
    """创建偏好关系图"""
    G = nx.DiGraph()
    # 添加节点和边
    for person, prefs in preferences.items():
        for rank, pref in enumerate(prefs):
            # 权重表示偏好程度，越小越偏好
            G.add_edge(person, pref, weight=rank, 
                      label=f"rank {rank+1}")
    # 绘制图形
    pos = nx.spring_layout(G, k=1, iterations=50)
    plt.figure(figsize=(10, 8))
    # 绘制节点
    nx.draw_networkx_nodes(G, pos, node_color='lightblue', 
                          node_size=500, alpha=0.8)
    # 绘制边，根据权重调整颜色
    edges = G.edges(data=True)
    weights = [edge[2]['weight'] for edge in edges]
    colors = plt.cm.RdYlGn([w/max(weights) for w in weights])
    nx.draw_networkx_edges(G, pos, edge_color=colors, 
                          arrowstyle='->', arrowsize=20, width=2)
    # 添加标签
    nx.draw_networkx_labels(G, pos, font_size=12, font_weight='bold')
    plt.title(title)
    plt.axis('off')
    return G
def visualize_matching(matches, men_preferences, women_preferences):
    """可视化匹配结果"""
    G = nx.Graph()
    # 添加男性节点
    for man in men_preferences.keys():
        G.add_node(man, bipartite=0, color='lightblue', size=500)
    # 添加女性节点
    for woman in women_preferences.keys():
        G.add_node(woman, bipartite=1, color='lightpink', size=500)
    # 添加匹配边
    for man, woman in matches.items():
        G.add_edge(man, woman, color='red', width=3)
    # 设置布局
    pos = {}
    men = list(men_preferences.keys())
    women = list(women_preferences.keys())
    # 男性在上方，女性在下方
    for i, man in enumerate(men):
        pos[man] = (i, 1)
    for i, woman in enumerate(women):
        pos[woman] = (i, 0)
    plt.figure(figsize=(12, 6))
    # 绘制节点
    node_colors = ['lightblue' if node in men else 'lightpink' 
                   for node in G.nodes()]
    nx.draw_networkx_nodes(G, pos, node_color=node_colors, 
                          node_size=500, alpha=0.8)
    # 绘制边
    edge_colors = ['red' if 'color' in G.edges[edge] and G.edges[edge]['color'] == 'red' 
                   else 'gray' for edge in G.edges()]
    edge_widths = [3 if 'width' in G.edges[edge] and G.edges[edge]['width'] == 3 
                   else 1 for edge in G.edges()]
    nx.draw_networkx_edges(G, pos, edge_color=edge_colors, 
                          width=edge_widths, alpha=0.7)
    # 添加标签
    nx.draw_networkx_labels(G, pos, font_size=12, font_weight='bold')
    plt.title("稳定婚姻匹配结果", fontsize=14)
    plt.axis('off')
    return G
# 示例数据
men_preferences = {
    '张三': ['李婷', '王芳', '赵雪'],
    '李四': ['王芳', '李婷', '赵雪'],
    '王五': ['赵雪', '王芳', '李婷']
}
women_preferences = {
    '李婷': ['张三', '李四', '王五'],
    '王芳': ['李四', '张三', '王五'],
    '赵雪': ['王五', '张三', '李四']
}
# 执行稳定婚姻匹配
matches = stable_marriage(men_preferences, women_preferences)
print("匹配结果:")
for man, woman in matches.items():
    print(f"{man} <-> {woman}")
# 可视化偏好关系
print("\n男性偏好关系图:")
G_men = create_preference_graph(men_preferences, "男性偏好")
plt.show()
print("\n女性偏好关系图:")
G_women = create_preference_graph(women_preferences, "女性偏好")
plt.show()
# 可视化匹配结果
print("\n匹配结果可视化:")
G_matching = visualize_matching(matches, men_preferences, women_preferences)
plt.show()

高级功能实现

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
class StableMarriageSolver:
    """稳定婚姻问题求解器"""
    def __init__(self, men_preferences, women_preferences):
        self.men = list(men_preferences.keys())
        self.women = list(women_preferences.keys())
        self.men_preferences = men_preferences
        self.women_preferences = women_preferences
        self.matches = {}
    def solve(self):
        """求解稳定婚姻问题"""
        free_men = self.men.copy()
        matches = {}
        woman_matches = {}
        proposal_count = {man: 0 for man in self.men}
        while free_men:
            man = free_men[0]
            if proposal_count[man] < len(self.women):
                woman = self.men_preferences[man][proposal_count[man]]
                proposal_count[man] += 1
                if woman not in woman_matches:
                    matches[man] = woman
                    woman_matches[woman] = man
                    free_men.remove(man)
                else:
                    current = woman_matches[woman]
                    woman_pref = self.women_preferences[woman]
                    if woman_pref.index(man) < woman_pref.index(current):
                        matches[man] = woman
                        woman_matches[woman] = man
                        free_men.remove(man)
                        free_men.append(current)
                        del matches[current]
            else:
                free_men.remove(man)
        self.matches = matches
        return matches
    def check_stability(self):
        """检查匹配是否稳定"""
        if not self.matches:
            print("请先运行solve()方法")
            return False
        for man, wife in self.matches.items():
            man_pref = self.men_preferences[man]
            woman_pref_index = man_pref.index(wife)
            # 检查每个男性是否会与更偏好的女性形成不稳定对
            for better_woman in man_pref[:woman_pref_index]:
                better_woman_husband = {v: k for k, v in self.matches.items()}[better_woman]
                better_woman_pref = self.women_preferences[better_woman]
                # 检查这个女性是否也更喜欢当前男性
                if better_woman_pref.index(man) < better_woman_pref.index(better_woman_husband):
                    print(f"发现不稳定对: ({man}, {better_woman})")
                    return False
        print("匹配是稳定的!")
        return True
    def create_matching_graph(self):
        """创建匹配关系图"""
        G = nx.Graph()
        # 添加节点
        for man in self.men:
            G.add_node(man, type='man', color='blue')
        for woman in self.women:
            G.add_node(woman, type='woman', color='red')
        # 添加匹配边
        for man, woman in self.matches.items():
            G.add_edge(man, woman, color='green', style='solid')
        return G
    def create_preference_matrix(self):
        """创建偏好矩阵"""
        n = len(self.men)
        matrix = np.zeros((n, n))
        for i, man in enumerate(self.men):
            for j, woman in enumerate(self.women):
                if man in self.matches and self.matches[man] == woman:
                    matrix[i][j] = 1
        return matrix
    def visualize_all(self):
        """综合可视化"""
        fig, axes = plt.subplots(2, 2, figsize=(15, 12))
        # 1. 匹配关系图
        G = self.create_matching_graph()
        pos = nx.spring_layout(G, k=2, iterations=50)
        node_colors = ['lightblue' if G.nodes[node]['type'] == 'man' 
                      else 'lightpink' for node in G.nodes()]
        nx.draw(G, pos, ax=axes[0,0], with_labels=True, 
               node_color=node_colors, node_size=500, 
               edge_color='green', width=2, font_weight='bold')
        axes[0,0].set_title('匹配关系图')
        # 2. 偏好矩阵热图
        matrix = self.create_preference_matrix()
        im = axes[0,1].imshow(matrix, cmap='RdYlGn', aspect='auto')
        axes[0,1].set_xticks(range(len(self.women)))
        axes[0,1].set_yticks(range(len(self.men)))
        axes[0,1].set_xticklabels(self.women)
        axes[0,1].set_yticklabels(self.men)
        axes[0,1].set_title('匹配矩阵')
        plt.colorbar(im, ax=axes[0,1])
        # 3. 男性偏好关系图
        G_men = nx.DiGraph()
        for man, prefs in self.men_preferences.items():
            for rank, pref in enumerate(prefs):
                G_men.add_edge(man, pref, weight=rank)
        pos_men = nx.spring_layout(G_men, k=1)
        edges = G_men.edges(data=True)
        weights = [edge[2]['weight'] for edge in edges]
        nx.draw(G_men, pos_men, ax=axes[1,0], with_labels=True,
               node_color='lightblue', node_size=400,
               edge_color=weights, edge_cmap=plt.cm.Blues,
               width=2, font_weight='bold')
        axes[1,0].set_title('男性偏好关系')
        # 4. 女性偏好关系图
        G_women = nx.DiGraph()
        for woman, prefs in self.women_preferences.items():
            for rank, pref in enumerate(prefs):
                G_women.add_edge(woman, pref, weight=rank)
        pos_women = nx.spring_layout(G_women, k=1)
        edges_w = G_women.edges(data=True)
        weights_w = [edge[2]['weight'] for edge in edges_w]
        nx.draw(G_women, pos_women, ax=axes[1,1], with_labels=True,
               node_color='lightpink', node_size=400,
               edge_color=weights_w, edge_cmap=plt.cm.Reds,
               width=2, font_weight='bold')
        axes[1,1].set_title('女性偏好关系')
        plt.tight_layout()
        plt.show()
# 使用示例
if __name__ == "__main__":
    # 定义偏好
    men_prefs = {
        '张三': ['李婷', '王芳', '赵雪'],
        '李四': ['王芳', '李婷', '赵雪'],
        '王五': ['赵雪', '王芳', '李婷']
    }
    women_prefs = {
        '李婷': ['张三', '李四', '王五'],
        '王芳': ['李四', '张三', '王五'],
        '赵雪': ['王五', '张三', '李四']
    }
    # 创建求解器
    solver = StableMarriageSolver(men_prefs, women_prefs)
    # 解决问题
    matches = solver.solve()
    print("稳定婚姻匹配结果:")
    for man, woman in matches.items():
        print(f"{man} <-> {woman}")
    # 检查稳定性
    solver.check_stability()
    # 可视化
    solver.visualize_all()

随机生成测试数据

import random
def generate_random_preferences(n, seed=None):
    """生成随机偏好数据"""
    if seed:
        random.seed(seed)
    men_names = [f'男{i+1}' for i in range(n)]
    women_names = [f'女{i+1}' for i in range(n)]
    men_preferences = {}
    women_preferences = {}
    for man in men_names:
        prefs = women_names.copy()
        random.shuffle(prefs)
        men_preferences[man] = prefs
    for woman in women_names:
        prefs = men_names.copy()
        random.shuffle(prefs)
        women_preferences[woman] = prefs
    return men_preferences, women_preferences
# 生成5个男性和5个女性的随机偏好
men_prefs, women_prefs = generate_random_preferences(5, seed=42)
print("随机生成的男性偏好:")
for man, prefs in men_prefs.items():
    print(f"{man}: {prefs}")
print("\n随机生成的女性偏好:")
for woman, prefs in women_prefs.items():
    print(f"{woman}: {prefs}")
# 求解
solver = StableMarriageSolver(men_prefs, women_prefs)
matches = solver.solve()
print("\n匹配结果:")
for man, woman in matches.items():
    print(f"{man} <-> {woman}")
solver.check_stability()

关键点说明

1. 算法核心：Gale-Shapley算法的实现
2. NetworkX应用：使用图形表示偏好关系和匹配结果
3. 稳定性检查：验证匹配结果是否稳定
4. 可视化：多角度展示匹配结果

这个案例展示了如何使用NetworkX来建模和解决稳定婚姻问题,包括算法实现、图形可视化和结果验证。