题目描述

问题名称：考场座位分配优化问题

背景：
在一个学校中，有10个班级，每个班级的学生人数不同，需要将这些学生分配到12个考场中，每个考场有42个座位，排列成6列7行。分配时需要满足以下条件：

1. 每个考场必须恰好有42个座位被占用。
2. 同一班级的学生不能坐在同一个考场的同一行或同一列。

输入：

• 班级人数数组：[50, 50, 50, 50, 51, 51, 51, 51, 50, 50]
• 考场数量：12
• 每个考场的座位数：42
• 座位排列：6列7行

输出：

• 一个二维数组，表示每个考场的座位分配情况，其中每个元素是一个包含班级编号和学生编号的元组。
• 每个考场每个班级的学生总数，以验证分配是否均匀。

算法要求：
设计一个算法来解决上述问题，并使用Python实现。如果无法找到一个满足所有约束条件的解决方案，需要说明理由。

解决思路(参考)

• 使用回溯算法尝试为每个学生分配考场和座位，同时检查是否违反了约束条件。
• 使用贪心算法初步分配学生，以减少回溯算法的搜索空间。
• 使用启发式方法（如最小剩余值优先）来指导搜索过程。

分析一下这个座位安排问题的约束条件和可行性。

首先列出问题的关键约束：

1. 12个考场，每个考场42人(6列7行)
2. 同一班级的学生不能坐在同一行或同一列
3. 1-10班的人数分别是: 50, 50, 50, 50, 51, 51, 51, 51, 50, 50
4. 总学生数: 504人
5. 总座位数: 12 * 42 = 504个，刚好等于学生总数

分析可行性：

1. 座位总数刚好等于学生总数，说明空间上是满足的
2. 每个考场6列7行的限制意味着同一个班级在一个考场最多只能安排6个学生(因为不能同行同列)
3. 对于人数最多的班级(51人)，需要分散到至少9个考场才能满足不同行同列的要求
4. 每个考场42个座位需要从10个班级中选择学生，且要保证不同行同列

实现算法来解决问题：

import numpy as np
from collections import defaultdict

class ExamRoom:
    def __init__(self, rows=7, cols=6):
        self.rows = rows
        self.cols = cols
        self.seats = np.zeros((rows, cols), dtype=int)  # 0表示空座位
        self.class_counts = defaultdict(int)  # 统计每个班级在该考场的人数
        
    def can_place_student(self, row, col, class_id):
        # 检查同一行是否有相同班级的学生
        if class_id in self.seats[row]:
            return False
            
        # 检查同一列是否有相同班级的学生
        if class_id in self.seats[:, col]:
            return False
            
        return True
        
    def place_student(self, row, col, class_id):
        self.seats[row, col] = class_id
        self.class_counts[class_id] += 1
        
    def is_full(self):
        return np.all(self.seats != 0)

class ExamSeatingSystem:
    def __init__(self, num_rooms=12, class_sizes=None):
        if class_sizes is None:
            class_sizes = [50, 50, 50, 50, 51, 51, 51, 51, 50, 50]
        self.num_rooms = num_rooms
        self.class_sizes = class_sizes
        self.rooms = [ExamRoom() for _ in range(num_rooms)]
        self.remaining_students = defaultdict(int)
        for i, size in enumerate(class_sizes, 1):
            self.remaining_students[i] = size
            
    def arrange_seating(self):
        # 使用贪婪算法尝试安排座位
        for room_idx in range(self.num_rooms):
            room = self.rooms[room_idx]
            for row in range(room.rows):
                for col in range(room.cols):
                    # 找到最适合放在当前位置的班级
                    best_class = self.find_best_class_for_position(room, row, col)
                    if best_class is None:
                        return False  # 无法完成安排
                    room.place_student(row, col, best_class)
                    self.remaining_students[best_class] -= 1
                    
        return self.verify_arrangement()
    
    def find_best_class_for_position(self, room, row, col):
        # 找到剩余学生最多且满足约束的班级
        valid_classes = []
        for class_id, remaining in self.remaining_students.items():
            if remaining > 0 and room.can_place_student(row, col, class_id):
                valid_classes.append((class_id, remaining))
        
        if not valid_classes:
            return None
            
        # 优先选择剩余学生最多的班级  只关注当前最优，而不考虑后续的影响。
        return max(valid_classes, key=lambda x: x[1])[0]
    
    def verify_arrangement(self):
        # 验证所有学生是否都被安排且满足约束
        total_arranged = defaultdict(int)
        for room in self.rooms:
            for class_id, count in room.class_counts.items():
                total_arranged[class_id] += count
        
        # 检查每个班级的学生数是否正确
        for class_id, size in enumerate(self.class_sizes, 1):
            if total_arranged[class_id] != size:
                return False
        return True
    
    def print_arrangement(self):
        for i, room in enumerate(self.rooms):
            print(f"\n考场 {i+1} 座位安排:")
            print(room.seats)
            print("\n各班级学生人数:")
            for class_id, count in sorted(room.class_counts.items()):
                print(f"班级 {class_id}: {count}人")

