đặt vấn đề tìm đường đi cơ bản ngắn nhất. Vấn đề đó là một vấn đề hết sức phức tạp mà ta sẽ không bàn tới ở đây. Dưới đây ta sẽ xét một số thuật toán tìm đường đi ngắn nhất từ đỉnh S tới đỉnh F trên đơn đồ thị có hướng G = (V, E) có n đỉnh và m cung. Trong trường hợp đơn đồ thị vô hướng với trọng số không âm, bài toán tìm đường đi ngắn nhất có thể dẫn về bài toán trên đồ thị có hướng bằng cách thay mỗi cạnh của nó bằng hai cung có hướng ngược chiều nhau.
Lưu ý rằng các thuật toán dưới đây sẽ luôn luôn tìm được đường đi ngắn nhất là đường đi cơ bản. Các thuật toán quan trọng nhất giải quyết bài toán này là: 2. Thuật toán Dijkstra Thuật toán Dijkstra, được đặt tên của nhà khoa học máy tính người Hà Lan Edsger Dijkstra vào năm 1956, là một thuật toán giải tốt nhất để quyết bài 17 toán đường đi ngắn nhất nguồn đơn trong một đồ thị có hướng không có cạnh mang trọng số âm. Thuật toán thường được sử dụng trong định tuyến với một chương trình con trong các thuật toán đồ thị hay trong công nghệ Hệ thống định vị toàn cầu.
Dijkstra đã nghĩ về bài toán đường đi ngắn nhất khi làm việc tại Trung tâm Toán học ở Amsterdam năm 1956 với tư cách là một lập trình viên để chứng minh khả năng của một máy tính mới có tên ARMAC. Mục tiêu của ông là chọn cả một bài toán và giải pháp (sẽ được tạo bởi máy tính) mà những người không thuần tính toán vẫn có thể hiểu được. Ông đã thiết kế thuật toán đường đi ngắn nhất và sau đó triển khai nó cho ARMAC bằng bản đồ giao thông được đơn giản hóa một chút của 64 thành phố ở Hà Lan. Một năm sau, ông gặp một vấn đề khác từ các kỹ sư phần cứng làm việc trên máy tính tiếp theo của học viện: giảm thiểu lượng dây cần thiết để kết nối các chân trên bảng điều khiển phía sau của máy.
Như một giải pháp, ông đã phát hiện lại thuật toán Prim (được biết đến trước đó với Jarník, và cũng được Prim khám phá lại). Dijkstra đã xuất bản thuật toán vào năm 1959, 2 năm sau Prim và 29 năm sau Jarník. Ví dụ: Chúng ta dùng các đỉnh của đồ thị để mô phỏng các thành phố trong một vùng và các cạnh là đường nối giữa chúng. Khi đó trọng số các cạnh có thể xem như độ dài của các con đường.
Chúng ta cần vận chuyển từ thành phố S đến thành phố T. Thuật toán Dijkstra sẽ giúp chỉ ra đường đi ngắn nhất chúng ta có thể đi. Giã mã giải thuật Dijkstra như sau: function Dijkstra(Graph, source): create vertex set Q for each vertex v in Graph: dist[v] ← INFINITY prev[v] ← UNDEFINED add v to Q dist[source] ← 0 while Q is not empty: u ← vertex in Q with min dist[u] remove u from Q 18 for each neighbor v of u: alt ← dist[u] + length(u, v) if alt < dist[v]: dist[v] ← alt prev[v] ← u return dist[], prev[] Thời gian chạy thuật toán hay còn gọi là độ phức tạp của giải thuật Dijkstra bình thường là O(n2+m)[2]. Để cải thiệp thời gian chạy ta có thể sử dụng kết hợp với cấu trúc Heap vào trong giải thuật Dijkstra, khi đó độ phức tạp sẽ là O((m+n)log(n)), nếu kết hợp với Fibonacci Heap thì độ phức tạp giảm xuống còn O(m+nlog n).
Thuật toán Bellman-Ford thuật toán Bellman-Ford là một thuật toán mà tính con đường ngắn nhất từ một nguồn duy nhất đỉnh đến tất cả các đỉnh khác trong một đồ thị có trọng số. Nó chậm hơn thuật toán của Dijkstra cho cùng một đồ thị, nhưng linh hoạt hơn, vì nó có khả năng xử lý các đồ thị trong đó một số trọng số cạnh là số âm. Thuật toán này lần đầu tiên được đề xuất bởi Alfonso Shimbel, nhưng thay vào đó được đặt theo tên của Richard Bellman và Lester Ford Jr. , người đã xuất bản nó vào năm 1958 và 1956 , tương ứng Edward F.
Moore cũng đã xuất bản thuật toán tương tự vào năm 1957 và vì lý do này, đôi khi nó còn được gọi là thuật toán Bellman-Ford-Moore. Giả mã của giải thuật như sau: function BellmanFord(list vertices, list edges, vertex source) is ::distance[], predecessor[] // This implementation takes in a graph, represented as // lists of vertices and edges, and fills two arrays // (distance and predecessor) about the shortest path // from the source to each vertex // Step 1: initialize graph for each vertex v in vertices do distance[v] := inf // Initialize the distance to all vertices to infinity predecessor[v] := null // And having a null predecessor 19 distance[source] := 0 // The distance from the source to itself is, of course, zero // Step 2: relax edges repeatedly for i from 1 to size(vertices)−1 do //just |V|−1 repetitions; i is never referenced for each edge (u, v) with weight w in edges do if distance[u] + w < distance[v] then distance[v] := distance[u] + w predecessor[v] := u // Step 3: check for negative-weight cycles for each edge (u, v) with weight w in edges do if distance[u] + w < distance[v] then error "Graph contains a negative-weight cycle" return distance[], predecessor[] Độ phức tạp của thuật toán Bellman Ford là O(n*m), trong đó n là số đỉnh và m là số cung của đồ thị. Thuật toán Floyd-Warshall Trong khoa học máy tính, thuật toán Floyd-Warshall là một thuật toán cho việc tìm kiếm đường đi ngắn nhất trong một đồ thị có trọng với trọng số cạnh dương hay âm đều được. Một lần thực hiện thuật toán sẽ tìm ra độ dài (tổng trọng số) của các đường đi ngắn nhất giữa tất cả các cặp đỉnh.
Mặc dù nó không trả về chi tiết của các đường dẫn, nhưng có thể xây dựng lại các đường dẫn với các sửa đổi đơn giản cho thuật toán. Thuật toán Floyd-Warshall là một ví dụ về lập trình động và được xuất bản dưới dạng hiện được công nhận bởi Robert Floyd vào năm 1962. Tuy nhiên, về cơ bản nó giống như các thuật toán được Bernard Roy xuất bản năm 1959 và cả bởi Stephen Warshall vào năm 1962 vì đã tìm thấy sự đóng cửa quá độ của đồ thị và có liên quan chặt chẽ với thuật toán của Kleene (xuất bản năm 1956) để chuyển đổi một máy tự động hữu hạn xác định thành biểu thức chính quy. Công thức hiện đại của thuật toán như ba vòng lặp lồng nhau được mô tả lần đầu tiên bởi Peter Ingerman, cũng vào năm 1962.
20 * Thuật toán: Thuật toán Floyd-Warshall so sánh tất cả các đường dẫn có thể thông qua biểu đồ giữa mỗi cặp đỉnh. Hãy xem xét một biểu đồ G với các đỉnh V đánh số từ 1 đến N. Xem xét thêm một chức năng shortestPath(i,j,k) trả về con đường ngắn nhất có thể từ i đến j chỉ sử dụng các đỉnh từ tập hợp {1,2,…,k} như các điểm trung gian trên đường đi. Bây giờ, với chức năng này, mục tiêu là tìm ra con đường ngắn nhất từ mỗi i cho mỗi j sử dụng bất kỳ đỉnh trong {1,2,…,N}[3].
Đối với mỗi cặp đỉnh này, shortestPath(i,j,k) có thể là một trong hai trường hợp. Một là một con đường không đi qua k (chỉ sử dụng các đỉnh trong tập hợp {1,…,k-1}[4] hoặc hai là một con đường đi qua k (từ i đến k và sau đó từ k đến i, cả hai chỉ sử dụng các đỉnh trung gian trong {1,…,k-1}) Chúng tôi biết rằng con đường tốt nhất từ i đến j chỉ sử dụng các đỉnh 1 xuyên qua k-1 được định nghĩa bởi shortestPath(i,j,k-1) và rõ ràng là nếu có một con đường tốt hơn từ i đến k đến j, sau đó độ dài của con đường này sẽ là sự kết hợp của con đường ngắn nhất từ i đến k (chỉ sử dụng các đỉnh trung gian trong {1,…,k-1}) và con đường ngắn nhất từ k đến j (chỉ sử dụng các đỉnh trung gian trong {1,…,k-1}). Công thức này là trái tim của thuật toán Floyd-Warshall. Thuật toán hoạt động bằng máy tính đầu tiên shortestPath(i,j,k) cho tất cả (i,j) cặp cho k=1, sau đó k=2, và như thế.
Quá trình này tiếp tục cho đến khi k = N và chúng tôi đã tìm ra con đường ngắn nhất cho tất cả (i,j) cặp sử dụng bất kỳ đỉnh trung gian. Mã giả cho phiên bản cơ bản này như sau: 21 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) for each edge (u, v) do dist[u][v] ← w(u, v) // The weight of the edge (u, v) for each vertex v do dist[v][v] ← 0 for k from 1 to |V| for i from 1 to |V| for j from 1 to |V| if dist[i][j] > dist[i][k] + dist[k][j] dist[i][j] ← dist[i][k] + dist[k][j] end if Độ phức tạp của thuật toán Floyd-Warshall là O(n3), trong đó n là số đỉnh của đồ thị 2. THUẬT TOÁN TÌM ĐƯỜNG TỐI ƯU GIAO THÔNG CÔNG CỘNG TRÊN THIẾT BỊ DI ĐỘNG 2. Đồ thị mô phỏng hệ thống giao thông công cộng Hà Nội Ta có hệ thống giao thông công cộng của Hà Nội gồm hơn 2500 điểm dừng, và 141 tuyến xe.
Các tuyến xe chính là đường đi qua các điểm dừng. Để mô hình hóa hệ thống giao thông công cộng Hà Nội thành đồ thị thì chúng ta coi mỗi một điểm dừng là một điểm của đồ thị, đường đi của tuyến xe qua các điểm dừng là cạnh có hướng, thời gian di chuyển giữa các điểm dừng chính là trọng số của cạnh đó. Như vậy mô hình hóa hệ thống giao thông công cộng Hà Nội chúng ta có một đồ thị G là một có hướng, có trọng số, đa đồ thị và gồm: - Khoảng 2500 đỉnh. Giải thuật tìm đường Điện thoại thông minh có rất nhiều ưu điểm để trở thành một công cụ hỗ trợ tìm đường nhưng nó lại có những nhược điểm cố hữu như tốc độ sử lý chậm, thời lượng pin hạn chế, giá thành dung lượng mạng di động cao.
Để khác phục những nhược điểm này thì độ phức tạp của giải thuật tìm đường cho hệ thông 22 giao thông công cộng phải đủ nhanh để có thể sử lý ngay trên thiết bị thông minh. Đối với đồ thị G, giải thuật tìm đường đi ngắn nhất thông dụng như Dijkstra chạy trên điện thoại thông minh thường mất từ 7 đến 15 giây. Bài toán tối ưu hệ thống giao thông công cộng Hà Nội được cụ thể như sau: Có hai điểm A và B thuộc đồ thị G. Yêu cầu tìm đường đi từ A đến B có thời gian sử lý ít nhất và tổng trọng số đường đi từ A và B là ít nhất.
Để tối ưu được đường đi cho bài toán trên chúng ta nhận thấy: - Do đi bộ mất nhiều thời gian nên sẽ trong giải thuật sẽ giảm tối đa thời gian đi bộ.