Ứng dụng của bài toán tìm đường đi ngắn nhất năm 2024
Với các bạn sinh viên chuyên ngành công nghệ thông tin, chắc không lạ gì với bài toán tìm đường đi ngắn nhất (Shortest Path Problems) trong đồ thị trọng số nữa. Ở bài viết lần này, mình sẽ làm 3 việc: Show
1. Giới thiệu bài toán tìm đường đi ngắn nhấtMình sẽ đưa ra một ví dụ cơ bản về bài toán này. Bài toán: Cho một đồ thị trọng số gồm các Sau khi giải bài toán, ta được kết quả như sau. Đường đi ngắn nhất từ A đến 5 node còn lại:
Để nói về ứng dụng của việc giải bài toán này, nếu bạn thay các Ví dụ như hình ở trên, bằng cách giải quyết bài toán này, bạn sẽ tìm được lộ trình ngắn nhất để đi từ vị trí của bạn đến Mễ Trì Thượng. Ngoài ra, nếu thay các node bằng các router mạng hoặc các host , chúng ta có bài toán định tuyến đường đi của một hệ thống mạng - loại bài toán cơ bản mà các kỹ sư mạng cần phải biết đến: Có khá nhiều giải thuật được đưa ra để giải quyết bài toán này : Dijkstra's algorithm , Bellman–Ford algorithm, A* search algorithm, Floyd–Warshall algorithm, ..... Tuy nhiên ở bài viết này, mình sẽ giải thích về giải thuật Dijkstra và cách để viết nó bằng code Ruby. 2. Giải thích về giải thuật DijkstraMô tả về giải thuật Dijkstra:
Để giải thích về cách giải thuật Dijkstra hoạt động, mình sẽ sử dụng đồ thị trọng số dưới đây để đi tìm đường đi ngắn nhất từ node C đến mọi node còn lại trong đồ thị : Trong quá trình thuật toán chạy, ta gọi
1 là khoảng cách ngắn nhất từ mỗi node đến node C và đánh dấu nó trên hình (giá trị số màu xanh da trời) . Khi thuật toán mới bắt đầu, ta mặc định lưu
2 , cost(A) = cost(B) = cost(D) = cost(E) = infinity. Ta cũng đánh dấu current_node (node đang xét hiện tại) bằng một dấu chấm đỏ trên hình. current_node đầu tiên sẽ là node đích của bài toán - ở đây là C. Thuật toán bắt đầu chạy bằng cách xét tất cả các node kề với current_node (các node được nối trực tiếp với current_node ) , ở đây là A, B và D. Ta sẽ bắt đầu với node B trước và thực hiện 4 bước:
Tương tự với A và D, ta cũng tìm được cost(A) = 1 và cost(D) = 2 . Sau khi xét hết tất cả các node kề với current_node, ta chuyểncurrent_node thành passed_node - tức là node đã được xét rồi. passed_node sẽ được đánh 1 dấu tích xanh trên hình. Bây giờ chúng ta sẽ chọn 1 current_node mới với 2 điều kiện:
Nếu xét trên hình, current_node tiếp theo sẽ là node A . Ta đánh dấu node A với 1 dấu chấm đỏ. Ta tiếp tục giải thuật bằng cách xét các node kề với current_node với điều kiện node kề không được là passed_node . Như vậy ở đây ta chỉ được xét node B .
Đánh dấu node A trở thành passed_node. Ta tiếp tục tìm current_node mới, lần này nó là node D với cost(D) = 2: Có 2 node kề với D là B và E. Xét với
4
Xét với `node`0
Đánh dấu node D trở thành passed_node. Ta tiếp tục tìm current_node mới, lần này nó là node B với `nodes`4 : Chỉ còn 1node kề với B là E. Xét với `node`0
Giờ chúng ta không còn node nào để check nữa. Đánh dấu node E trở thành passed_node và kết thúc thuật toán. Vậy ta có kết quả của thuật toán với đường đi ngắn nhất từ C đến các điểm còn lại là:
3. Giải thuật Diijkstra với code RubyMình đã giải thích rất rõ cách hoạt động của giải thuật Dijkstra rồi. Nên việc triển khai nó trong code Ruby khá dễ hiểu. |