# 运行示例
def main():
    class_sizes = [50, 50, 50, 50, 51, 51, 51, 51, 50, 50]
    seating_system = ExamSeatingSystem(12, class_sizes)
    
    if seating_system.arrange_seating():
        print("座位安排成功！")
        seating_system.print_arrangement()
    else:
        print("无法完成座位安排，请检查约束条件。")

if __name__ == "__main__":
    main()

该算法使用以下策略：

1. 使用贪心算法进行座位分配：
   • 按照考场顺序，依次填充每个座位
   • 对于每个位置，选择剩余学生最多的符合条件的班级（局部最优选择）
   • 例如：
     • 假设当前有班级 A（剩余 10 人）和班级 B（剩余 5 人），且两个班级都满足座位约束。
     • 贪心算法会选择班级 A，因为它的剩余学生最多。贪心算法不会提前考虑全局影响。
     • 贪心算法通过简单的规则（选择剩余学生最多的班级）快速做出决策，而不需要复杂的计算。快速决策的特点使得贪心算法适合处理大规模问题。
2. 约束检查：
   • 实时检查同行同列约束
   • 追踪每个班级的剩余学生数量
   • 验证最终分配是否满足所有班级的学生总数
3. 数据结构：
   • 使用NumPy数组表示考场座位
   • 使用字典追踪每个班级的学生分配情况
4. 验证机制：
   • 检查所有学生是否都被安排
   • 验证每个班级的总人数是否正确
   • 确保满足不同行同列的约束

需要注意的是，这个问题是一个复杂的约束满足问题，可能存在多个有效解。当前的实现使用贪心策略，虽然不能保证在所有情况下都能找到解，但对于给定的条件，它会尝试找到一个可行的解决方案。并会输出每个考场的具体座位安排以及各班级的分配情况。如果无法找到解决方案，程序会提示无法完成安排。

拓展

与React前端组件结合起来,创建一个可视化的考场座位安排表

import React, { useState, useEffect } from 'react';
import { Card, CardHeader, CardContent } from '@/components/ui/card';

// 后端逻辑的JavaScript实现
class ExamRoom {
  constructor(rows = 7, cols = 6) {
    this.rows = rows;
    this.cols = cols;
    this.seats = Array(rows).fill().map(() => Array(cols).fill(0));
    this.classCounts = {};
  }

  canPlaceStudent(row, col, classId) {
    // 检查同行
    if (this.seats[row].includes(classId)) return false;
    // 检查同列
    for (let i = 0; i < this.rows; i++) {
      if (this.seats[i][col] === classId) return false;
    }
    return true;
  }

  placeStudent(row, col, classId) {
    this.seats[row][col] = classId;
    this.classCounts[classId] = (this.classCounts[classId] || 0) + 1;
  }
}

class SeatingSystem {
  constructor(numRooms = 12, classSizes = null) {
    this.classSizes = classSizes || [50, 50, 50, 50, 51, 51, 51, 51, 50, 50];
    this.numRooms = numRooms;
    this.rooms = Array(numRooms).fill().map(() => new ExamRoom());
    this.remainingStudents = {};
    this.classSizes.forEach((size, i) => {
      this.remainingStudents[i + 1] = size;
    });
  }

