JavaScript is required

Trong bài toán Hungary, nếu người ta yêu cầu cho thêm điểm ứ đọng, bạn cần phải làm gì:

A.

Gán cho công việc đó giá trị bằng 0 và giải bình thường

B.

Đổi dấu tất cả các phần tử trong bảng phân việc

C.

Không làm gì cả

D.

Không có đáp án nào đúng

Trả lời:

Đáp án đúng: D


Bài toán Hungary là một thuật toán tối ưu tổ hợp để giải bài toán gán (assignment problem). Khi có yêu cầu thêm điểm "ứ đọng", điều này có nghĩa là một công việc cụ thể không thể được thực hiện bởi bất kỳ ai. Để giải quyết tình huống này trong bài toán Hungary, ta gán cho công việc đó một giá trị chi phí rất lớn (thường là vô cùng lớn hoặc một số đủ lớn để đảm bảo rằng nó không được chọn trong quá trình tối ưu), hoặc trong trường hợp bài toán đang tìm min, ta có thể gán giá trị bằng 0 và giải như bình thường nếu bài toán đang tìm max. Trong các đáp án được đưa ra, đáp án A là phù hợp nhất, với hàm ý rằng ta gán một giá trị (có thể là một giá trị rất lớn nếu tìm min, hoặc 0 nếu tìm max) để không ai được chọn làm công việc đó.

Câu hỏi liên quan