Phân công tối ưu và thuật toán Hungary | Prasanna Sethuraman | Tháng 7, 2024

Bài viết này cung cấp ví dụ từng bước về cách thuật toán Hungary giải quyết bài toán gán tối ưu trên đồ thị

Lý do tôi viết bài viết này là vì tôi đã vật lộn trong vài ngày để hiểu cách Thuật toán Hungary hoạt động trên đồ thị. Phiên bản ma trận dễ hiểu hơn nhiều, nhưng không cung cấp được cái nhìn sâu sắc cần thiết. Tất cả thông tin tuyệt vời mà tôi tìm thấy trên net đều không cung cấp cho tôi sự rõ ràng cần thiết để hiểu trực quan tại sao thuật toán lại làm như vậy.

Tôi cũng không dễ dàng để dịch các mô tả thuật toán thành một ví dụ thực tế. Mặc dù các công cụ LLM khác nhau mà chúng ta có ngày nay đã giúp diễn đạt lại mô tả thuật toán theo nhiều cách khác nhau, nhưng tất cả đều thất bại thảm hại khi tôi yêu cầu chúng tạo ra một ví dụ từng bước thực tế. Vì vậy, tôi đã kiên trì tạo ra một ví dụ về thuật toán Hungary thực hiện phép thuật của nó trên một đồ thị. Tôi trình bày ví dụ từng bước này ở đây và trực giác mà tôi có được từ bài tập này, với hy vọng rằng nó sẽ giúp những người khác đang cố gắng học thuật toán tuyệt vời này để giải quyết vấn đề gán tối ưu.

Bài toán gán tối ưu là tìm sự khớp một-một từ một tập hợp các nút tới một tập hợp các nút khác, trong đó cạnh giữa mỗi cặp nút có chi phí liên quan đến nó và sự khớp được tạo ra phải đảm bảo tổng chi phí là nhỏ nhất.

Vấn đề này rất phổ biến. Có thể là phân công một nhóm người cho một nhóm công việc, mỗi người yêu cầu một mức giá cụ thể cho một công việc cụ thể, và sau đó vấn đề là phân công mọi người cho các công việc sao cho tổng chi phí được giảm thiểu. Có thể là phân công một nhóm taxi có sẵn cho nhóm người đang tìm taxi, mỗi taxi cần một khoảng thời gian cụ thể để đến được một người cụ thể. Thuật toán Hungary được sử dụng để giải quyết vấn đề này mỗi khi chúng ta đặt xe Uber hoặc Ola.

Vấn đề giao nhiệm vụ được thể hiện tốt nhất dưới dạng hai bên đồ thị, là đồ thị có hai tập hợp nút riêng biệt và các cạnh không bao giờ kết nối các nút từ cùng một tập hợp. Chúng ta lấy ví dụ về ghép taxi và đồ thị hai phần ở đây cho thấy các kết nối có thể có giữa các nút. Trọng số cạnh cho biết thời gian (tính bằng phút) để taxi cụ thể đến được một người cụ thể. Nếu tất cả các nút từ một tập hợp được kết nối với tất cả các nút từ tập hợp khác, đồ thị được gọi là hoàn thành.

Trong ví dụ này, chúng ta cần ánh xạ 4 người đến 4 xe taxi. Chúng ta có thể dùng phương pháp brute drive để giải quyết:

• Đối với người thứ nhất, có bốn nhiệm vụ taxi có thể thực hiện và chúng ta có thể chọn bất kỳ nhiệm vụ nào trong số đó
• Đối với người thứ hai, còn lại ba chiếc taxi, và chúng tôi chọn một trong ba chiếc
• Đối với người thứ ba, chúng tôi chọn một trong hai chiếc taxi còn lại
• Đối với người cuối cùng, chúng tôi chọn chiếc taxi còn lại

Vì vậy, tổng số phép gán có thể là 4 x 3 x 2 x 1, tức là 4 giai thừa. Sau đó, chúng ta tính tổng chi phí cho tất cả 4 phép gán này! và chọn phép gán có chi phí thấp nhất. Đối với các bài toán gán có kích thước nhỏ hơn, phương pháp brute drive vẫn có thể khả thi. Nhưng vì Nsố lượng người/taxi tăng lên, N! trở nên khá lớn.