  findBestClass(room, row, col) {
    const validClasses = Object.entries(this.remainingStudents)
      .filter(([classId, remaining]) => 
        remaining > 0 && room.canPlaceStudent(row, col, parseInt(classId)))
      .map(([classId, remaining]) => [parseInt(classId), remaining]);
    
    if (validClasses.length === 0) return null;
    return validClasses.reduce((a, b) => b[1] > a[1] ? b : a)[0];
  }

  arrangeSeating() {
    for (let roomIdx = 0; roomIdx < this.numRooms; roomIdx++) {
      const room = this.rooms[roomIdx];
      for (let row = 0; row < room.rows; row++) {
        for (let col = 0; col < room.cols; col++) {
          const bestClass = this.findBestClass(room, row, col);
          if (bestClass === null) return false;
          room.placeStudent(row, col, bestClass);
          this.remainingStudents[bestClass]--;
        }
      }
    }
    return true;
  }
}

// React 组件
export default function ExamSeatingDisplay() {
  const [selectedRoom, setSelectedRoom] = useState(1);
  const [seatingData, setSeatingData] = useState(null);
  
  useEffect(() => {
    const system = new SeatingSystem();
    if (system.arrangeSeating()) {
      setSeatingData(system.rooms);
    }
  }, []);

  const getClassColor = (classId) => {
    const colors = [
      'bg-blue-100', 'bg-green-100', 'bg-yellow-100', 'bg-red-100', 
      'bg-purple-100', 'bg-pink-100', 'bg-indigo-100', 'bg-orange-100', 
      'bg-teal-100', 'bg-cyan-100'
    ];
    return colors[(classId - 1) % colors.length];
  };

  if (!seatingData) return <div className="p-4">正在生成座位安排...</div>;

  const currentRoom = seatingData[selectedRoom - 1];

  return (
    <Card className="w-full max-w-4xl mx-auto">
      <CardHeader className="flex flex-row items-center justify-between">
        <div className="text-xl font-bold">考场 {selectedRoom} 座位安排</div>
        <div className="flex items-center gap-2">
          <button 
            onClick={() => setSelectedRoom(prev => prev > 1 ? prev - 1 : 12)}
            className="px-3 py-1 rounded bg-gray-100 hover:bg-gray-200"
          >
            上一个
          </button>
          <span>{selectedRoom}/12</span>
          <button 
            onClick={() => setSelectedRoom(prev => prev < 12 ? prev + 1 : 1)}
            className="px-3 py-1 rounded bg-gray-100 hover:bg-gray-200"
          >
            下一个
          </button>
        </div>
      </CardHeader>
      
      <CardContent>
        <div className="grid grid-cols-6 gap-2 mb-6">
          {currentRoom.seats.map((row, rowIndex) => (
            row.map((classId, colIndex) => (
              <div
                key={`${rowIndex}-${colIndex}`}
                className={`aspect-square flex items-center justify-center rounded-lg ${getClassColor(classId)} relative`}
              >
                <span className="font-medium">{classId}班</span>
                <span className="absolute top-1 left-1 text-xs text-gray-500">
                  {rowIndex * 6 + colIndex + 1}
                </span>
              </div>
            ))
          ))}
        </div>

        <div className="grid grid-cols-5 gap-2">
          {Object.entries(currentRoom.classCounts).map(([classId, count]) => (
            <div key={classId} className="flex items-center gap-2 p-2 rounded">
              <div className={`w-4 h-4 rounded ${getClassColor(parseInt(classId))}`} />
              <span className="text-sm">{classId}班: {count}人</span>
            </div>
          ))}
        </div>
      </CardContent>
    </Card>
  );
}

1. 后端逻辑：

   • 将Python代码转换为等效的JavaScript实现
   • 保持了相同的约束检查和分配逻辑
   • 使用类似的数据结构和算法

2. 前端展示：

   • 直观的网格布局展示座位安排
   • 颜色编码区分不同班级
   • 座位编号显示
   • 班级统计信息
   • 考场切换功能

3. 交互功能：

   • 上一个/下一个考场导航
   • 显示当前考场编号
   • 每个座位显示班级和座位号
   • 底部显示各班级人数统计

4. 优化：

   • 使用useEffect确保只在组件加载时生成一次座位安排
   • 使用状态管理保存和切换考场数据
   • 响应式设计适应不同屏幕尺寸

效果图：