Thuật toán BFS và ƯCLN (GCD) trong bài toán Đong Nước

Khái niệm

Bài toán đong nước: hai bình dung tích A và B (lít), không vạch chia; chỉ được đổ đầy, đổ cạn, hoặc rót từ bình này sang bình kia tới khi đầy/cạn. Hỏi làm sao đo được đúng T lít.

Điều kiện có lời giải: T phải là bội của ƯCLN(A, B) và T ≤ max(A, B). Thuật giải dùng BFS trên các trạng thái (lượng nước của hai bình) để tìm chuỗi thao tác ngắn nhất, tránh lặp trạng thái.

Ví dụ

Hai bình 5 lít và 3 lít, cần đo 4 lít: ƯCLN(5, 3) = 1 nên đo được. Một chuỗi: đổ đầy 5 → rót sang 3 (còn 2) → đổ cạn 3 → rót 2 sang 3 → đổ đầy 5 → rót sang 3 (đang có 2, chỉ nhận thêm 1) → bình 5 còn đúng 4 lít.

BFS cho chuỗi thao tác ngắn nhất và loại bỏ các trạng thái đã gặp để không đi vòng.

Minh hoạ động