Giải bài toán điều tiết giao thông

Giải bài toán “Điều tiết giao thông”


Trên một đoàn đường giao thông miền núi: đường hẹp, ô tô chỉ đi được 1 chiều, nên người ta làm “Ô tránh nạn” cũng là để xe tránh nhau. Nhưng có tình huống 2 đoàn xe đi ngược chiều nhau đúng chỗ có “Ô tránh nạn” như sau:


Hãy tìm cách “Điều tiết” để di chuyển toàn bộ số xe ở bên trái sang phải và toàn bộ số xe bên phải sang trái ( vẫn giữ đúng thứ tự các xe từ trái qua phải đúng theo Đoàn) . Biết rằng “Ô tránh nạn” ở giữa có thể chứa tối đa mỗi bên 1 xe và 1 xe chỉ có thể đi được khi ở luồng giữa không có xe. Các xe có kích thước như nhau.

Bài giải : (Điều tiết theo các bước qua các sơ đồ sau)
* Bước 1










*Bước 2



*Bước 3




*Bước 4




*Bước 5








*Bước 6



*Bước 7




*Bước 8 Thông xe !




_______________________________________________________________
Nguồn ý tưởng ( đầu bài ) WWW trí thong minh