Lập trình

II.1. Đường đi ngắn nhất với mọi cặp đỉnh

Trở lại bài tóan tìm đường đi ngắn nhất với mọi cặp đỉnh, để giải quyết bài tóan này ta cần chạy một thuật tóan các lộ trình ngắn nhất nguồn đơn  lần, mỗi lần cho một đỉnh làm nguồn. Nếu tất cả các cạnh đều không âm, ta có thể dùng thuật tóan Dijkstra. Nếu thực thi theo mảng tuyến tính của hàng đợi ưu tiên, thời gian thực hiện là O( V³ + VE) = O(V³). Cách thực thi theo đống nhị phân của hành đợi ưu tiên sẽ cho thời gian thực hiện O(VelgV), là một cải thiện nếu đồ thị thưa. Một cách cải thiện khác nếu thực thi theo hàng đơi ưu tiên với đống Fibonaci, mang lại thời gian thực hiện O(V²lgV+VE).

Khi các trọng số không âm, ta không thể thực hiện thuật tóan Dijkstra mà phải chạy thuật tóan Bellman –Ford chậm hơn mỗi lần từ một đỉnh. Thời gian thực hiện kết quả là O(V²E), mà trên đồ thị trù mật nó là O(V²)  

II.2.Các đường đi ngắn nhất và phép nhân ma trận

