การจับคู่ที่สมบูรณ์แบบ: วิธีการฮังกาเรียน (The Hungarian Method)

 

 

มาทำความรู้จักกับการจับคู่ที่สมบูรณ์แบบ

การจับคู่ที่สมบูรณ์แบบ (Perfect Matching) มีความสำคัญในหลายแง่มุมของวิทยาการคอมพิวเตอร์และการวิเคราะห์ข้อมูล การถามหาวิธีที่ดีที่สุดในการจับคู่รายการสองชุดอยู่เป็นเรื่องที่ถูกพูดถึงมากมาย และหนึ่งในวิธีที่ได้รับความนิยมคือ "วิธีการฮังกาเรียน" (The Hungarian Method)

วิธีการฮังกาเรียนได้ถูกพัฒนาขึ้นในปี 1955 โดยนักคณิตศาสตร์ชาวฮังการีที่ชื่อว่า "D. L. Konig" เพื่อแก้ไขปัญหาในด้านการจับคู่งานหรือการจัดสรรทรัพยากร ซึ่งเป็นการสร้างความสัมพันธ์ระหว่างชุดข้อมูลสองชุดให้ได้ผลลัพธ์ที่ดีที่สุด จากนั้นมันถูกนำไปใช้ในหลากหลายสถานการณ์ เช่น การจับคู่ผู้สมัครงานกับนายจ้าง การจัดสรรรถบรรทุกไปเก็บของในคลังสินค้า เป็นต้น

 

วิธีการฮังกาเรียนทำงานอย่างไร?

วิธีการฮังกาเรียนจะใช้ทฤษฎีกราฟซึ่งสามารถทำงานได้ตามลำดับขั้นตอน ดังนี้

1. สร้างกราฟ: ข้อมูลจะถูกจัดทำในรูปแบบกราฟ โดยมีจุดเชื่อมโยงระหว่างวัตถุในชุดที่หนึ่งกับชุดที่สอง 2. หาค่าต่ำสุด: ค้นหาค่าต่ำสุดซึ่งจะแสดงถึงการเลือกคู่ที่ดีที่สุด 3. วิเคราะห์ความเป็นไปได้: ศึกษาข้อมูลเพื่อดูว่ามีการจับคู่ที่สามารถดำเนินการได้อย่างไร ทำให้สามารถหาวิธีที่มีต้นทุนต่ำที่สุด

 

ตัวอย่างการใช้ Would Use Case ในโลกจริง

โดยสมมติว่าเรามีผู้สมัครงานจำนวน 4 คนและตำแหน่งที่เปิดรับสมัคร 4 ตำแหน่ง เราต้องการหาการจับคู่ที่ดีที่สุดที่จะทำให้เกิดประสิทธิภาพในการทำงานสูงสุด โดยการประเมินจะเป็นเชิงตัวเลขที่แสดงถึงความสามารถของผู้สมัครในแต่ละตำแหน่ง

ตารางความสามารถ:

| | ตำแหน่ง A | ตำแหน่ง B | ตำแหน่ง C | ตำแหน่ง D |

|-------|------------|------------|------------|------------|

| ผู้สมัคร 1 | 8 | 6 | 7 | 5 |

| ผู้สมัคร 2 | 7 | 8 | 6 | 4 |

| ผู้สมัคร 3 | 6 | 5 | 8 | 7 |

| ผู้สมัคร 4 | 5 | 4 | 7 | 6 |

จากตารางข้างต้น ทำให้เราสามารถใช้วิธีการฮังกาเรียนเพื่อหาการจับคู่ที่มีประสิทธิภาพที่สุด

 

โค้ดตัวอย่างใน Swift

ต่อไปนี้คือโค้ดตัวอย่างในการใช้วิธีการฮังกาเรียนเพื่อหาการจับคู่ที่ดีที่สุดในภาษา Swift:

 import Foundation

class HungarianMethod {
    var costMatrix: [[Int]]
    var n: Int
    var u: [Int]
    var v: [Int]
    var p: [Int]
    var way: [Int]

