Home / / giải thuật tìm đường đi ngắn nhất

Giải Thuật Tìm Đường Đi Ngắn Nhất

admin - 13/02/2023 38

Với chúng ta sinh viên siêng ngành technology thông tin, dĩ nhiên không kỳ lạ gì với việc tìm lối đi ngắn độc nhất (Shortest Path Problems) trong trang bị thị trọng số nữa. Ở nội dung bài viết lần này, bản thân sẽ làm 3 việc:

Giới thiệu việc tìm đường đi ngắn duy nhất và áp dụng của nó.Giải thích giải mã Dijkstra để giải quyết và xử lý bài toán trênViết giải mã Dijkstra bằng code Ruby .

Bạn đang xem: Giải thuật tìm đường đi ngắn nhất

1. Reviews bài toán tìm đường đi ngắn nhất

Mình sẽ đưa ra một lấy ví dụ cơ phiên bản về việc này.

Bài toán: cho 1 đồ thị trọng số gồm những nodes A,B,C,D,E,F và khoảng cách giữa các nodes tương xứng với những cạnh như hình dưới . Tìm đường đi ngắn duy nhất từ node B đến những node sót lại trong đồ dùng thị?

Sau khi giải bài bác toán, ta được công dụng như sau. Đường đi ngắn tuyệt nhất từ A đến 5 node còn lại:

Từ A -> B : A - B, tổng độ dài lối đi = 2Từ A -> C : A - C, tổng độ dài lối đi = 5Từ A -> D : A - D, tổng độ dài lối đi = 1Từ A -> E : A - D - E, tổng độ dài lối đi = 2Từ A -> F : A - D - E - F, tổng độ dài lối đi = 4

Để nói đến ứng dụng của bài toán giải việc này, nếu như bạn thay những node bằng những giao lộ, và các cạnh của chính nó là những tuyến đường, ta sẽ có một bài toán hết sức quen thuộc. Vấn đề tìm lối đi ngắn nhất đến một địa điểm trên bạn dạng đồ.

Ví dụ như hình sống trên, bằng phương pháp giải quyết bài toán này, các bạn sẽ tìm được trong suốt lộ trình ngắn nhất để đi từ vị trí của người sử dụng đến Mễ Trì Thượng.

Ngoài ra, ví như thay các node bằng những router mạng hoặc các host , họ có việc định tuyến phố đi của một khối hệ thống mạng - loại việc cơ bản mà các kỹ sư mạng cần biết đến:

Có khá nhiều giải thuật được chỉ dẫn để xử lý bài toán này : Dijkstra"s algorithm , Bellman–Ford algorithm, A* tìm kiếm algorithm, Floyd–Warshall algorithm, .....

Tuy nhiên ở bài viết này, bản thân sẽ phân tích và lý giải về lời giải Dijkstra và cách để viết nó bằng code Ruby.

2. Giải thích về giải thuật Dijkstra

Mô tả về lời giải Dijkstra:

Bước 1: chọn S = là tập các soure_node bao hàm current_node và passed_node . Với current_node là node đang rất được xét đến, passed_node là các node đã có xét.current_node đầu tiên sẽ là node đích của việc tìm lối đi ngắn nhất.Bước 2: Khởi tạo lời giải với current_node là node đích và cost(N) là quý hiếm của đường đi ngắn tuyệt nhất từ N mang đến node đích.Bước 3: Xét các node kề N cùng với current_node . điện thoại tư vấn d(current_node,N) là khoảng cách giữa node kề N với current_node . Với p = d(current_node,N) + cost (current_node). Nếu p thì cost(N) = p . Nếu như không thì cost(N) giữ nguyên giá trị .Bước 4: sau khoản thời gian xét hết các node kề N, ghi lại current_node thành passed_node .Bước 5: tìm kiếm current_node new với 2 điều kiện: không phải passed_node với cost(current_node) là nhỏ tuổi nhấtBước 6: ví như tập S = cất đủ những node của vật dụng thị thì giới hạn thuật toán. Còn nếu như không thì quay trở lại Bước 3 .

Để phân tích và lý giải về cách giải mã Dijkstra hoạt động, bản thân sẽ áp dụng đồ thị trọng số dưới đây để đi tìm đường đi ngắn độc nhất từ node C đến hầu hết node còn lại trong đồ dùng thị :

Trong quy trình thuật toán chạy, ta call cost(node) là khoảng phương pháp ngắn duy nhất từ từng node mang lại node C và khắc ghi nó trên hình (giá trị số greed color da trời) . Lúc thuật toán new bắt đầu, ta mang định lưu cost(C) = 0 , cost(A) = cost(B) = cost(D) = cost(E) = infinity.

Ta cũng khắc ghi current_node (node sẽ xét hiện tại tại) bằng một vết chấm đỏ bên trên hình.current_node trước tiên sẽ là node đích của câu hỏi - ở đây là C.

Xem thêm: Khách Sạn Vũng Tàu Giá Rẻ Đường Thùy Vân View Biển Tốt Nhất, Top 10 Khách Sạn Vũng Tàu Đường Thùy Vân Có View

Thuật toán ban đầu chạy bằng phương pháp 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ẽ ban đầu với node B trước và tiến hành 4 bước:

Đầu tiên ta kiếm được khoảng những từ current_node cho node B: d(C,B) = 7.Tính toán giá trị đường đi từ node đích -> current_node -> node B :p = d(C,B) + cost(current_node) = 0 + 7 = 7Nếu giá trị vừa tính p thì cost(B) = p, trái lại thì cost(B) giữ nguyên. ( ở đây 7 cần cost(B) = 7 )Đánh lốt cost(B) lên hình.

Tương tự với A và D, ta cũng tìm được cost(A) = 1 cùng 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ờ bọn họ sẽ chọn một current_node mới với 2 điều kiện:

current_node không thể là passed_node.cost(current_node) có giá trị nhỏ tuổi nhất.

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 liên tục giải thuật bằng phương pháp xét các node kề cùng với current_node với đk node kề ko được là passed_node . Như vậy tại đây ta chỉ được xét node B .

d(A,B) = 3, cost(A) = 1 .p = d(A,B) + cost(A) = 4p . Vậy cost(B) = 4Đánh vết cost(B) lên hình

Đánh vệt node A biến chuyển passed_node. Ta liên tục tìm current_node mới, lần này nó là node D cùng với cost(D) = 2:

Có 2 node kề với D là B cùng E.

Xét cùng với node B

d(D,B) = 5, cost(D) = 2 .p = d(D,B) + cost(D) = 7p > cost(B) ( 7 > 4 ) . Vậy cost(B) = 4Giữ nguyên cost(B)

Xét với node E

d(D,E) = 7, cost(D) = 2 .p = d(D,E) + cost(D) = 9p . Vậy cost(E) = 9Đánh vệt cost(E) lên hình.

Đánh vết node D đổi mới passed_node. Ta liên tiếp tìm current_node mới, lần này nó là node B cùng với cost(B) = 4 :

Chỉ còn 1node kề cùng với B là E.

Xét với node E

d(B,E) = 1, cost(B) = 4 .p = d(B,E) + cost(B) = 5p . Vậy cost(E) = 5Đánh dấu cost(E) lên hình.

Giờ chúng ta không còn node làm sao để kiểm tra nữa. Đánh vệt node E biến đổi passed_node và chấm dứt thuật toán.

Xem thêm: Kinh Nghiệm Đặt Khách Sạn Tam Đảo Giá Tốt Nhất Cùng Traveloka