MẸO TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN GOOGLE MAPS DÀNH CHO NGƯỜI DÙNG IPHONE, IPAD

     

Với các bạn sinh viên siêng ngành công nghệ thông tin, chắc hẳn không lạ gì với bài toán tìm đường đi ngắn nhất (Shortest Path Problems) trong thiết bị thị trọng số nữa. Ở nội dung bài viết lần này, mình sẽ làm cho 3 việc:

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

Bạn đang xem: Mẹo tìm đường đi ngắn nhất trên google maps dành cho người dùng iphone, ipad

1. Ra mắt bài toán tìm lối đi ngắn nhất

Mình sẽ giới thiệu một lấy ví dụ cơ bạn dạng về câu hỏi này.

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

*

Sau khi giải bài xích toán, ta được kết quả như sau. Đường đi ngắn tuyệt nhất từ A mang đế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 đường đi = 1Từ A -> E : A - D - E, tổng độ dài đường đi = 2Từ A -> F : A - D - E - F, tổng độ dài đường đi = 4

*

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

*

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

Ngoài ra, nếu như thay những node bằng những router mạng hoặc các host , bọn họ có bài toán định tuyến đường đi của một hệ thống mạng - loại câu hỏi cơ bạn dạng mà những kỹ sư mạng nên biết đến:

*

Có không ít giải thuật được chỉ dẫn để giải quyết bài toán này : Dijkstra"s algorithm , Bellman–Ford algorithm, A* tìm kiếm algorithm, Floyd–Warshall algorithm, .....

Tuy nhiên ở nội dung bài viết này, mình sẽ lý giải về lời giải Dijkstra và cách để viết nó bằng code Ruby.

2. Lý giải về lời giải Dijkstra

Mô tả về giải thuật Dijkstra:

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

Để phân tích và lý giải về cách lời giải 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 phần đông node sót lại trong đồ dùng thị :

*

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

*

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

Xem thêm: Vntrip: Đặt Phòng Khách Sạn Honey House Phú Nhuận, Honey House Hotel Ở Quận Phú Nhuận, Tp

Thuật toán bắt đầu chạy bằng phương pháp xét tất cả các node kề cùng 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à triển khai 4 bước:

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

*

Tương trường đoản cú với A và D, ta cũng tìm kiếm được cost(A) = 1 với cost(D) = 2 .

*

Sau lúc xét hết tất cả các node kề với current_node, ta chuyểncurrent_node thành passed_node - có nghĩa là node đã làm được xét rồi. Passed_node sẽ tiến hành đánh 1 dấu vết xanh trên hình.

*

Bây giờ họ sẽ chọn 1 current_node mới với 2 điều kiện:

current_node cần yếu là passed_node.cost(current_node) có mức giá trị nhỏ tuổi nhất.

Nếu xét bên trên hình, current_node tiếp theo sau sẽ là node A . Ta đánh dấu node A với cùng một dấu chấm đỏ.

*

Ta liên tiếp giải thuật bằng phương pháp 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 tại chỗ nà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 lốt node A đổi thay 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ề cùng với D là B cùng E.

Xét 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 cùng 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 biến chuyển passed_node. Ta thường xuyên tìm current_node mới, lần này nó là node B với cost(B) = 4 :

*

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

Xét cùng với node E

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

*

Giờ bọn họ không còn node như thế nào để check nữa. Đánh vết node E biến passed_node và chấm dứt thuật toán.

Xem thêm: Địa Chỉ Đồi Cỏ Hồng Đà Lạt, Địa Chỉ Đồi Hoa Cỏ Hồng Đà Lạt

*

Vậy ta có hiệu quả của thuật toán với lối đi ngắn duy nhất từ C đến những điểm còn sót lại là:

Từ C -> A: C - A, cost(A) = 1Từ C -> B: C - A - B, cost(B) = 4Từ C -> D: C - D, cost(D) = 2Từ C -> E: C - A - B - E, cost(E) = 5

3. Giải mã Diijkstra cùng với code Ruby

Mình đã giải thích rất rõ cách hoạt động vui chơi của giải thuật Dijkstra rồi. Cho nên việc triển khai nó trong code Ruby khá dễ dàng hiểu.