    init(costMatrix: [[Int]]) {
        self.costMatrix = costMatrix
        self.n = costMatrix.count
        self.u = Array(repeating: 0, count: n)
        self.v = Array(repeating: 0, count: n)
        self.p = Array(repeating: 0, count: n)
        self.way = Array(repeating: 0, count: n)
    }

    func solve() {
        for i in 0..<n {
            p[0] = i + 1
            var j0 = 0
            var minV = Array(repeating: Int.max, count: n)
            var used = Array(repeating: false, count: n)
            var j1 = 0

            repeat {
                used[j0] = true
                var delta = Int.max
                var j1 = 0

                for j in 0..<n {
                    if !used[j] {
                        let cur = costMatrix[p[i]][j] - u[p[i]] - v[j]
                        if cur < minV[j] {
                            minV[j] = cur
                            way[j] = j0
                        }
                        if minV[j] < delta {
                            delta = minV[j]
                            j1 = j
                        }
                    }
                }

                for j in 0..<n {
                    if used[j] {
                        u[p[i]] += delta
                        v[j] -= delta
                    } else {
                        minV[j] -= delta
                    }
                }
                j0 = j1
            } while p[j0] != 0

            while j0 != 0 {
                j1 = way[j0]
                p[j0] = p[j1]
                j0 = j1
            }
        }
    }

    func displayResult() {
        for j in 1..<n {
            let i = p[j]
            print("ผู้สมัคร \(i) ตำแหน่ง \(j)")
        }
    }
}

// การใช้งาน
let costMatrix: [[Int]] = [
    [8, 6, 7, 5],
    [7, 8, 6, 4],
    [6, 5, 8, 7],
    [5, 4, 7, 6]
]

let hungarian = HungarianMethod(costMatrix: costMatrix)
hungarian.solve()
hungarian.displayResult()

 

วิเคราะห์ Complexity

ความซับซ้อนของการทำงานวิธีการฮังกาเรียนคือ \(O(n^3)\) ซึ่งหมายความว่าการทำงานจะมีผลกระทบจากจำนวนงานที่เพิ่มขึ้นในระดับของกำลังสาม โดยปกติวิธีนี้จะค่อนข้างเร็วสำหรับปัญหาที่ไม่ใหญ่มากนัก

 

ข้อดีและข้อเสีย

ข้อดี

1. ประสิทธิภาพ: วิธีการฮังกาเรียนสามารถให้ผลลัพธ์ที่ถูกต้องมากในเวลาอันรวดเร็ว 2. ความยืดหยุ่น: สามารถนำไปใช้ในสถานการณ์ที่แตกต่างกันได้หลากหลาย 3. เวลาทำนายได้: การคาดการณ์เวลาในการทำงานเป็นไปได้ง่ายเมื่อรู้ขนาดของข้อมูล

ข้อเสีย

1. ความจำกัด: หากมีข้อมูลที่มีความซับซ้อนมาก หรือกราฟขนาดใหญ่ การคำนวณอาจใช้เวลานานขึ้น 2. การใช้งานที่ซับซ้อน: สำหรับผู้ที่ไม่มีพื้นฐานในคณิตศาสตร์หรือทฤษฎีกราฟ อาจทำให้ไม่เข้าใจได้ง่าย

 

สรุป

วิธีการฮังกาเรียนถือเป็นหนึ่งในวิธีที่มีประสิทธิภาพในการแก้ไขปัญหาการจับคู่ที่สมบูรณ์แบบ ด้วยการใช้งานง่ายและผลลัพธ์ที่ถูกต้อง อย่างไรก็ตาม การเข้าใจและประยุกต์ใช้งานอาจต้องใช้เวลาและการฝึกฝน ถ้าหากคุณสนใจในการเรียนรู้เพิ่มเติมเกี่ยวกับการเขียนโปรแกรมขั้นสูงและทฤษฎีการคำนวณ มาเรียนรู้กับ EPT กันเถอะ! EPT มีหลักสูตรที่หลากหลายสำหรับการพัฒนาทักษะของคุณในทางด้านการเขียนโปรแกรมและวิทยาในการคำนวณได้ดียิ่งขึ้น!

 

 

หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง