1. Trang Chủ
  2. Cơ sở dữ liệu
  3. Ứng dụng thuật toán tìm đường đi nhanh nhất tìm luồng cực đại đa phương tiện tuyến tính đồng thời chi phí cực tiểu trên mạng giao thông mở rộng

Ứng dụng thuật toán tìm đường đi nhanh nhất tìm luồng cực đại đa phương tiện tuyến tính đồng thời chi phí cực tiểu trên mạng giao thông mở rộng

Bài viết Ứng dụng thuật toán tìm đường đi nhanh nhất tìm luồng cực đại đa phương tiện tuyến tính đồng thời chi phí cực tiểu trên mạng giao thông mở rộng phân tích, chứng minh các kết quả và đánh giá độ phức tạp của thuật toán. Chương trình thuật toán được viết bằng ngôn ngữ Java với cơ sở dữ liệu mạng mở rộng cài đặt trong hệ quản trị cơ sở dữ liệu MySQL cho kết quả chính xác. TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 10(71).2013 ỨNG DỤNG THUẬT TOÁN TÌM ĐƯỜNG ĐI NHANH NHẤT TÌM LUỒNG CỰ

Thể loại Tài liệu miễn phí Cơ sở dữ liệu

Số trang 7

Ngày tạo 4/11/2023 12:50:32 PM +00:00

Loại tệp PDF

Kích thước 0.58 M

Tên tệp

Tải Ứng dụng thuật toán tìm đường đi nhanh nhất tìm lu... (.pdf)

