การจับคู่ที่สมบูรณ์ (The Perfect Matching) ด้วยวิธีฮังการี (The Hungarian Method)

 

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

 

ทำความเข้าใจเกี่ยวกับ Algorithm นี้

วิธีฮังการี (Hungarian Method)

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

Use Case ในโลกจริง

- การจัดสรรพนักงาน: หากคุณมีพนักงานที่มีทักษะแตกต่างกันและงานที่ต้องการมอบหมาย โดยมีต้นทุนแตกต่างกันในการมอบหมายแต่ละพนักงานให้กับงาน การใช้วิธีฮังการีจะช่วยให้คุณมอบหมายงานไปยังพนักงานได้อย่างมีประสิทธิภาพที่สุด - การจับคู่สินค้ากับลูกค้า: ในระบบอีคอมเมิร์ซ การจับคู่สินค้าที่เหมาะสมให้กับลูกค้าโดยพิจารณาจากความสนใจและความต้องการในต้นทุนที่ต่ำที่สุด

 

การวิเคราะห์อัลกอริธึมนี้

Complexity

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

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

ข้อดี

- คำนวณได้อย่างมีประสิทธิภาพในการจับคู่ในสถานการณ์ที่มีหลายตัวเลือก

- ช่วยลดค่าใช้จ่ายโดยการหาต้นทุนที่ต่ำที่สุด

ข้อเสีย

- เมื่อเทียบกับวิธีอื่น ๆ อาจมีความซับซ้อนในกระบวนการทำ

- ขึ้นอยู่กับการมีอยู่ของข้อมูลที่เป็นจำนวนเต็ม (integer)

 

ตัวอย่างโค้ดในภาษา Kotlin

เราจะพัฒนาโค้ดในภาษา Kotlin ที่จะทำให้เรานำเสนอวิธีฮังการี เพื่อหาค่าต่ำสุดในการจับคู่:

 fun hungarianMethod(cost: Array<IntArray>): Pair<Int, List<Pair<Int, Int>>> {
    val n = cost.size
    val u = IntArray(n)
    val v = IntArray(n)
    val p = IntArray(n)
    val way = IntArray(n)

    for (i in 1 until n) {
        p[0] = i
        var j0 = 0
        val minv = IntArray(n)
        val used = BooleanArray(n)
        do {
            used[j0] = true
            var j1 = -1
            var delta = Int.MAX_VALUE

            for (j in 1 until n) {
                if (!used[j]) {
                    val cur = cost[p[0]][j] - u[p[0]] - 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 until n) {
                if (used[j]) u[p[j]] += delta
                else minv[j] -= delta
            }
            j0 = j1
        } while (j0 != -1)

        do {
            val j1 = way[j0]
            p[j0] = p[j1]
            j0 = j1
        } while (j0 != 0)
    }

    var totalCost = 0
    val assignment = mutableListOf<Pair<Int, Int>>()
    for (j in 1 until n) {
        totalCost += cost[p[j]][j]
        assignment.add(Pair(p[j], j))
    }

    return Pair(totalCost, assignment)
}

fun main() {
    val cost = arrayOf(
        intArrayOf(0, 2, 3, 4),
        intArrayOf(1, 0, 5, 6),
        intArrayOf(2, 4, 0, 2),
        intArrayOf(3, 5, 6, 0)
    )

    val (totalCost, assignment) = hungarianMethod(cost)
    println("Total Cost: $totalCost")
    println("Assignments: $assignment")
}

อธิบายโค้ด

ในโค้ดนี้ เรากำหนดค่า cost เป็น array ของค่าใช้จ่ายในการจับคู่ โดยใช้ฟังก์ชัน `hungarianMethod` เพื่อคำนวณค่าต่ำสุดที่สามารถทำได้และนำเสนอผลลัพธ์เป็นค่าใช้จ่ายรวมและจับคู่ที่ได้รับ

 

สิ้นบทความ

“การจับคู่ที่สมบูรณ์” ด้วย “วิธีฮังการี” เป็นเครื่องมือที่มีประสิทธิภาพ โดยเฉพาะในปัญหาการมอบหมายงานต่าง ๆ หากคุณสนใจที่จะศึกษาการเขียนโปรแกรมและอัลกอริธึมเหล่านี้เพิ่มเติม รับรองว่าคุณจะได้พบกับความรู้อีกมากมายที่ EPT (Expert-Programming-Tutor) ที่ทุ่มเทให้คุณได้เรียนรู้ ไม่สามารถหลีกเลี่ยงได้เลย! 🤓

การเรียนรู้โปรแกรมไม่เพียงแต่ช่วยให้คุณสนุกสนาน ยังเป็นการเพิ่มโอกาสในการตลาดและการประกอบอาชีพในอนาคต อย่าพลาดโอกาสในการเติบโตและค้นพบความรู้ใหม่ ๆ ที่ EPT!

 

 

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