Làm thế nào tìm con đường ngắn nhất?
Trong cuộc sống hằng ngày, ta thường gặp bài toán tìm con đường ngắn nhất từ điểm A đến điểm E như hình vẽ. Mỗi điểm cuối của đoạn đường là một địa điểm, mỗi đoạn thẳng biểu thị một con đường nối giữa hai điểm, còn con số trên đoạn thẳng là độ dài của đoạn đường đó.
Cách thông thường là liệt kê tất cả tuyến đường có thể đi, tính tổng độ dài của từng tuyến rồi chọn tuyến ngắn nhất. Từ A đến E có 3 × 3 × 3 × 1 tuyến đường. Mỗi tuyến cần thực hiện ba phép cộng, tức phải làm 81 phép cộng, rồi thêm 26 lần so sánh mới tìm được đường ngắn nhất: A → B2 → C2 → D3 → E, với tổng độ dài bằng 15.
Phương pháp này đơn giản về ý tưởng nhưng không dễ thực hiện khi số địa điểm nhiều, vì phép tính sẽ tăng lên rất nhanh. Vậy có cách nào hiệu quả hơn không?
Giả sử ta đã biết đường ngắn nhất là A → B2 → C2 → D3 → E, thì mọi đoạn con trong tuyến ấy cũng phải là ngắn nhất. Ví dụ, đoạn C2 → D3 → E phải là đường ngắn nhất từ C2 đến E; nếu không, ta thay bằng đoạn ngắn hơn sẽ có cả tuyến ngắn hơn, trái với giả thiết ban đầu.
Vì thế, có thể bắt đầu từ cuối tuyến đường rồi truy ngược từng bước. Bước thứ nhất, tìm đường ngắn nhất từ các điểm D đến E: f(D1) = 5, f(D2) = 8, f(D3) = 1, trong đó f(xi) biểu thị khoảng cách ngắn nhất từ xi đến E.
Bước thứ hai, xét đường ngắn nhất từ các điểm C đến E. Từ C1 có thể đi đến D1, D2 hoặc D3; sau khi cộng khoảng cách từ C1 đến từng điểm D với f(D), ta chọn được tuyến ngắn nhất là C1 → D3 → E. Làm tương tự, ta có tuyến ngắn nhất từ C2 là C2 → D3 → E, từ C3 là C3 → D3 → E với f(C3) = 6.
Tiếp tục tính ngược, ta tìm được f(B1) = 12 cho tuyến B1 → C2 → D3 → E, f(B2) = 7 cho tuyến B2 → C2 → D3 → E, và f(B3) = 12 cho một tuyến tương ứng đi qua C1 hoặc C2 rồi đến D3 → E.
Khi xuất phát từ A, chỉ cần so sánh các lựa chọn đi qua B1, B2, B3 là tìm được đường ngắn nhất. Quá trình này chỉ cần 21 phép cộng và 14 phép so sánh, ít hơn rất nhiều so với cách liệt kê toàn bộ.
Trong toán học, phương pháp này gọi là “quy hoạch động”. Đây là phương pháp giải nhanh các bài toán tối ưu do nhà toán học Mỹ Bellman đưa ra năm 1959. Ngày nay, nó được dùng rộng rãi trong kỹ thuật công trình, quản lý kinh tế, sản xuất công nghiệp, kỹ thuật quân sự và cả trong lựa chọn phạm vi tính toán của máy tính.