Cách tiếp cận khác là thuật toán tham lam. Bạn chọn một người, chỉ định taxi có chi phí thấp nhất cho người đó, sau đó chọn người tiếp theo, chỉ định một trong những chiếc taxi còn lại có chi phí thấp nhất, v.v. Trong ví dụ này, việc chỉ định chi phí thấp nhất là không thể đối với người cuối cùng vì chiếc taxi có thể đến chỗ anh ta trong thời gian ngắn nhất đã được chỉ định cho một người khác rồi. Vì vậy, thuật toán chọn chiếc taxi khả dụng tiếp theo với chi phí thấp nhất. Do đó, người cuối cùng phải chịu sự tham lam của mọi người khác. Giải pháp cho thuật toán tham lam có thể được thấy trong biểu đồ tại đây. Không có gì đảm bảo rằng cách tiếp cận tham lam này sẽ dẫn đến một sự chỉ định tối ưu, mặc dù trong ví dụ này, nó dẫn đến việc đạt được chi phí tối thiểu là 36.

Thuật toán Hungary cung cấp một cách hiệu quả để tìm ra giải pháp tối ưu. Trước tiên, chúng ta sẽ bắt đầu với thuật toán ma trận. Chúng ta có thể biểu diễn đồ thị dưới dạng ma trận kề, trong đó trọng số của mỗi cạnh là một mục của ma trận. Đồ thị và ma trận kề của nó có thể được xem tại đây.

Sau đây là các bước của thuật toán Hungary hoạt động trên ma trận kề:

1. Đối với mỗi hàng trong ma trận kề, tìm và trừ phần tử nhỏ nhất khỏi tất cả các phần tử của hàng đó
2. Đối với mỗi cột trong ma trận kề, tìm và trừ mục nhập tối thiểu khỏi tất cả các mục nhập của cột đó
3. Phủ tất cả các số 0 trong ma trận bằng số dòng ít nhất
   a. Đếm số số không ở mỗi hàng và mỗi cột
   b. Vẽ các đường thẳng trên hàng/cột có nhiều số 0 nhất trước, sau đó đến nhiều thứ hai, v.v.
   c. Nếu số dòng cần thiết bao phủ toàn bộ số không ít hơn số hoặc hàng/cột của ma trận, hãy tiếp tục bước 4, nếu không, hãy chuyển sang bước 5
4. Tìm mục nhỏ nhất không được bao phủ bởi đường thẳng và trừ mục đó khỏi tất cả các mục không được bao phủ trong khi cộng nó vào tất cả các mục được bao phủ hai lần (đường ngang và đường dọc), chuyển sang bước 3
5. Có thể tạo ra phép gán tối ưu bằng cách bắt đầu với hàng/cột chỉ có một số không

Hai bước đầu tiên thì dễ. Bước thứ ba yêu cầu gạch bỏ các hàng hoặc cột theo thứ tự số lượng số không mà chúng có, từ cao nhất đến thấp nhất. Nếu số lượng hàng và cột bị gạch bỏ không bằng số lượng nút cần khớp, chúng ta cần tạo thêm số không — điều này được thực hiện ở bước thứ tư. Lặp lại bước 3 và bước 4 cho đến khi đủ số lượng hàng và cột bị gạch bỏ. Sau đó, chúng ta có đủ số không trong ma trận để khớp tối ưu.

Các bước của thuật toán Hungary cho ví dụ ghép taxi này được hiển thị trong ảnh GIF động này.

Đối với những ai thấy khó hiểu về GIF, đây là hình ảnh hiển thị các bước.

Thuật toán kết thúc khi số hàng/cột đã bị gạch bỏ bằng số nút cần khớp. Bước cuối cùng sau đó là tìm phép gán và điều này dễ dàng thực hiện bằng cách trước tiên gán cạnh tương ứng với một trong các mục nhập bằng không, trong ví dụ này, có thể là (P1, T2) bằng cách chọn số không đầu tiên trong hàng đầu tiên. Do đó, chúng ta không thể gán T2 cho bất kỳ ai khác, do đó, số không thứ hai trong cột T2 có thể bị xóa. Số không duy nhất còn lại trong hàng P4 cho biết nó phải được gán cho T1, do đó, phép gán tiếp theo là (P4, T1). Bây giờ, số không thứ hai trong cột T1 có thể bị xóa và sau đó hàng P2 chỉ có một số không. Phép gán thứ ba sau đó là (P2, T3). Do đó, phép gán cuối cùng là (P3, T4). Người đọc có thể tính tổng chi phí bằng cách cộng tất cả các trọng số cạnh tương ứng với các phép gán này và kết quả sẽ là 36.

Quá trình gán này trực quan hơn nhiều nếu chúng ta xem hình ảnh động GIF, trong đó chúng ta có một đồ thị con kết nối tất cả các nút và chúng ta có thể tạo một đường dẫn xen kẽ trong đó các cạnh xen kẽ giữa khớp (màu xanh lá cây) và không khớp (màu đỏ).