基于稳定婚配算法实现的志愿和招生匹配程序应用

基于学生填报的志愿，结合招生计划进行招生工作，是各类招考系统中，常见的应用场景和需求。本文探讨了一个借助稳定婚配算法，用于志愿和招生匹配录取操作程序的应用案例。

稳定婚配算法

稳定婚配算法，又称为Gale-Shapley算法。关于这个算法的理论和细节这里不会特别深入讨论。主要是从应用和操作的角度，来结合具体的问题来进行分析。下面是这个算法的伪代码(它以婚配过程为例)：

如果想要更深入的了解相关的内容，可以参考这位大神的算法教程：

github.com/wangshusen/…

我们以招生工作涉及的考生和志愿院校为例，讨论其应用稳定婚配算法的相关要素包括：

• 请求集合，由一定数量的请求方元素构成，这里就是考生
• 请求优先列表，每个请求集合中的元素都有自己的意向优先表，就是有序的接受集合列表，就是考生的志愿列表
• 接受集合，接受集合的元素数量，这里就是招生院校的招生位，它由院校清单和招生计划展开而成
• 接受优先列表，每个接收方也都有自己的意向优先列表，就是有序的考生列表，如按照成绩排序，或者随机确定顺序

这里有几个约束和需要注意的问题：

• 请求集合和接受集合的算法地位并不完全相同，匹配算法的结果有利于请求方，所以应该合理评估业务需求，确定请求和接收方
• 请求方的数量和接受方的数量是一样的
• 请求方和接受方的优先意向列表，数量也是一样的，都是某一方的数量，但顺序可以由需求和业务确定，比如考生志愿由考生自己填写志愿时确定；而学生顺序由学生成绩确定

算法基本过程如下：

1 每一个未匹配的请求者，以请求对象的优先次序，向接受方提出匹配请求

2 如果接受方未匹配，则接受匹配请求，完成匹配

3 如果接受方已经匹配，则接受方评估当前请求者是否在意向优先列表中更优先

3.1 如果更优先，则接受匹配

3.2 如果不优先，则维持当前匹配，未接收的请求方，可能需要进入下一轮

4 无论匹配结果如何，请求方需要在自己的优先列表中，去除当前的请求对象

5 进入下一轮匹配，直到所有请求者完成匹配

对于合规的数据和组织方式，通过稳定婚姻匹配算法，可以确保实现一个稳定的匹配。

下面，我们使用一套测试用的数据，和相关的示例代码，来分析这个算法的具体应用和实现。

实现和实例

基础数据

本示例中有三个学校，总招生计划为9，分校招生计划分别为UA: 2 ，UB: 3, UC: 4

同时有9个学生，分别为 S01~S09

录取位置归化

将三个学校的录取计划，展开化为10个录取位： UA1、UA2、UB1、UB2、UB3、UC1、UC2、UC3、UC4

编写志愿意向表：

由学生填报志愿时确定。例如：

学生	志愿
S01	UA,UB,UC
S02	UA,UB,UC
S03	UC,UB,UA
S04	UC,UA,UB
S05	UA,UC,UB
S06	UA,UC,UB
S07	UB,UA,UC
S08	UC,UB,UA
S09	UA,UB,UC

利用稳定婚配算法求解

下面是示例测试代码：

const 
// 录取学校-集合，学生列表-志愿
RLIST = { UA:2, UB: 3, UC: 4},
SLIST = {
    S01: { wList: ["UA","UB","UC"] },
    S02: { wList: ["UA","UB","UC"] },
    S03: { wList: ["UC","UB","UA"] },
    S04: { wList: ["UC","UA","UB"] },
    S05: { wList: ["UA","UC","UB"] },
    S06: { wList: ["UA","UC","UB"] },
    S07: { wList: ["UB","UA","UC"] },
    S08: { wList: ["UC","UB","UA"] },
    S09: { wList: ["UA","UB","UC"] },
},
// 录取初始值
XVALUE = "XXX"; 

// 匹配方法
const doMatch = (data)=>{
    // 院校录取位列表，初始值设置
    let HLIST = Object.values(data)[0].wList.sort().reduce((c,v)=>(c[v] = null,c),{});
    let stu, ostu, bRoll = true;

    while(bRoll) {         
        bRoll = false; // 默认退出
        Object.keys(data).forEach(sid=>{ // 遍历学生
            stu = data[sid];            
            if (!stu.School) { // 是否需要处理学生志愿
                school = stu.wList.shift(); // 优先志愿
                ostu = HLIST[school] || XVALUE ; 

                if (sid < ostu) { // 判断学生优先级 需要替换
                    HLIST[school] = sid;
                    data[sid].School = school;

                    if (ostu !== XVALUE) { //学校修改录取学生
                        data[ostu].School = null;
                        bRoll = true; // 需要进入下一轮
                    } 
                } else {                     
                    bRoll = true; // 未匹配，需要进入下一轮
                }
            };
        });
    };

    // 返回学校录取位 
    return HLIST;
};

const start = ()=>{
    let rlist2 = Object.keys(RLIST).reduce((c,k)=>{
        c[k] = Array(RLIST[k]).fill().map((v,i)=> k +  (i+1).toString().padStart(3,"0") );
        return c;
    },{});

    
    // 展开志愿
    Object.keys(SLIST).forEach(k=>SLIST[k].wList = SLIST[k].wList.map(v=> rlist2[v]).flat());
    
    // 学校录取位匹配表
    let r = doMatch(SLIST);
    console.log("School Match:",r );
}; start();

// 结果：
node h
School Match: {
  UA001: 'S01',
  UA002: 'S02',
  UB001: 'S07',
  UB002: 'S08',
  UB003: 'S09',
  UC001: 'S03',
  UC002: 'S04',
  UC003: 'S05',
  UC004: 'S06'
}

小结

本文探讨了一个借助稳定婚配算法(Gale_Shapley)，用于志愿和招生匹配录取操作程序的应用案例。简单分析了GS算法的基本过程，并提供了示例数据结构设计和代码实现