Python婚礼座位规划代码咨询：100宾客10桌分配方案优化建议

Great call starting with a familiarity matrix—that’s exactly the right foundation for this problem! As a Python beginner, you’ve already nailed the core idea, so let’s break down feasible, beginner-friendly optimization paths and implementation steps to turn this into working code.

Core Idea Recap & Objective Clarification #

Your matrix approach is perfect: each entry familiarity[i][j] represents how well guest i and j get along (higher = more harmonious, lower = more conflict). Our goal is to maximize the total "happiness" of the seating arrangement—this means summing up all pairwise familiarity values within each table (since a table with more positive interactions will be more enjoyable).

For a table of guests, the happiness is calculated as:

sum(familiarity[i][j] for all i < j in the table)

Beginner-Friendly Optimization Approaches #

Brute-forcing all possible arrangements is impossible for 100 guests (the number of permutations is astronomical), so we need practical, iterative methods:

1. Greedy Algorithm (Easy to Code) #

Start by prioritizing the most compatible pairs first:

• Calculate all pairwise familiarity scores, sort them from highest to lowest.
• Assign guests to tables one pair at a time, ensuring no table exceeds its capacity (10 guests for your case) and no guest is assigned twice.
• Fill remaining spots with guests who have the least negative relationships with existing table members.

Pros: Simple to implement, fast to run. Cons: Might not give the absolute optimal arrangement, but it’s a solid starting point.

2. Iterative Improvement (Hill-Climbing) #

Take the greedy arrangement and make small tweaks to boost total happiness:

• Randomly swap two guests from different tables.
• Calculate if the total happiness increases after the swap.
• Keep the swap if it’s better; revert it if not.
• Repeat hundreds/thousands of times until no more improvements are found.

This is easy to code and often leads to much better arrangements than the greedy approach alone. For even better results, you can adapt it to simulated annealing (allowing occasional worse swaps early on to avoid getting stuck in a "local optimum").

Practical Implementation Steps #

Let’s outline code using your 12-guest/3-table example as a test case. We’ll use numpy for efficient matrix calculations (install it with pip install numpy if you haven’t).

Step 1: Define the Familiarity Matrix #

import numpy as np

# Example 12x12 familiarity matrix (symmetric, diagonal = 0)
familiarity = np.array([
    [0, 5, -2, 3, 1, 0, -1, 2, 4, -3, 0, 1],
    [5, 0, 3, -1, 2, 4, 0, 1, -2, 0, 3, 2],
    [-2, 3, 0, 2, -1, 1, 5, -3, 0, 4, -2, 0],
    [3, -1, 2, 0, 4, -2, 1, 3, -1, 0, 2, -1],
    [1, 2, -1, 4, 0, 3, -2, 1, 2, -1, 0, 4],
    [0, 4, 1, -2, 3, 0, 2, -1, 1, 3, -2, 0],
    [-1, 0, 5, 1, -2, 2, 0, 4, -3, 1, 3, -1],
    [2, 1, -3, 3, 1, -1, 4, 0, 2, -2, 1, 3],
    [4, -2, 0, -1, 2, 1, -3, 2, 0, 5, -1, 0],
    [-3, 0, 4, 0, -1, 3, 1, -2, 5, 0, 2, -1],
    [0, 3, -2, 2, 0, -2, 3, 1, -1, 2, 0, 4],
    [1, 2, 0, -1, 4, 0, -1, 3, 0, -1, 4, 0]
])

Step 2: Calculate Total Happiness #

def calculate_total_happiness(seating, familiarity):
    total = 0
    for table in seating:
        # Sum all pairwise familiarity values in the table
        table_matrix = familiarity[np.ix_(table, table)]
        # Sum upper triangle (avoid double-counting)
        total += np.sum(np.triu(table_matrix, k=1))
    return total

Step 3: Greedy Initial Seating #

def greedy_seating(familiarity, num_tables, table_size):
    num_guests = len(familiarity)
    # Create sorted list of pairs (highest familiarity first)
    pairs = []
    for i in range(num_guests):
        for j in range(i+1, num_guests):
            pairs.append((-familiarity[i][j], i, j))  # Negative for ascending sort
    pairs.sort()
    
    assigned = [False] * num_guests
    seating = [[] for _ in range(num_tables)]
    
    # Assign top pairs first
    for _, i, j in pairs:
        if not assigned[i] and not assigned[j]:
            for table in seating:
                if len(table) < table_size:
                    table.extend([i, j])
                    assigned[i] = assigned[j] = True
                    break
    
    # Fill remaining unassigned guests
    unassigned = [k for k in range(num_guests) if not assigned[k]]
    for guest in unassigned:
        # Find table where adding this guest gives maximum happiness boost
        best_table_idx = -1
        max_boost = -float('inf')
        for idx, table in enumerate(seating):
            if len(table) < table_size:
                boost = sum(familiarity[guest][member] for member in table)
                if boost > max_boost:
                    max_boost = boost
                    best_table_idx = idx
        seating[best_table_idx].append(guest)
    
    return seating

Step 4: Iterative Improvement (Hill-Climbing) #

def improve_seating(seating, familiarity, num_iterations=2000):
    num_tables = len(seating)
    table_size = len(seating[0])
    current_happiness = calculate_total_happiness(seating, familiarity)
    
    for _ in range(num_iterations):
        # Pick two random tables and one guest from each
        t1, t2 = np.random.choice(num_tables, 2, replace=False)
        g1 = np.random.choice(seating[t1])
        g2 = np.random.choice(seating[t2])
        
        # Swap guests temporarily
        seating[t1].remove(g1)
        seating[t1].append(g2)
        seating[t2].remove(g2)
        seating[t2].append(g1)
        
        new_happiness = calculate_total_happiness(seating, familiarity)
        
        if new_happiness > current_happiness:
            current_happiness = new_happiness
        else:
            # Revert swap if no improvement
            seating[t1].remove(g2)
            seating[t1].append(g1)
            seating[t2].remove(g1)
            seating[t2].append(g2)
    
    return seating, current_happiness

Putting It All Together #

# Test with 12 guests, 3 tables of 4
num_tables = 3
table_size = 4

initial_seating = greedy_seating(familiarity, num_tables, table_size)
initial_happiness = calculate_total_happiness(initial_seating, familiarity)
print(f"Initial Greedy Happiness: {initial_happiness}")

improved_seating, improved_happiness = improve_seating(initial_seating, familiarity)
print(f"Improved Happiness: {improved_happiness}")
print("\nFinal Seating Arrangement:")
for idx, table in enumerate(improved_seating):
    # Convert to 1-indexed guest numbers for readability
    print(f"Table {idx+1}: Guests {[g+1 for g in table]}")

Tips for Your 100-Guest Case #

• Hard Constraints: If guests must sit together, set their pairwise familiarity to a huge positive number (like 1000). If they must sit apart, set it to a huge negative number (like -1000).
• Efficiency: For 100 guests, numpy will drastically speed up calculations compared to pure Python loops.
• Visualization: Use matplotlib to plot a heatmap of your familiarity matrix or bar charts of each table’s happiness to spot patterns.
• Simulated Annealing: If hill-climbing gets stuck, look up simple simulated annealing implementations—they’re easy to adapt and explore more of the solution space.

As a beginner, starting with the greedy algorithm and adding hill-climbing is a great way to learn about combinatorial optimization without feeling overwhelmed. You’ll see tangible improvements in your seating plan, and you can build on this as your Python skills grow.

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