นี่คือโปรแกรม C++ สำหรับแก้ปัญหาการจับคู่ (Matching Problem) สำหรับกรณีเฉพาะ โดยมี N ชายและ N หญิง แต่ละคนจัดอันดับความชอบของเพศตรงข้าม จับคู่ชายและหญิงเข้าด้วยกัน โดยที่ไม่มีคู่ใดของเพศตรงข้ามที่ทั้งสองชอบกันมากกว่าคู่ปัจจุบัน ทุกการแต่งงานจะเป็น "Stable" หากไม่มีคนแบบนั้นอยู่
อัลกอริทึม
เริ่มต้น ฟังก์ชัน WomenPrefersMenOverMen1(): A) ตรวจสอบว่าหญิงชอบชายคนนี้มากกว่าชายที่หมั้นอยู่ (men1) B) ถ้า men1 อยู่ก่อน men ในรายการของหญิง แสดงว่าหญิงชอบคู่หมั้นปัจจุบัน C) ถ้า men อยู่ก่อน men1 ในรายการของหญิง ให้ยกเลิกการหมั้นกับ men1 และหมั้นกับ men แทน จบ เริ่มต้น ฟังก์ชัน stablewedding(): 1) ชายหมายเลข 0 ถึง N-1 2) หญิงหมายเลข N ถึง 2N-1 3) ในขณะที่ชายยังโสด A) เลือกชายโสดคนแรก B) ไปหาหญิงทีละคนตามลำดับความชอบของชายคนนั้น C) หญิงที่ถูกเลือกยังโสด หญิงและชายจะเป็นคู่ D) ถ้าหญิงไม่โสด หาคู่หมั้นปัจจุบันของหญิง E) ถ้าหญิงชอบชายคนนี้มากกว่าคู่หมั้นปัจจุบัน (men1) ให้ยกเลิกการหมั้นระหว่างหญิงและ men1 และจับคู่ชายคนนี้กับหญิงแทน จบ
ตัวอย่างโค้ด
#include <iostream> #include <string.h> #include <stdio.h> using namespace std; #define N 4 bool WomenPrefersMenOverMen1(int prefer[2*N][N], int w, int m, int m1) { for (int i = 0; i < N; i++) { if (prefer[w][i] == m1) return true; if (prefer[w][i] == m) return false; } } void stablewedding(int prefer[2*N][N]) { int wPartner[N]; //อาร์เรย์เก็บคู่ของหญิง bool mFree[N]; //อาร์เรย์เก็บสถานะโสดของชาย //เริ่มต้นชายและหญิงทั้งหมดเป็นโสด memset(wPartner, -1, sizeof(wPartner)); memset(mFree, false, sizeof(mFree)); int freeCnt = N; while (freeCnt > 0) { //ในขณะที่ชายยังโสด int m; //เลือกชายโสดคนแรก //ไปหาหญิงทีละคนตามลำดับความชอบของชายคนนั้น for (m = 0; m < N; m++) if (mFree[m] == false) break; for (int i = 0; i < N && mFree[m] == false; i++) { int w = prefer[m][i]; //หญิงที่ถูกเลือกยังโสด หญิงและชายจะเป็นคู่ if (wPartner[w-N] == -1) { wPartner[w-N] = m; mFree[m] = true; freeCnt--; } else { //ถ้าหญิงไม่โสด //หาคู่หมั้นปัจจุบันของหญิง int m1 = wPartner[w-N]; // ถ้าหญิงชอบชายคนนี้มากกว่าคู่หมั้นปัจจุบัน men1 // แล้วยกเลิกการหมั้นระหว่างหญิงและ men1 และจับคู่ชายคนนี้กับหญิง if (WomenPrefersMenOverMen1(prefer, w, m, m1) == false) { wPartner[w-N] = m; mFree[m] = true; mFree[m1] = false; } } } } cout << "Woman Man" << endl; for (int i = 0; i < N; i++) cout << " " << i+N << "\t" << wPartner[i] << endl; } int main() { int p[2*N][N] = { {7, 5, 6, 4}, {5, 4, 7, 6}, {4, 5, 7, 6}, {4, 5, 7, 6}, {0, 1, 3, 2}, {0, 1, 3, 2}, {0, 1, 3, 2}, {0, 1, 3, 2}, }; stablewedding(p); return 0; }
ผลลัพธ์
Woman Man 4 3 5 1 6 2 7 0
