Làm thế nào tìm con đường ngắn nhất?

Trong cuộc sống hằng ngày chúng ta thường gặp vấn đề sau đây: Cần tìm con đường ngắn nhất đi từ điểm A đến điểm E như ở hình vẽ. Trên hình vẽ các điểm cuối mỗi đoạn đường là một địa điểm, đoạn thẳng chỉ con đường nối giữa hai điểm, con số trên mỗi đoạn thẳng chỉ cự ly của đoạn đường.

Trước hết xin dẫn ra phương pháp thông thường. Xem xét tất cả các tuyến đường có thể đi, tính toán tổng các cự ly, từ đó chọn được tuyến đường ngắn nhất. Từ A đến E có 3.3.3.1 đoạn đường có thể đi, mỗi tuyến đi cần thực hiện ba lần phép cộng, cần phải thực hiện 81 phép cộng. Ngoài ra còn phải tiến hành 26 lần phép so sánh, cuối cùng sẽ tìm được tuyến đường ngắn nhất là A → B2 → C2 → D3 → E. Cự ly tương ứng bằng 15.

Ta dễ dàng nhận thấy thực hiện như phương pháp thông thường quả là đơn giản nhưng để thực hiện lại không dễ vì phải qua nhiều địa điểm, thực hiện quá nhiều phép tính.

Vậy liệu có phương pháp nào khác không?

Giả sử ta chọn được con đường ngắn nhất là A → B2 → C2 → D3 → E thì đoạn đường nhỏ trong đó đi từ hai điểm của tuyến đường cũng phải là ngắn nhất, ví dụ C2 → D3 → E cũng phải là con đường ngắn nhất từ C2 đến E. Nếu không, khi dùng phản chứng ta phải tìm được một tuyến đường khác ngắn hơn và điều đó trái với giả thiết. Tuyến đường ngắn nhất như mô tả ở trên, chúng ta có thể bắt đầu từ cuối tuyến đường truy dần từng bước ta sẽ tìm được tuyến đường ngắn nhất từ A đến E.

Bước thứ nhất: Tìm đoạn đường ngắn nhất từ D đến E.

Từ D1, D2, D3 đến E có các tuyến f(D1) = 5, f(D2) = 8, f(D3) = 1. f(xi) biểu diễn cự ly ngắn nhất từ xi đến E.

Bước thứ hai: Xét đoạn đường ngắn nhất từ C đến E.

Xuất phát từ C1 có khả năng chọn đến D1, D2 hoặc D3.

trong đó, d(C1, D1) biểu diễn khoảng cách từ C1 đến D1, dễ dàng tìm thấy khoảng cách ngắn nhất là theo tuyến C1 → D3→ E.

Tương tự xuất phát từ C2 ta có

Và tuyến ngắn nhất là C2→D3 → E. Tương tự

Từ C3 tuyến ngắn nhất là C3 → D3 →E với f(C3) = 6

Cũng với lí do tương tự, ta tìm thấy f(B1) = 12 cho đoạn đường con B1 → C2 → D3 → E

và f(B2) = 7 cho đoạn đường con B2 → C2 → D3 → E

f(B3) = 12 cho đoạn đường con B1 → C__1 (hoặc C2) → D3 → E

Xuất phát từ A ta có:

Dựa vào quá trình tính toán, ta thấy số lượng phép toán giảm đi rất nhiều: chỉ cần 3.3 + 3.3 + 3 = 21 phép cộng và 3.2 + 3.2 + 2 = 14 phép so sánh. Nếu số địa điểm càng lớn thì ưu điểm của phương pháp càng rõ rệt. Dùng phương pháp này không chỉ cho thấy tìm được đường từ A đến E ngắn nhất mà còn biết được cự ly từ điểm này đến điểm khác của tuyến đường. Trong toán học, người ta gọi đây là phương pháp “giải pháp theo quy tắc động thái”.

“Quy tắc động thái” là phương pháp cho phép giải quyết nhanh bài toán tối ưu, do nhà toán học Mỹ Bellman đưa ra năm 1959. Đây là bài toán “tối ưu hoá” đã được phát triển thành ngành toán học mới. Phương pháp quy tắc động thái được phát huy rộng rãi trong các ngành kĩ thuật công trình, quản lí kinh tế, trong sản xuất công nghiệp và kĩ thuật quân sự và ngày càng được coi trọng, thậm chí còn được dùng trong việc chọn phạm vi trong máy tính. Bởi vì nếu dùng phương pháp thông thường thì đến cả máy tính cũng khó thực hiện hết được các phép tính.

Tại sao sinh vật có thể bị tuyệt chủng?

Chim Đô Đô và chim bồ câu Bắc Mĩ là những sinh vật đã từng tồn tại trên Trái Đất với số lượng lớn và sớm đã trở thành di vật của lịch sử. Những loại động vật quý hiếm khác như hổ Đông Bắc, voi Châu Phi, hắc tinh tinh...

Vì sao cần chế biến sữa thành sữa chua?

Sữa là loại thực phẩm giàu chất dinh dưỡng, trong đó có đường (khoảng 4,6%), protein (khoảng 3,5%) và chất béo (khoảng 3,5%). Ngoài ra trong sữa còn...

Kiến trúc thành phố hoà hợp với con người và thiên nhiên như thế nào?

Các công trình hiện đại là nơi tiêu hao chủ yếu nguồn năng lượng thiên nhiên. Theo thống kê của Liên hợp quốc, nguồn năng lượng bị tiêu hao có liên...

Thực chất Heli có quan hệ gì với Mặt trời?

Điều này bắt đẩu từ một lẩn nhật thực toàn phẩn xảy ra vào ngày 18 tháng 8 năm 1868. Lúc đó, một nhà khoa học người Pháp tên là Saliđến An Độ để quan...

Làm thế nào để tạo thành thuốc từ vi khuẩn?

Trong thuốc hiện đại có một thành phần gọi là chất nhiễu. Nó không những có thể đề kháng nhiều loại độc tố bệnh, chữa được một số bệnh do độc tố bệnh...

Các kiến trúc cao tầng chống gió như thế nào?

Tục ngữ có câu "cây to gió lớn". Kiến trúc cao tầng giống như một cây cực kỳ cao to, ảnh hưởng của gió đối với nó là rất lớn, đối với kiến trúc cao 50...

Vì sao dùng vệ tinh có thể thăm dò tài nguyên Trái đất?

Vệ tinh dùng để thăm dò và nghiên cứu tài nguyên Trái Đất gọi là vệ tinh tài nguyên. Nó là một loại vệ tinh ứng dụng rất quan trọng.

Vì sao nói cây xanh là "máy tiêu âm" tự nhiên?

Có người ví cây xanh là máy tiêu âm tự nhiên, đó là vì cây xanh có tác dụng giảm thấp tiếng ồn. Nhiều thành phố Trung Quốc đang trong quá trình phát...

Để phát huy tác dụng chữa bệnh, thuốc có liên quan với thụ thể như thế nào?

Thuốc và chất độc sau khi vào cơ thể sẽ có tác động khác nhau. Thuốc phát huy tác dụng chữa bệnh, còn chất độc sản sinh phản ứng có hại đối với cơ...