The Perfect Matching - The Hungarian Method

 

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

 

Hungarian Method คืออะไร?

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

 

ปัญหาที่เกี่ยวข้อง

มาลองดูการใช้ Hungarian Method ในการแก้ปัญหาในชีวิตจริงกันบ้าง ตัวอย่างเช่น สมมติว่าเรามีคนงาน 4 คนและงาน 4 งาน โดยมีค่าใช้จ่ายในการทำงานที่แตกต่างกันไป ดังนี้:

| | งาน 1 | งาน 2 | งาน 3 | งาน 4 |

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

| คน 1 | 9 | 2 | 7 | 8 |

| คน 2 | 6 | 4 | 3 | 7 |

| คน 3 | 5 | 8 | 1 | 8 |

| คน 4 | 7 | 6 | 9 | 4 |

เราต้องการหาว่าคนงานคนไหนทำงานไหนจึงจะใช้ค่าใช้จ่ายรวมต่ำที่สุด

 

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

โค้ดตัวอย่างด้านล่างนี้จะแสดงถึงการประยุกต์ใช้อัลกอริธึม Hungarian Method ในภาษา Dart:

 class Hungarian {
  List<List<int>> _costMatrix;

  Hungarian(this._costMatrix);

  void solve() {
    int n = _costMatrix.length;
    List<int> u = List.filled(n, 0);
    List<int> v = List.filled(n, 0);
    List<int> p = List.filled(n, -1);
    List<int> way = List.filled(n, -1);

    for (int i = 0; i < n; i++) {
      List<int> minV = List.filled(n, 1 << 30);
      List<bool> used = List.filled(n, false);
      int j0 = 0;
      p[0] = i;
      int j1;

      while (true) {
        used[j0] = true;
        int i0 = p[j0], delta = 1 << 30, j1;

        for (int j = 1; j < n; j++) {
          if (used[j]) continue;
          int cur = _costMatrix[i0][j] - u[i0] - v[j];
          if (cur < minV[j]) {
            minV[j] = cur;
            way[j] = j0;
          }
          if (minV[j] < delta) {
            delta = minV[j];
            j1 = j;
          }
        }

        for (int j = 0; j < n; j++) {
          if (used[j]) {
            u[p[j]] += delta;
            v[j] -= delta;
          } else {
            minV[j] -= delta;
          }
        }

        j0 = j1;
        if (p[j0] == -1) break;
      }

      while (j0 != -1) {
        j1 = way[j0];
        p[j0] = p[j1];
        j0 = j1;
      }
    }

    for (int j = 1; j < n; j++) {
      print("คนงาน ${p[j]} ทำงาน $j กับค่าใช้จ่าย ${_costMatrix[p[j]][j]}");
    }
  }
}

void main() {
  var costMatrix = [
    [9, 2, 7, 8],
    [6, 4, 3, 7],
    [5, 8, 1, 8],
    [7, 6, 9, 4]
  ];

  var hungarian = Hungarian(costMatrix);
  hungarian.solve();
}

การวิเคราะห์ Complexity

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

 

ข้อดีของ Hungarian Method

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

 

ข้อเสียของ Hungarian Method

1. ไม่เหมาะสำหรับกราฟขนาดใหญ่: อัลกอริธึมนี้มีความซับซ้อนในกรณีที่มีกราฟขนาดใหญ่ เพราะ Complexity O(n^3) 2. ใช้เวลาในการจัดการข้อมูล: การเตรียมโครงสร้างข้อมูลที่จำเป็นก่อนใช้ค่อนข้างซับซ้อน

 

สรุป

อัลกอริธึม Hungarian Method เป็นเครื่องมือที่มีประสิทธิภาพในการจับคู่ข้อมูลในหลายขอบเขต ไม่ว่าจะเป็นการจัดคนให้ทำงานที่เหมาะสมที่สุด หรืองานที่มีต้นทุนที่แตกต่างกัน แนะนำให้ผู้ที่สนใจเรียนรู้เกี่ยวกับอัลกอริธึมนี้เข้ามาศึกษาเพิ่มเติมได้ที่ EPT (Expert-Programming-Tutor) ที่มีหลักสูตรการเรียนการสอนที่ครอบคลุมและการสอนที่น่าสนใจ มาร่วมเรียนรู้กับเราที่ EPT เพื่อพัฒนาทักษะการเขียนโปรแกรมของคุณ!

 

 

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