Khác với bài tóan nguồn đơn, hầu hết các bài tóan ở phần này đều sử dụng một phép biểu diễn ma trận kề. ( Thuật tóan John cho đồ thị thưa sử dụng ma danh sách kề). Nhập liệu là một ma trận n x n. W biểu diễn cho trọng số cạnh của một đồ thị

 G = (V,E) có hướng  n. Nghĩa là, đồ thị được biểu diễn một ma trận kề W= (, ở đó

	nếu i =j trọng số của cạnh có hướng (i,j)   nếu i ≠ j và i,j E                                                             nếu i ≠ j và i,j  E

 

 

                                                                                                                    (26.1)

 

Trọng số của các cạnh có thể âm, và ta mặc nihên công nhận đồ thị nhập liệu không chứa chu trình âm.

Giả sử đồ thị được biểu diễn một ma trận kề W= (. Xét một lộ trình ngắn nhất p từ đỉnh i đến đỉnh j, và giả sử p chứa tối đa m cạnh. Giả sử G không có các chu trình trọng số âm, m hữu hạn. Nếu i = j thì p có trọng số 0 và không có các cạnh. Nếu i và j phân biệt ta phân tích lộ trình p thành i   kàj, ở đó p^’ chứa tối đa m-1 cạnh. Hơn nữa, theo bổ đề  trên, p^’ là lộ trình ngắn nhất từ i đến k. Như vậy theo hệ luận 1.2.1 ta có

Giả sử cho  là trọng số cực tiểu của của bất kỳ lộ trình nào từ đỉnh i đến j chứa tối đa m cạnh. Khi m =0, ta có một lộ trình ngắn nhất từ i đến j mà không có các cạnh nếu và chỉ nếu i = j. Như vậy :

nếu i = j nếu i ≠ j

               

 

            Với m ≥1 ta tính tóan  dưới dạng cực tiểu của . Như vậy từ định nghĩa theo đệ quy ta có

           

                   =                                                           (2.6.2)

Đẳng thức trên đúng với  = 0 với mọi j.

            Đâu là trọng số ngắn nhất thực tế . Nếu đồ thị không chứa các chu trình trọng số âm, thì tất cả các lộ trình ngắn nhất là đơn giản và như vậy chứa tối đa n-1 cạnh. Một lộ trình từ đỉnh i đến j trên n-1 cạnh không thể có ít trọng số hơn một lộ trình ngắn nhất từ i đến j. Do đó, các trọng số lộ trình ngắn nhất thực tế là :

              =                                                     (26.3)

Tính tóan các lộ trình ngắn nhất từ dưới lên

Để nhập liệu ta lấy ma trận W= () và tính tóan các ma trận D⁽¹⁾, D⁽²⁾, …D^(n-1), ở đó với m=1,2,…,n-1. Ta có D^(m) = ( ). Ma trận chung cuộc chứa các trọng số của lộ trình ngắn nhất thực tế. Nhận thấy do với tất cả các đỉnh i,j V nên ta có D⁽¹⁾=W. Trọng tâm của thuật tóan là thủ tục dưới đây. Căn cứ vào các ma trận D^(m-1) và W, nó trả về ma trận D^(m) . Nghĩa là nó mở rộng thêm một cạnh cho các lộ trình ngắn nhất đã tính.

EXTEND-SHORTEST –PATHS(D,W)

            n  rows[D]

            cho D^’ = là một ma trận n xn

            for i 1 to n

                        do for j1 to n

                                    do ∞

                                                for k 1 to n

                                                            do  = min(, )

            return D^’

            Ta có thể quan hệ với phép nhân ma trận. Giả sử ta muốn tính tích ma trận C=A*B của 2 ma trận n x n của A và B. Như vậy với i,j= 1,2,…,n ta tính tóan

                                                                                              (26.4)

            Nhận thấy nếu ta tiến hành thay :

            d^(m-1)  a

            w  b

            d^(m)  c

            min  +

            + .

Trong phương trình (26.2) ta được phương trình (26.4). Như vậy, nếu ta thực hiện thay đổi này với EXTEND-SHORTEST –PATHS và cũng thay ∞ (đồng nhất thức của min) bằng 0( đồng nhất thức của +) ta được thủ tục đơn giản trong phép nhân ma trận.

MATRIX-MULTIPLY(A,B)

n  rows[A]

Cho C là ma trận n x n

for i  1 to n

            do for j  1 to n

                        do    0

                        for  k 1 to n

                                    do    

 return C

Trở lại với bài tóan lộ trình ngắn nhất với mọi cặp, ta tính tóan các lộ trình ngắn nhất bằng cách mở rộng các lộ trình ngắn nhất theo từng cạnh. Việc cho A*B qua kết quả trả về EXTEND-SHORTEST –PATHS(A,B), ta tính dãy n-1 ma trận.

D⁽¹⁾ = D⁽⁰⁾*W = W

D⁽²⁾ = D⁽¹⁾*W = W²

D⁽³⁾ = D⁽¹⁾*W = W³

……………………

D^(n-1) = D^(n-2)*W = W^(n-1)

Thủ tục dưới đây thể hiện dãy tính tóan này

SLOW-ALL-PAIRS-SHORTEST-PATHS(W)

n  rows[W]

D⁽¹⁾ W

for m  2 to n-1

            do D^(m) j  1 to EXTEND-SHORTEST –PATHS(D^(m-1),W)

 return D^(n-1)

Hình 1.3 nêu một đồ thị và các ma trận D(m) đã tính tóan theo thủ tục SLOW-ALL-PAIRS-SHORTEST-PATHS

Cải thiện thời gian thực hiện

Tuy nhiên, mục tiêu của chúng ta là không tính tóan tất cả các ma trận D^(m) mà chỉ quan tâm đến ma trận D^(n-1) . Với chú ý rằng, không có chu trình trọng số âm thì phương trình (26.3) hàm ý D^(m) = D^(n-1) với tất cả các số nguyên m≥ n-1. Ta có thể tính tóan D^(n-1) với chỉ  tích ma trận bằng cách tính tóan dãy

 

 

 

 

 

 

 

 

 

 

 

 

 

Hình 1.3.Một đồ thị có hướng và dãy cac ma trận D^(m)  được SLOW-ALL-PAIRS-SHORTEST-PATHS tính tóan

D⁽¹⁾ = W        = W

D⁽²⁾ = W²       = W*W

D⁽⁴⁾ = W⁴       = W²*W²

D⁽⁸⁾ = W⁸       = W⁴*W⁴

……………………

D^2(n-1) = W^2(n-2) = W^(n-1)*W^(n-1)

Bởi vì , tích chung cuộc ⁾  sẽ bằng với D^(n-1)

Thủ tục dưới đây tính tóan dãy ma trận trên bằng cách dùng kỹ thuật bình phương lập lại

FASTER-ALL-PAIRS-SHORTEST-PATHS(W)

n  rows[W]

D⁽¹⁾ W

m  2 to n-1

while n-1 > m

            do ⁾  EXTEND-SHORTEST –PATHS(D^(m-1),D^(m))

 return D^(m)

            Trong mỗi lần lặp lại của vòng While, ta tính D^(2m) = (D^(m))^2,  bắt đầu với m =1. Vào cuối mỗi lần lặp ta nhân đôi giá trị m. Lần lặp cuối cùng sẽ tính tóan D^(n-1) bằn thực tế tính tóan D^(2m) với n-1 ≤ 2m ≤ 2n-2. Theo phương trình (26.3) D^(2m) = D^(n-1). Vào lần sau, đợt kiểm tra dòng 4 được thực hiện, ma đã được nhân đôi, do đó giờ đây n-1 ≤m, đợt kiểm tra thất bại và thủ tục trả về ma trận cuối mà nó đã tính tóan.

            Thời gian thực hiện thủ tục FASTER-ALL-PAIRS-SHORTEST-PATHS là (n³lgn), bởi mỗi trong số  tích ma trận mất (n³) thời gian.        

II.3. Thuật toán Floyd – Warshall

Trong đoạn này, ta sẽ dùng một cách trình bày lập trình động khác để giải quyết bài toán các lộ trình ngắn nhất mọi cặp đỉnh trên một đồ thị có hướng G = ( V, E). Thuật toán kết quả, có tên là thuật toán Floyd – Warshall, chạy trong (V³) thời gian. Như trên đây, các trọng số cạnh âm có thể hiện diện, nhưng ta nhận ra không có các chu trình trọng số âm. Cũng như trong đoạn 26.1, ta sẽ theo tiến trình lập trình động để phát triển thuật toán. Sau khi nghiên cứu thuật toán kết quả, ta sẽ trình bày một số phương pháp tương tự để tìm bao đóng bắc cầu ( transitive closure) của một đồ thị có hướng.

II.3.1.Cấu trúc của một lộ trình ngắn nhất

            Trong thuật toán Floyd – Warshall, ta dùng một kiểu mô tả đặc điểm khác về cấu trúc của một lộ trình ngắn nhất so với kiểu đã dùng trong các thuật toán mọi cặp gốc phép nhân ma trận. Thuật toán xét các đỉnh trung gian của một lộ trình ngắn nhất, ở đó một đỉnh trung gian của một lộ trình đơn giản p = < v₁, v₂, ..., v_i> là bất kỳ đỉnh nào của p khác ngoài v₁ hoặc v_i, nghĩa là bất kỳ đỉnh nào trong tập hợp {v_2, v₃, ...,v_{i-1 }}

Tất cả các đỉnh trung gian trong {1, 2,...k-1} tất cả các đỉnh trung gian trong {1 ,2, …,k-1}

P: tất cả các đỉnh trung gian trong {1, 2,…k}

			P1
					p2

 

 

 

 

 

 

 

 

Hình 1.4.Lộ trình p là một lộ trình ngắn nhất từ đỉnh i đến đỉnh j, và k là đỉnh trung gian được đánh số cao nhất của p.

Lộ trình p₁, phần lộ trình p từ đỉnh I đến đỉnh k, có tất cả các đỉnh trung gian trong tập hợp {1, 2 , …,k-1} . Điều này cũng áp dụng cho lộ trình p₂ từ đỉnh k đến đỉnh j.

            Thuật toán Floyd – Warshall dựa trên nhận xét dưới đây. Cho các đỉnh của G là V = {1, 2,…n} và xét một tập hợp con {1, 2, …, k} các đỉnh với vài k. Với một cặp đỉnh i, j thuộc V bất kỳ, xét tất cả các lộ trình từ i đến j có tất cả các đỉnh trung gian được rút ra từ {1, 2, …,k} và cho p là một lộ trình trọng số cực tiểu từ trọng số chúng. (Lộ trình p là đơn giản, bởi ta mặc nhận p không chứa các chu trình trọng số âm. Thuật toán Floyd – Warshall khai thác một mối quan hệ giữa lộ trình p và các lộ trình ngắn nhất từ i đến j với tất cả các đỉnh trung gian trong tập hợp {1, 2, …, k-1}. Mối quan hệ tuỳ thuộc vào việc có phải là một đỉnh trung gian của lộ trình p hay không?

            + Nếu k không phải là một đỉnh trung gian của lộ trình p, thì tất cả các đỉnh trung gian của lộ trình p nằm trong tập hợp {1, 2, …,k-1}. Như vậy, một lộ trình ngắn nhất từ đỉnh i đến đỉnh j với tất cả các đỉnh trung gian trong tập hợp {1, 2,…,k-1} cũng là một lộ trình ngắn nhất từ i đến j với tất cả các đỉnh trung gian trong tập hợp {1, 2,….,k}.

            + Nếu k là một đỉnh trung gian của lộ trình p, thì ta tách nhỏ phần p thành iàp₁àkàp₁àj như đã nêu trong hình 1.1 Theo bổ đề 1.1, p1 là một lộ trình ngắn nhất từ i đến k với tất cả các đỉnh trung gian trong tập hợp {1, 2,…k}. Thực vây, đỉnh k không phải là một đỉnh trung gian của lộ trình p1, và do đó p1 là một lộ trình ngắn nhất từ 1 đến k với tất cả các đỉnh trung gian trong tập hợp {1, 2,…k-1} . Cũng vậy, p₂ là một lộ trình ngắn nhất từ đỉnh k đến đỉnh j với tất cả các đỉnh trung gian trong tập hợp {1, 2, …k-1}.

II.3.2. Một giải pháp đệ quy cho bài toán các lộ trình ngắn nhất mọi cặp

            Dựa vào các nhận xét trên đây, ta định nghĩa một cách trình bày đệ quy khác về các ước lượng lộ trình ngắn nhất so với trong đoạn II.2.Cho d^(k)_ij là trọng số của một lộ trình ngắn nhất từ đỉnh i đến đỉnh j với tất cả các đỉnh trung gian trong tập hợp {1, 2, ….k}. Khi k = 0 , một lộ trình từ đỉnh i đến đỉnh j mà không có đỉnh trung gian nào được đánh số cao hơn 0 sẽ không có các đỉnh trung gian nào cả. Như vậy nó có tối da một cạnh và do đó d⁽⁰⁾_ij = wij . Một định nghĩa đệ quy dựa vào:

         (26.5)

Ma trận D^(m) = (d^(m)_ij ) cho đáp án chung cuộc d^(m)_ij = δ(i, j) với tất cả i, j thuộc V - bởi tất cả các đỉnh trung gian nằm trong tập hợp {1, 2,….n}.

II.3.3.Tính toán các trọng số lộ trình ngắn nhất dưới lên

            Dựa trên phép toán (26.5) ta có thể dùng thủ tục dưới lên sau đây để tính toán các giá trị d^(k)_ij theo thứ tự của các giá trị tăng dần của k. Nhập liệu của nó là một ma trận n xn . W được định nghĩa như trong phương trình (26.1). Thủ tục trả về ma trận D^m  gồm các trọng số lộ trình ngắn nhất.

FLOYD –WARSHALL (W)

1. nßrows[W]

2. D⁰ ßW

3. for k ß1 to n

4.                  do for i ß1 to n

5.                  do for j ß1 to n

6 .                  d^(m)_ij ßmin(d^(k-1)_ij , d^(k-1)_ik , + d^(k-1)_kj )

7. return D^m

Hình 26.4 nêu một số đồ thị có hướng và ma trận D^(k) đã tính toán bằng thuật toán Floyd – Warshall ở đồ thị hình 26.1

Thời gian thực hiện của thuật toán Floyd – Warshall được xác định bằng các vòng lập for  được lồng 3 trong các dòng 3-6. Mỗi lần thi hành dòng 6 mất O(1) thời gian. Do đó, thuật toán chạy trong thời gian O(n³). Như trong thuật toán chung cuộc trong đoạn 26.1, mã là chặt, không có các cấu trúc dữ liệu tinh vi, và do đó hằng ẩn trong hệ ký hiệu O là không nhỏ. Như vậy, thuật toán Floyd – Warshall khá thực tiễn với các đồ thị nhập liệu có quy mô vừa phải.

II.3.4.Kiến tạo một lộ trình ngắn nhất

Có nhiều phương pháp khác nhau để kiến tạo các lộ trình ngắn nhất trong thuật toán Floyd-Warshall. Một cách đó là tính toán ma trận D của các trọng số lộ trình ngắn nhất rồi kiến tạo ma trận phần tử tiền vị Π từ ma trận D. Phương pháp này có thể được thực thi để chạy trong O(n³) thời gian. Cho ma trận phần tử tiền vị Π, thủ tục PRINT-ALL-PAIRS-SHORTEST-PATH có thể được dùng để in các đỉnh trên một lộ trình ngắn nhất đã cho.

Ta có thể tính toán ma trận phần tử tiền vị Π trực tuyến hệt như thuật toán Floyd – Warshall tính toán các ma trận D^(k). Cụ thể, ta tính toán một dãy các ma trận Π⁽⁰⁾, Π⁽¹⁾, ……Π⁽ⁿ⁾, ở đó Π= Π⁽ⁿ⁾ và Π^(k) ij được định nghĩa là phần tử tiền vị của đỉnh j trên một lộ trình ngắn nhất từ đỉnh I với tất cả các đỉnh trung gian trong tập hợp {1, 2,…k}.

Ta có thể đưa ra một cách trình bày đệ quy của Π^(k) ij . Khi k = 0, một lộ trình ngắn nhất từ i đến j không có các đỉnh trung gian nào cả. do đó,

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Hình 1.5Dãy các ma trận D^(k) và Π^(k) được tính toán bởi thuật toán Floyd –Warshall với đồ thị trong hình 26.1.

Π⁽⁰⁾_ij =   NIL nếu i = j hoặc wij = ∞

i nếu ij và wij < ∞ 1

            Với k ≥ 1 , nếu ta lấy lộ trình i àk àj thì phần tử tiền vị của j mà ta chọn sẽ giống như phần tử tiền vị của j mà ta đã chọn trên một lộ trình ngắn nhất từ k với các đỉnh trung gian trong tập hợp {1, 2,...k-1}. Bằng không, ta cũng chọn phần tử tiền vị của j mà ta đã chọn trên một lộ trình ngắn nhất từ i với tất cả các đỉnh trung gian trong tậ hợp {1, 2,...,k-1}. Chính thức, vơi k ≥

Π^(k)_ij=  Π^(k-1)_ij  nếu  d^(k-1)_ij ≤ d^(k-1)_ik , + d^(k-1)_kj

Π^(k-1)_kj  nếu  d^(k-1)_ij > d^(k-1)_ik , + d^(k-1)_kj

            Ta để việc sát nhập các phép tính ma trận Π^(k)vào thủ tục FLOYD-WARSHALL làm bài tập 26.2-3 . Hình 26.4 có nêu dãy các ma trận Π^(k)mà thuật toán kết quả tính toán cho đò thị của hình 26.1. Bài tập cũng yêu cầu khó hơn khi phải chứng minh rằng đồ thị con phần tử tiền vị GΠ  là một cây các lộ trình ngắn nhất có gốc i. Bài 26.2-6 cũng nêu ra một cách khác để kiến tạo lại các lộ trình ngắn nhất.

II.3.5.Bao đóng bắc cầu của một đồ thị có hướng

Cho một đồ thị có hướng G = (V, E) với tập hợp đỉnh V = (1, 2,....n), ta cần tìm xem cố một lộ trình trong G từ i đến j với tất cả các cặp đỉnh i, j thuộc V hay không. Bao đóng bắc cầu của G được định nghĩa dưới dạng đồ thị G^’ = (V, E’), ở đó:

E’ = {(i,j)}: có một lộ trình từ đỉnh i đến đỉnh j trong G

Một cách để tính toán bao đóng bắc cầu của một đồ thị trong O(n³) thơờigian đó là gắn một trọng số l cho mỗi cạnh của E và chạy thuật toán Floyd – Warshall. Nếu có một lộ trình từ đỉnh i đến đỉnh j, ta có dij < n, bằng không, ta có dij = ∞.

Có một cách khác tương tự để tính toán bao đóng bắc cầu của G trong O (n³) thơờigian có thể tiết kiệm thời gian và không gian trong thực tế. Phương pháp này bao hàm việc dùng các phép toán logic thay cho các phép toán số học min và + trong thuật toán Floyd-Warshall. Với i, j, k = 1, 2,...n, ta định nghĩa t^(k)_ij là 1 nếu ở đó tồn tại một lộ trình trong đồ thị G từ đỉnh i đến đỉnh j với tất cả các đỉnh trung gian trong tập hợp {1, 2, ...k} mà bằng không là 0. Ta kiến tạo bao đóng bắc cầu G’  = (V, E’) bằng cách đặt cạnh (i, j) vào E’ nếu và chỉ nếu t^(k)_ij = 1. Một định nghĩa đệ quy về t^(k)_ij , tương tự như phép truy toán (26.5), là:

t^(k)_ij  = 0 nếu i ≠ j và (i, j) không thuộc E

1 nếu i = j hoặc (i, j) thuộc E.

Và với k ≥ 1

t^(k)_ij  = t^(k-1)_ij   v (t^(k-1)_ik  ^ t^(k-1)_kj  )

            Như trong thuật toán Floyd – Warshall, ta tính toán các ma trận T^(k) = t^(k)_ij  theo thứ tự của k tăng dần.

TRANSITIVE-CLOSURE(G)

1 n ßtrị tuyệt đối V(g)

2 For i ß1 to n

3     do for j ßto n

4           do if I = j hoặc (I,j) thuộc E(G)

5                  then t⁽⁰⁾_ij  ß1

6                  then t⁽⁰⁾_ij  ß0

7 for k ß1 to n

8     do for i ß1 to n

9         do for j ß1 to n

10              do t^(k)_ij  = t^(k-1)_ij   v (t^(k-1)_ik  ^ t^(k-1)_kj  )

11 trả về T⁽ⁿ⁾

Hình 1.6 nêu các ma trận T^(k) đã được thủ tục TRANSITIVE - CLOSURE(G) tính toán trên một đồ thị mẫu. Cũng như thuật toán Floyd – Warshall, thời gian thực hiện của thủ tục TRANSITIVE - CLOSURE(G) là O(n³). Thuy nhiên, trên vài máy tính, các phép toán logic trên các giá trị bit đơn thi hành nhanh hơn các phép toán số học trên các từ dữ liệu số nguyên. Hơn nữa, do thuật toán bao đóng bắc cầu trực tiếp chỉ sử dụng các giá trị Bool thay vì các giá trị số nguyên, yêu cầu không gian của nó nhỏ hơn của thuật toán Floyd – Warshall theo một hệ số tương ứng với kích cỡ của một kho lưu trữ máy tính.

 

 

 

 

 

 

 

 

 

 

 

                                               

 

 

 

 

 

 

Hình1.6.Một đồ thị có hướng và ma trận T^(k) đã được tính bởi thuật toán bao đóng bắc cầu