Xem mẫu

  1. TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 10(71).2013 ỨNG DỤNG THUẬT TOÁN TÌM ĐƯỜNG ĐI NHANH NHẤT TÌM LUỒNG CỰC ĐẠI ĐA PHƯƠNG TIỆN TUYẾN TÍNH ĐỒNG THỜI CHI PHÍ CỰC TIỂU TRÊN MẠNG GIAO THÔNG MỞ RỘNG APPLICATION OF THE FASTEST PATH ALGORITHM TO FINDING MAXIMUM CONCURENT MULTICOMMODITY LINEAR FLOW WITH MINIMAL COST ON EXTENDED TRAFFIC NETWORK Trần Quốc Chiến Trường Đại học Sư phạm, Đại học Đà Nẵng Email: tqchien@dce.udn.vn TÓM TẮT Đồ thị và mạng mở rộng là công cụ toán học hữu ích ứng dụng trong nhiều lĩnh vực như giao thông, truyền thông, công nghệ thông tin, kinh tế, …. [7]. Kết quả chính của bài báo là nghiên cứu thuật toán tìm luồng cực đại đa phương tiện tuyến tính đồng thời chi phí cực tiểu trên mạng giao thông mở rộng, sử dụng thuật toán tìm đường đi nhanh nhất trên mạng giao thông mở rộng [6]. Trên sơ sở bài toán đối ngẫu trong [7], tác giả xây dựng thuật toán đưa tỉ lệ hàm mục tiêu hai bài toán đối ngẫu này tiến đến 1, và từ đó suy ra luồng cực đại đồng thời chi phí cực tiểu. Đây là thuật toán tính gần đúng với tỉ lệ xấp xỉ là (1+) với  dương nhỏ tùy ý. Bài báo phân tích, chứng minh các kết quả và đánh giá độ phức tạp của thuật toán. Chương trình thuật toán được viết bằng ngôn ngữ Java với cơ sở dữ liệu mạng mở rộng cài đặt trong hệ quản trị cơ sở dữ liệu MySQL cho kết quả chính xác. Từ khóa: đồ thị; mạng; luồng đa phương tiện; tối ưu; xấp xỉ ABSTRACT Extended graph and network is a powerful mathematical tool applied in many fields such as transportation, communication, informatics, economy, … [7]. The main result of this paper is to design a Maximum Concurent Multicommodity Flow with Minimal Cost algorithm on extended traffic networks using the algorithm to find shortest paths on extended networks [6]. On the basis of the dual linear programming problem studied in [7], the author designs the algorithm to reduce the ratio of objective values of the dual and the primal problems down to 1. Then, it follows the concurent maximal flow with minimal cost of the origin problem. This algorithm is an approximate algorithm with a (1+)-approximation ratio, where  is an arbitrary positive. The paper analyses, proves obtained results, as well as evaluates the running time. The algorithm is coded in the programming language Java with extended network database in the database management system MySQL and gives exact result. Key words: Graph; Network; Multicommodity Flow; Optimization; Approximation 1. Đặt vấn đề đa phương tiện đồng thời chi phí cực tiểu trên Bài toán tìm luồng cực đại đa phương tiện mạng giao thông mở rộng, để có thể áp dụng bài tuyến tính đồng thời chi phí cực tiểu trên mạng toán này cho các bài toán thực tế phức tạp. Bài giao thông mở rộng là dạng bài toán quy hoạch viết này sử dụng các khái niệm, ký hiệu, mô hình tuyến tính được xây dựng ở công trình [7]. Tuy và kết quả trong công trình [7]. nhiên, sử dụng các phương pháp truyền thống 2. Thuật toán trong quy hoạch tuyến tính sẽ gặp nhiều khó Ký hiệu fej(a) là luồng phương tiện j đi khăn nếu bài toán có nhiều loại phương tiện, qua cạnh a, j = 1,...,k, aE, fvj(u,a,a‘) là luồng nhiều ràng buộc về chi phí, về khả năng thông phương tiện j đi trên cạnh a vào nút u ra cạnh a‘, hành, … Lý thuyết đồ thị mô hình hóa bài toán này thành bài toán tìm luồng trên mạng. Ứng j = 1,..., k, uV, a,a‘Eu. dụng này làm cho việc giải bài toán trở nên đơn Thuật toán tìm luồng giản và hiệu quả hơn. Vấn đề đặt ra là cần xây F ={fej(a), fvj(u,e,e‘)| aE, (e,u,e‘)Bảng bV, dựng một thuật toán tổng quát tìm luồng cực đại j=1,...,k} 85
  2. TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 10(71).2013 Luồng F có thể vi phạm ràng buộc về khả năng thông qua cũng như ràng buộc về chi phí.  D leis, j , lvis, j , is, j  =  le s i , j (e).c E (e) + eE Tuy nhiên, theo mục 3, từ luồng F ta nhận được luồng tối ưu sau khi chia nó cho một hằng số.  lv vV s i , j (v).cV (v) +B.  i, j s = le eE s 1 i , j (e).c E (e) +. Khởi tạo: fej(a)=0 aE, fvj(u,e,e‘)=0 (e,u,e‘)Bảng bV, j=1,...,k  le s 1 s i , j (e). f i , j + lv s 1 i , j (v).cV (v) +. e pis, j vV Chọn  > 0 và  > 0 (giá trị  và  xác định ở phần phân tích sau).  lv s 1 i, j (v). f i ,sj vpis, j Thuật toán được thực hiện bởi một số giai +B.  i , j +. i , j .b( đoạn, mỗi giai đoạn gồm k vòng lặp (k là số s 1 s 1 pis, j ). f i ,sj = phương tiện). Ở vòng lặp thứ j, j = 1,..., k, của giai đoạn thứ i ta chuyển d(j) đơn vị phương tiện  D leis,j1, lvis,j1, is, j 1 +.  f i ,sj  le s 1 i , j ( e) +. f i ,sj thứ j qua luồng. Việc này được thực hiện trong e pis, j một số bước. Xét bước thứ s. Ký hiệu length s 1 là hàm  lv s 1 i , j (v) +. f i ,sj .b( pis, j ).  is, j 1 i, j v pis, j độ dài ở đầu bước thứ s (định nghĩa theo biểu thức (2)) và p s là đường đi ngắn nhất từ sj đến  = D lei , j , lvi , j , i , j +. s 1 s 1 s 1  f i ,sj . i, j s  dist j leis,j1, lvis,j1,is, j 1  (1) tj theo hàm này. Nghĩa là p i, j có độ dài là Vòng lặp thứ j của giai đoạn i kết thúc length s 1 i, j  p  . Đặt s i, j f s i, j = min{c, d s 1 i , j }, B s i, j sau q(i,j) bước, khi mà d iq, (ji , j ) = 0. Tổng luồng = b( pis, j ). f i ,sj , trong đó c là khả năng thông gửi qua mạng ở mỗi vòng lặp không vượt quá d(j) và chi phí ở mỗi bước không vượt quá B. qua nhỏ nhất của các cạnh và nút trên pis, j , Giai đoạn i kết thúc, khi vòng lặp thứ k của giai đoạn i kết thúc. d is, j 1 là lượng phương tiện thứ j còn lại cần Hàm đối ngẫu le và lv được tính như sau: chuyển qua (trong số d(j) đơn vị cần chuyển qua - Hàm đối ngẫu ban đầu: s trong vòng lặp này). Nếu Bi , j > B, thì ta gán lại le10,0 = /cE(e),e E, lv10, 0 = /cV(v), v  V. s s s s s f i, j = f i, j .B/ B i, j và B i, j = B. Chuyển f i, j - Hàm đối ngẫu ở đầu vòng lặp đầu tiên s đơn vị phương tiện thứ j dọc theo p i, j . của mỗi giai đoạn i bằng hàm đối ngẫu ở cuối giai đoạn trước (i1) : Luồng của phương tiện j sẽ được thay đổi như sau: lei0, 0 = leiq(1i,k1, k ) , lv i0, 0 = lviq(1i,k1, k ) . fej(a) = fej(a) + f i ,sj a pis, j & - Hàm đối ngẫu ở đầu mỗi vòng lặp tiếp theo j của giai đoạn i có giá trị bằng hàm đối fvj(u,e,e‘) = fvj(u,e,e‘) + f i ,sj (e,u,e‘) pis, j ngẫu ở cuối vòng lặp trước (j1) của giai đoạn i: Sau đó ta hiệu chỉnh lại các đại lượng lei0, j = leiq, (ji,1j 1) , lv i0, j = lviq, (ji,1j 1) . khác như sau: Tương tự, d is, j = d is, j 1  f i ,sj ,  i,s j =  is, j1 .(1+. Bis, j /B), 10, 0 = /B, i0,0 = iq(1i,k1, k ) ,  i0, j = iq, (ji,1j 1) . leis, j (e) = leis,j1 (e) (1+. f i ,s j /cE(e)),e  pis, j , Suy ra lvis, j (v) = lvis,j1 (v) (1+. f i ,sj /cV(v)),v  pis, j , 86
  3. TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 10(71).2013  D le10,0 , lv10,0 , 10,0  = le 0 1,0 (e).c E (e) +  D(i)  D(i1) + .(i) (2) eE Tiếp theo, ta có  lv10,0 (v).cV (v) + B.  0 1, 0 D(i) D (i ) vV  (i)    (i)     = c eE E ( e) c E ( e) + c vV V (v ) cV (v) + B./B Thế vào (2) ta nhận được D(i  1) = m. + n. +  = (m+n+1) D(i)  D(i1)+  D(i)/  D(i)   1  /  với m là số cạnh, n là số nút của mạng. D(i  2) D(0) ...  Ký hiệu lei, lvi, i, D(i), (i) là hàm giá trị 1   /   2 1   /  i các đại lượng ở cuối mỗi giai đoạn i. Thuật toán Thế D(0) = (m+n+1). và giả thiết   1, dừng sau giai đoạn t, khi mà D(t)  1. với mọi i  1 ta có 3. Phân tích thuật toán i 1 m  n  1. = m  n  1. . 1    1   /        leiq, (ji , j ) D(i) Để đơn giản, ký hiệu lei,j thay cho 1   /  i , lvi,j thay cho lviq, (ji , j ) , i,j thay cho  iq, (ji , j ) . Do  (i 1)  (i 1)  m  n  1. e    m  n  1. e   các biến le, lv và  luôn tăng sau mỗi bước của 1   /   1    mỗi vòng lặp nên tại bước thứ s (s > 0) của vòng Kết hợp điều kiện dừng của thuật toán là lặp ta có (sử dụng (1)) D(t)  1, ta có  D leis, j , lvis, j , is, j  = Dle s 1 i, j , lvis,j1 , is, j1 +  (t 1) m  n  1. e   . f i ,sj . dist j leis,j1, lvis,j1,is, j1   1  D(t)  1     D leis,j1 , lvis,j1 , is, j1 +. f s i, j .distj(lei,j,lvi,j, i,j). Suy ra   Mặt khác, do tổng luồng trong q(i,j) bước  (3) t 1 1  thực hiện ở vòng lặp j là d(j), bằng truy hồi suy 1   ln ra m  n  1  D lei, j , lvi , j , i, j    D lei, j , lvi , j , i, j 0 0 0  +  Nhận xét: Trong (t1) giai đoạn thực hiện thuật toán trên, j = 1,.., k, ta đã chuyển .d(j).distj(lei,j, lvi,j, i,j) = (t1).d(j) đơn vị phương tiện qua luồng. Tuy   D lei, j 1 , lvi, j 1 ,i, j 1 +.d(j).distj(lei,j,lvi,j,i,j) nhiên, luồng đã chuyển có thể vượt quá khả năng thông qua của các cạnh và nút. Bổ đề sau đây   D lei, j 1 , lvi, j 1 ,i, j 1 +.d(j).dist (le j  i,k,lvi,k, i,k) giải quyết vấn đề trên. t 1 Xét tổng truy hồi k vòng lặp trong giai  Bổ đề 1.  > . log1 (1 /  ) đoạn thứ i, ta có Chứng minh. Ban đầu, le0 = /cE(e), e   D lei, k , lvi, k , i, k    D lei,0 , lvi,0 , i,0 + .  E, lv 0 = /cV(v), v  V. Sau (t1) giai đoạn k  d ( j).dist (le j i,k , lvi , k ,i , k ) được thực hiện, ta có D(t1) < 1, tức là j 1 le t 1 (e).c E (e) + lv t 1 (v).cV (v) + B.t-1 < 1. =  D lei 1, k , lvi 1, k , i 1, k +  . eE vV k Suy ra let1(e) < 1/cE(e) e  E và lvt-1(v)  d ( j).dist (le j 1 j i ,k , lvi ,k ,  i ,k ) < 1/cV(v) vV. 87
  4. TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 10(71).2013 Gọi fe(e) là tổng phương tiện qua cạnh Ở trên ta phân tích thấy sau (t1) giai đoạn eE và fv(v) là tổng phương tiện qua nút vV thực hiện, j = 1,.., k, ta đã chuyển (t1).d(j) đơn trong (t1) giai đoạn thực hiện. vị phương tiện qua luồng. Tuy nhiên để luồng Xét cạnh eE. Giả sử trong quá trình xây chấp nhận, ta phải chia luồng chuyển qua mạng dựng luồng fe(e) có cE(e) đơn vị của luồng được 1 cho lượng log1  . Vậy, j = 1,.., k, ta chuyển chuyển qua e qua r bước, mỗi bước chuyển gs  phương tiện, g s = cE(e). Qua mỗi bước le(e) t 1 d(j), thì luồng qua mỗi cạnh eE sẽ s log1 (1 /  ) tăng lên thừa số (1+.gs/cE(e)). Vậy qua r bước không lớn hơn cE(e) và luồng qua mỗi nút vV sẽ le(e) tăng lên thừa số 1   .g s s / c E (e)  > (1+. không lớn hơn cV(v). Vậy,theo bài toán đặt ra ban t 1 đầu, ta có > g s s / cE(e)) = (1+). log1 (1 /  ) .  Bổ đề 2. Cho  > 0. Khi đó tồn tại  và Ta thấy, với mọi cạnh eE, cứ mỗi cE(e) đơn vị của luồng được chuyển qua e, thì le(e)  sao cho luồng tìm được của thuật toán, sau khi tăng lên ít nhất một thừa số (1+). chia cho log1 (1 /  ) , là luồng cực đại đồng Tương tự, với mọi nút vV, cứ mỗi cV(v) thời chi phí cực tiểu với tỉ lệ xấp xỉ là (1+). đơn vị của luồng được chuyển qua v, thì lv(v)  1 tăng lên ít nhất một thừa số (1+  ). Chứng minh: Đặt  = log1  . t 1  Mặt khác, số lần để gửi cE(e) đơn vị của  luồng qua mỗi cạnh eE ít nhất là fe(e)/cE(e) và Theo bổ đề 1 ta có  > /. Thay từ (3) vào t 1 số lần để gửi cV(v) đơn vị của luồng qua mỗi nút biểu thức  ta được vV ít nhất là fv(v)/cV(v). 1 Lúc này, hàm cạnh le và hàm nút lv sẽ  . log1 <  = thỏa bất đẳng thức sau: 1  (1   ) ln let-1(e)  le0(e). 1    fe ( e ) / c E ( e ) e  E và lvt- m  n  1. 1  lv0(v). 1    v  V.  fv ( v ) / cV ( v ) ln 1(v)  Suy ra (1   ) ln(1   ) ln 1  m  n  1. let 1 (e) fe(e)  cE(e). log1  <  1 le0 (e)  m  n 1   Chọn  =   , thì tỉ số  1   1 / c E ( e) 1 cE(e). log1  = cE(e). log1  e  E 1  / c E (e )  ln  = (1)1, và suy ra và 1  ln m  n  1. lvt 1 (v) fv(v)  cV(v). log1  < lv0 (v)   <  (1   ) ln(1   ) 2 (1   ) (   2 / 2) 2 1 / cV (v) 1 cV(v). log1  = cV(v). log1  v V.  (1)3  / cV (v)  Mặt khác theo định lý đối ngẫu yếu, ta có Chia fe(e) cho lượng log1 (1 /  ) e    1. Để /
  5. TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 10(71).2013 (1)3  1+    1  3 1 . Khi đó, giá D (l )  c(e).l (e) 1  Nhìn lại,  = minl = eE  (l ) k trị  = t 1 là trị xấp xỉ cực đại với tỉ lệ  d ( j).dist (l ) j 1 j log1 (1 /  ) . Ta có thể tăng hoặc giảm  bởi một thừa số r (1+). bằng cách nhân các c(e) hoặc các d(j) lên một  Bổ đề 3. Tổng chi phí luồng trong (t1) thừa số r tương ứng (mà việc nhân này sẽ không vòng lặp không vượt quá B. log1 (1 /  ) . Nghĩa ảnh hưởng đến kết quả của bài toán, vì sau đó ta là, tổng chi phí của luồng sau khi chia cho có thể giảm hoặc tăng  bởi thừa số r). log1 (1/  ) không vượt quá B. Gọi zi là luồng cực đại của phương tiện i, i = 1, …, k. Đặt z = minizi/d(i). Khi đó z chính là Chứng minh. Ta có 1,0 = /B. Sau (t1) giai phân số của các yêu cầu cần vận chuyển các đoạn được thực hiện, ta có D(t1) < 1, tức là phương tiện một cách độc lập. Từ  = , suy ra z/k  le eE t 1 (e).cE (e) +  lvt 1 (v).cV (v) + B.t-1 < 1. vV    z. Ta có thể chia các c(e) hoặc các d(j) cho một số sao cho z/k = 1, để thỏa mãn giả thuyết đưa Suy ra t1 < 1/B. Hơn nữa, mỗi khi ra ban đầu là   1. Lúc này ta cũng có   k. chuyển luồng qua mạng mà tổng chi phí tăng lên  1 Đặt T = 2. log1   tương ứng với B, thì  tăng lên một thừa số không nhỏ hơn   (1+). Vì vậy, gọi x là số lần thuật toán làm tăng   2. Nếu thuật toán không dừng lại ở T giai chi phí lên B đơn vị, ta có 1,0.(1+)x  t1  1/B đoạn thực hiện, thì chúng ta nhân đôi tất cả các  x  log1 (1 /  ) . d(j), (tương đương với chia đôi , nhưng vẫn Vậy tổng chi phí của quá trình thực hiện là thỏa   1), rồi thực hiện thuật toán tiếp T giai B. log1 (1 /  ) . Khi chia luồng đạt được cho đoạn nữa. Nếu thuật toán vẫn chưa dừng, ta tiếp tục giải pháp trên đến khi thuật toán dừng và lưu log1 (1/  ) , ta đồng thời có tổng chi phí giảm ý lúc này vẫn thỏa   1 . đi thừa số log1 (1 /  ) , thỏa mãn yêu cầu đặt ra Ta thấy mỗi khi thực hiện T giai đoạn thì của bài toán.  giảm đi một nữa. Nếu x là số lần thực hiện T Độ phức tạp thuật toán được trình bày giai đoạn, thì  giảm đi một thừa số 2x. Ta có và chứng minh trong mệnh đề sau. 1  /2x  2x    k  x  log2k  Định lí. Thuật toán tính được luồng xấp xỉ cực đại với tỉ lệ (1+) có độ phức tạp là  1 Vậy t = T.x = 2.log2k. log1  . O(2.(2k.log2k+m).log2m.n3).    Trong đó k là số phương tiện, m là số  1  m   cạnh, n là số nút của mạng. Thay  =   vào ta được 1   Chứng minh. Trước tiên, chúng ta tìm số giai đoạn mà thuật toán đã thực hiện. Theo bổ đề 1 m  t = 2.logk.  log1   1  1    1 và do  = , ta có 1   = log1   t  t 1  Mặt khác, mỗi giai đoạn ta thực hiện k 1  1 vòng lặp, nên số vòng lặp là k.t. Hơn thế, ở mỗi 1 + . log1  t =   . log1   ,    vòng lặp, ta thực hiện một số bước. Tiếp theo, ta đi tìm tổng số bước thực hiện của thuật toán. Ở trong đó,  và  phụ thuộc vào . Ngoài mỗi bước, trừ bước sau cùng của mỗi vòng lặp, ta ra, t còn phụ thuộc vào . tăng độ dài của ít nhất một cạnh lên (1+) lần. Xét cạnh e bất kì, ta có l0(e)=/c(e) và lt(e)
  6. TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 10(71).2013 D(t1)
  7. TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 10(71).2013 ngôn ngữ Java với cơ sở dữ liệu mạng mở rộng cài đặt trong hệ quản trị cơ sở dữ liệu MySQL. Chương trình cho kết quả phân luồng cực đại như sau: Hệ số cực đại  = 0.8723167523 Chi phí thực tế là: 594.3263411978 Hình 4. Số phương tiện được phân luồng cho mỗi 5. Kết luận cặp nguồn đích là 8.72. Thuật toán tìm luồng cực đại đa phương Phân luồng cho phương tiện đi từ nguồn 1 tiện đồng thời chi phí cực tiểu trên mạng mở đến đích 5, nguồn 2 đến đích 4 và nguồn 3 đến rộng trình bày ở trên có thể áp dụng giải quyết đích 6 cho tương ứng ở hình 2, hình 3 và hình 4. nhiều vấn đề thực tế có thể đưa về dạng bài toán tối ưu trên mạng đa phương tiện mở rộng, ví dụ như bài toán phân luồng giao thông, vận tải hàng hóa, phân luồng trên mạng internet, lưu hành phương tiện, … Chương trình thuật toán được viết bằng ngôn ngữ Java với cơ sở dữ liệu mạng mở rộng cài đặt trong hệ quản trị cơ sở dữ liệu Hình 2. MySQL cho kết quả chính xác. Hình 3. TÀI LIỆU THAM KHẢO [1] Naveen Garg, Jochen Könemann: Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems, SIAM J. Comput, Canada, 37(2), 2007, pp. 630-652. [2] Trần Quốc Chiến: Bài toán mạng giao thông đa phương tiện tuyến tính, Đề tài NCKH cấp Bộ, mã số B2010DN-03-52. [3] Trần Quốc Chiến, Trần Thị Mỹ Dung: Ứng dụng thuật toán tìm đường đi ngắn nhất tìm luồng cực đại đa hàng hóa. Tạp chí Khoa học & Công nghệ, Đại học Đà Nẵng, 3(44)2011. [4] Trần Quốc Chiến: Ứng dụng thuật toán tìm đường đi ngắn nhất đa nguồn đích tìm luồng cực đại đa hàng hóa đồng thời. Tạp chí Khoa học & Công nghệ, Đại học Đà Nẵng, 4(53)2012. [5] Trần Quốc Chiến: Ứng dụng thuật toán tìm đường đi ngắn nhất đa nguồn đích tìm luồng cực đại đa hàng hóa đồng thời chi phí cực tiểu. Tạp chí Khoa học & Công nghệ, Đại học Đà Nẵng, 5(54)2012. [6] Trần Quốc Chiến: Thuật toán tìm đường đi ngắn nhất trên đồ thị tổng quát, Tạp chí Khoa học & Công nghệ, Đại học Đà Nẵng, 12(61)/2012, 16-21. [7] Trần Quốc Chiến: Mạng giao thông mở rộng và bài toán phân luồng giao thông đa phương tiện tuyến tính, Tạp chí Khoa học & Công nghệ, Đại học Đà Nẵng. Submitted. (BBT nhận bài: 27/07/2013, phản biện xong: 25/09/2013) 91
nguon tai.lieu . vn
Tin học văn phòng Đồ họa - Thiết kế - Flash Quản trị Web Cơ sở dữ liệu Quản trị mạng Kỹ thuật lập trình Hệ điều hành Phần cứng An ninh - Bảo mật Chứng chỉ quốc tế Thủ thuật máy tính Điện - Điện tử Kinh tế học Hoá học Xã hội học Môi trường