Thuật toán Bellman-Ford cải biên tìm đường đi ngắn nhất trên mạng mở rộng
Số trang: 4
Loại file: pdf
Dung lượng: 245.35 KB
Lượt xem: 27
Lượt tải: 0
Xem trước 1 trang đầu tiên của tài liệu này:
Thông tin tài liệu:
Bài viết Thuật toán Bellman-Ford cải biên tìm đường đi ngắn nhất trên mạng mở rộng xây dựng và chứng minh thuật toán Bellman-Ford cải biên tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh khác trên mạng đồ thị mở rộng.
Nội dung trích xuất từ tài liệu:
Thuật toán Bellman-Ford cải biên tìm đường đi ngắn nhất trên mạng mở rộng 84 Trần Quốc Chiến THUẬT TOÁN BELLMAN-FORD CẢI BIÊN TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN MẠNG MỞ RỘNG REVISED BELLMAN-FORD ALGORITHM FINDING SHORTEST PATH ON EXTENDED NETWORKS Trần Quốc Chiến Trường Đại học Sư phạm, Đại học Đà Nẵng; tqchien@dce.udn.vn Tóm tắt - Đồ thị là công cụ toán học hữu ích ứng dụng trong nhiều Abstract - Graph is a powerful mathematical tool applied in many lĩnh vực như giao thông, truyền thông, công nghệ thông tin, kinh tế, fields such as transportation, communication, informatics, …. Cho đến nay, trong đồ thị mới chỉ xét đến trọng số của các economy, … So far, in ordinary graph the weights of edges and cạnh, các đỉnh một cách độc lập, trong đó độ dài đường đi chỉ đơn vertexes are considered independently and the length of a path is thuần là tổng trọng số các cạnh và các đỉnh trên đường đi đó. Tuy simply the sum of weights of the edges and the vertexes on this nhiên, trong nhiều bài toán thực tế, trọng số tại một đỉnh không path. However, in many practical problems, weights at a vertex giống nhau với mọi đường đi qua đỉnh đó, mà còn phụ thuộc vào are not the same for all paths passing this vertex, but depend on cạnh đi đến và cạnh đi khỏi đỉnh đó. Trong bài báo, mô hình đồ thị coming and leaving edges. Therefore, a more general type of mở rộng được định nghĩa. Bài toán tìm đường đi ngắn nhất là bài graphs, called extended graph, is defined in this work. The toán quan trọng nhất trong lý thuyết đồ thị và có nhiều ý nghĩa khoa shortest path problem is one of the most important problems học và ứng dụng. Thuật toán Bellman-Ford là thuật toán chính tìm having great scientific and practical meaning. On the basis of the đường đi ngắn nhất từ một đỉnh đến các đỉnh khác, trong đó trọng Bellman-Ford algorithm which finds shortest paths from a vertex số cạnh có thể âm. Trên cơ sở thuật toán Bellman-Ford tìm đường to other verteces, this paper develops a revised Bellman-Ford đi ngắn nhất trên đồ thị truyền thống, tác giả xây dựng và chứng algorithm finding the shortest path from a vertex to other verteces minh thuật toán Bellman-Ford cải biên tìm đường đi ngắn nhất từ on extended networks. một đỉnh đến các đỉnh khác trên mạng đồ thị mở rộng. Từ khóa - đồ thị; đồ thị mở rộng; đường đi ngắn nhất; thuật toán Key words - graph; extended graph; shortest path; Dijkstra Dijkstra; thuật toán Bellman-Ford. algorithm; Bellman-Ford algorithm. 1. Đặt vấn đề trong mạng thặng dư sẽ xuất hiện trọng số âm. Khi đó, ta Đồ thị là công cụ toán học hữu ích ứng dụng trong phải tìm chu trình âm để hiệu chỉnh luồng giảm chi phí. nhiều lĩnh vực như giao thông, truyền thông, công nghệ 2. Đồ thị hỗn hợp mở rộng thông tin, kinh tế, …. Cho đến nay trong đồ thị mới chỉ xét đến trọng số của các cạnh, các đỉnh một cách độc lập, trong Cho đồ thị hỗn hợp G=(V, E) với tập đỉnh V và tập đó độ dài đường đi chỉ đơn thuần là tổng trọng số các cạnh cạnh E, trong đó các cạnh có thể có hướng hoặc vô và các đỉnh trên đường đi đó. Tuy nhiên, trong nhiều bài hướng. Mỗi cạnh eE được gán trọng số wE(e). Ký hiệu toán thực tế, trọng số tại một đỉnh không giống nhau với Ei0 là tập hợp các cạnh vô hướng của G và E1 là tập hợp mọi đường đi qua đỉnh đó, mà còn phụ thuộc vào cạnh đi các cạnh có hướng của G, m0 = |E0|, m1 = |E1|. Với mỗi đến và cạnh đi khỏi đỉnh đó. Ví dụ, thời gian đi qua ngã tư đỉnh vV, ký hiệu Nv là tập các cạnh vô hướng liên thuộc trên mạng giao thông phụ thuộc vào hướng di chuyển của đỉnh v, Iv là tập các cạnh có hướng đi vào đỉnh v và Ov là phương tiện giao thông: rẽ phải, đi thẳng hay rẽ trái. tập các cạnh có hướng đi ra từ đỉnh v. Mỗi đỉnh vV và Vì vậy, cần xây dựng một mô hình đồ thị tổng quát để mỗi cặp cạnh (e,e’)(NvIv)(NvOv), ee’ được gán có thể áp dụng mô hình hóa các bài toán thực tế chính xác trọng số wV(v,e,e’). và hiệu quả hơn. Thuật toán tìm đường đi ngắn nhất là Bộ (V, E, wE, wV) gọi là đồ thị mở rộng. thuật toán cơ sở quan trọng, được sử dụng trong nhiều bài Cho p là đường đi từ đỉnh u đến đỉnh v qua các cạnh toán tối ưu trên đồ thị và mạng. Thuật toán Dijkstra nổi ei, i = 1, …, h+1, và các đỉnh ui, i = 1, …, h, như sau: tiếng tìm đường đi ngắn nhất giữa hai đỉnh đã được cải p = [u, e1, u1, e2, u2, …, eh, uh, eh+1, v] biên thành thuật toán tìm đường đi ngắn nhất trong đồ thị mở rộng [1], [2]. Tuy nhiên, thuật toán này có một hạn Định nghĩa độ dài đường đi p, ký hiệu l(p), theo công chế là trọng số các cạnh phải dương. Thuật toán Bellman- thức sau: h 1 h Ford là thuật toán tìm đường đi ngắn nhất từ một đỉnh đến l p wE (ei ) wV (ui , ei , ei 1 ) các đỉnh khác, trong đó trọng số cạnh có thể âm, được i 1 i 1 (1) nghiên cứu và phát triển trong các công trình [3]-[9]. Trên Bài toán tìm đường đi ngắn nhất cơ sở thuật ...
Nội dung trích xuất từ tài liệu:
Thuật toán Bellman-Ford cải biên tìm đường đi ngắn nhất trên mạng mở rộng 84 Trần Quốc Chiến THUẬT TOÁN BELLMAN-FORD CẢI BIÊN TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN MẠNG MỞ RỘNG REVISED BELLMAN-FORD ALGORITHM FINDING SHORTEST PATH ON EXTENDED NETWORKS Trần Quốc Chiến Trường Đại học Sư phạm, Đại học Đà Nẵng; tqchien@dce.udn.vn Tóm tắt - Đồ thị là công cụ toán học hữu ích ứng dụng trong nhiều Abstract - Graph is a powerful mathematical tool applied in many lĩnh vực như giao thông, truyền thông, công nghệ thông tin, kinh tế, fields such as transportation, communication, informatics, …. Cho đến nay, trong đồ thị mới chỉ xét đến trọng số của các economy, … So far, in ordinary graph the weights of edges and cạnh, các đỉnh một cách độc lập, trong đó độ dài đường đi chỉ đơn vertexes are considered independently and the length of a path is thuần là tổng trọng số các cạnh và các đỉnh trên đường đi đó. Tuy simply the sum of weights of the edges and the vertexes on this nhiên, trong nhiều bài toán thực tế, trọng số tại một đỉnh không path. However, in many practical problems, weights at a vertex giống nhau với mọi đường đi qua đỉnh đó, mà còn phụ thuộc vào are not the same for all paths passing this vertex, but depend on cạnh đi đến và cạnh đi khỏi đỉnh đó. Trong bài báo, mô hình đồ thị coming and leaving edges. Therefore, a more general type of mở rộng được định nghĩa. Bài toán tìm đường đi ngắn nhất là bài graphs, called extended graph, is defined in this work. The toán quan trọng nhất trong lý thuyết đồ thị và có nhiều ý nghĩa khoa shortest path problem is one of the most important problems học và ứng dụng. Thuật toán Bellman-Ford là thuật toán chính tìm having great scientific and practical meaning. On the basis of the đường đi ngắn nhất từ một đỉnh đến các đỉnh khác, trong đó trọng Bellman-Ford algorithm which finds shortest paths from a vertex số cạnh có thể âm. Trên cơ sở thuật toán Bellman-Ford tìm đường to other verteces, this paper develops a revised Bellman-Ford đi ngắn nhất trên đồ thị truyền thống, tác giả xây dựng và chứng algorithm finding the shortest path from a vertex to other verteces minh thuật toán Bellman-Ford cải biên tìm đường đi ngắn nhất từ on extended networks. một đỉnh đến các đỉnh khác trên mạng đồ thị mở rộng. Từ khóa - đồ thị; đồ thị mở rộng; đường đi ngắn nhất; thuật toán Key words - graph; extended graph; shortest path; Dijkstra Dijkstra; thuật toán Bellman-Ford. algorithm; Bellman-Ford algorithm. 1. Đặt vấn đề trong mạng thặng dư sẽ xuất hiện trọng số âm. Khi đó, ta Đồ thị là công cụ toán học hữu ích ứng dụng trong phải tìm chu trình âm để hiệu chỉnh luồng giảm chi phí. nhiều lĩnh vực như giao thông, truyền thông, công nghệ 2. Đồ thị hỗn hợp mở rộng thông tin, kinh tế, …. Cho đến nay trong đồ thị mới chỉ xét đến trọng số của các cạnh, các đỉnh một cách độc lập, trong Cho đồ thị hỗn hợp G=(V, E) với tập đỉnh V và tập đó độ dài đường đi chỉ đơn thuần là tổng trọng số các cạnh cạnh E, trong đó các cạnh có thể có hướng hoặc vô và các đỉnh trên đường đi đó. Tuy nhiên, trong nhiều bài hướng. Mỗi cạnh eE được gán trọng số wE(e). Ký hiệu toán thực tế, trọng số tại một đỉnh không giống nhau với Ei0 là tập hợp các cạnh vô hướng của G và E1 là tập hợp mọi đường đi qua đỉnh đó, mà còn phụ thuộc vào cạnh đi các cạnh có hướng của G, m0 = |E0|, m1 = |E1|. Với mỗi đến và cạnh đi khỏi đỉnh đó. Ví dụ, thời gian đi qua ngã tư đỉnh vV, ký hiệu Nv là tập các cạnh vô hướng liên thuộc trên mạng giao thông phụ thuộc vào hướng di chuyển của đỉnh v, Iv là tập các cạnh có hướng đi vào đỉnh v và Ov là phương tiện giao thông: rẽ phải, đi thẳng hay rẽ trái. tập các cạnh có hướng đi ra từ đỉnh v. Mỗi đỉnh vV và Vì vậy, cần xây dựng một mô hình đồ thị tổng quát để mỗi cặp cạnh (e,e’)(NvIv)(NvOv), ee’ được gán có thể áp dụng mô hình hóa các bài toán thực tế chính xác trọng số wV(v,e,e’). và hiệu quả hơn. Thuật toán tìm đường đi ngắn nhất là Bộ (V, E, wE, wV) gọi là đồ thị mở rộng. thuật toán cơ sở quan trọng, được sử dụng trong nhiều bài Cho p là đường đi từ đỉnh u đến đỉnh v qua các cạnh toán tối ưu trên đồ thị và mạng. Thuật toán Dijkstra nổi ei, i = 1, …, h+1, và các đỉnh ui, i = 1, …, h, như sau: tiếng tìm đường đi ngắn nhất giữa hai đỉnh đã được cải p = [u, e1, u1, e2, u2, …, eh, uh, eh+1, v] biên thành thuật toán tìm đường đi ngắn nhất trong đồ thị mở rộng [1], [2]. Tuy nhiên, thuật toán này có một hạn Định nghĩa độ dài đường đi p, ký hiệu l(p), theo công chế là trọng số các cạnh phải dương. Thuật toán Bellman- thức sau: h 1 h Ford là thuật toán tìm đường đi ngắn nhất từ một đỉnh đến l p wE (ei ) wV (ui , ei , ei 1 ) các đỉnh khác, trong đó trọng số cạnh có thể âm, được i 1 i 1 (1) nghiên cứu và phát triển trong các công trình [3]-[9]. Trên Bài toán tìm đường đi ngắn nhất cơ sở thuật ...
Tìm kiếm theo từ khóa liên quan:
Đồ thị mở rộng Thuật toán Dijkstra Thuật toán Bellman-Ford Đồ thị hỗn hợp mở rộng Thuật toán tìm đường đi ngắn nhấtTài liệu có liên quan:
-
Thực hành Toán rời rạc - Chương 7: Đồ thị và các tính chất của đồ thị
10 trang 49 0 0 -
Bài giảng Lý thuyết đồ thị: Chương 7 - TS. Lê Nhật Duy
19 trang 48 0 0 -
Bài giảng Thuật toán ứng dụng: Graphs
141 trang 45 0 0 -
47 trang 37 0 0
-
Bài giảng Toán rời rạc 2: Phần 2
59 trang 35 0 0 -
Bài giảng cơ sở lập trình nâng cao - Chương 8
37 trang 33 0 0 -
Bài 14_Chương 8: Bài toán đường đi ngắn nhất
9 trang 29 0 0 -
Bài giảng môn Lý thuyết đồ thị - Chương 5: Bài toán đường đi ngắn nhất
69 trang 29 0 0 -
Chương 3 - CÁC BÀI TOÁN ĐƯỜNG ĐI
74 trang 28 0 0 -
Bài giảng Lý thuyết đồ thị: Chương 5 - Tôn Quang Toại
34 trang 28 0 0