Đề bài:
Gara ôtô có hình dạng hình vuông 10x10 ô, mỗi ô có thể để được một ôtô. Gara có tường rào bao bọc xung quanh, chỉ để một cửa ra vào ở góc trên bên trái (ô A). Người chủ gara muốn sắp xếp ôtô thế nào để một chiếc xe bất kỳ có thể ra vào gara mà không bị chắn bởi các xe khác.
Trên hình là một phương án thích hợp với 54 chỗ để xe. Chắc chắn phương án này chưa phải là tối ưu vì còn quá nhiều chỗ trống. Hãy đề xuất một phương án mà bạn cho là tốt nhất.
A | X | X | X | X | X | X | X | X | X |
X | X | X | X | X | X | X | X | X | |
X | X | X | X | X | X | X | X | X | |
X | X | X | X | X | X | X | X | X | |
X | X | X | X | X | X | X | X | X | |
X | X | X | X | X | X | X | X | X |
Lời giải:
Xuất xứ bài toán là đề thi Olympic toán của Matxcơva. Trong đề cũng ghi rõ: hãy cố gắng tìm phương án càng được nhiều xe sẽ càng được nhiều điểm. Trong đáp án nêu ra một phương án với 60 xe và ghi rõ luôn là "cho đến nay, chúng tôi không biết là có phương án nào xếp được nhiều xe hơn hay không".
Vậy: "Liệu 60 xe có phải là phương tốt nhất hay chưa?", "Nếu có thì có thể chứng minh điều này bằng lý thuyết được không?". Tất nhiên là câu hỏi thứ hai khó hơn (và bao trùm) câu hỏi thứ nhất.
Chúng tôi có một số lý luận cơ bản sau (ta quy ước ô đen là ô có xe, ô trắng là ô trống):
- Một ô đen phải kề với ít nhất một ô trắng.
- Một ô trắng chỉ có thể kề với nhiều nhất 3 ô đen.
Từ lý luận này, nếu gọi a là số ô trắng và b là số ô đen thì b ≤ 3a và a + b = 100.
Suy ra 4a ≥ 100, a ≥ 25 và b ≤ 75.
Lý luận này có thể làm mạnh hơn (điều này cần xét chi tiết hơn một chút) với mệnh đề sau: "Nếu ta có một cách xếp mà có ô trắng kề 3 ô đen thì ta có thể điều chỉnh để ô trắng chỉ kề 2 ô đen nhưng không làm thay đổi số ô đen".
Bằng cách này, ta suy ra b ≤ 2a, 3a ≥ 100 và a ≥ 34, suy ra b ≤ 66.
Xét lý thuyết chỉ có thể được đến đó.
Để giải quyết câu hỏi 1, cũng là điều mà chúng ta cùng quan tâm, chúng tôi quay sang tìm sự trợ giúp của tin học. Vì kích thước 10x10 là khá nhỏ nên chúng tôi dùng phương pháp khá thủ công là duyệt từng bước. Cụ thể ý tưởng như sau.
- Khảo sát lần lượt từng ô, thử gán ô đen trước, thử gán ô trắng sau.
- Điều kiện chặn đệ quy là ước lượng số ô đen tối đa ở phương án hiện tại và so sánh với đáp án tốt nhất hiện có:
* Ước lượng bằng công thức: * thresh + số ô đen hiện có>
* thresh có giá trị thuộc (0, 1].
* Ví dụ ta đang xét ô (2, 2) trên bảng 4x4 và tình trạng bảng hiện tại như sau:
0 1 0 0
0 1 * *
Khi đó, ta đã gán 2 ô đen, nên số ô đen tối đa có thể gán là số ô đánh dấu * nhân với một hệ số. Giá trị tối đa của hệ số là 1, nghĩa là toàn bộ các ô * sẽ đều được gán là 1.
* Hệ số thresh này là tỷ lệ tối đa của số ô đen so với số ô cần xử lý, hiện tại giá trị mặc định được đặt là 0.75, nghĩa là cứ 4 ô thì gán được tối đa 3 ô đen. Thresh càng nhỏ, đáp án càng thiếu chính xác nhưng tốc độ càng nhanh, và ngược lại. Thresh = 1 đảm bảo có kết quả tối ưu.
Chúng tôi đã chạy chương trình và cho ra kết quả: con số tối ưu đúng là 60. Dưới đây là kết quả do chương trình chạy ra.
Đây thực sự là một bài toán rất thú vị, tuy nhiên lời giải của nó cũng như các hướng mở rộng (với kích thước lớn chương trình của chúng tôi sẽ chạy chậm và đến một mức nào đó không xử lý được do bùng nổ trường hợp) nằm ngoài khuôn khổ của một chuyên mục mang tính giải trí và giáo dục nhẹ nhàng.
Bạn đọc nào quan tâm chi tiết hơn (và muốn xem source code của chương trình) xin liên hệ với chúng tôi qua email: trannamdung@yahoo.com.
Trần Nam Dũng
ĐH Khoa học Tự nhiên, ĐH Quốc gia TP HCM