18/12/2022 05:59:51 PM

Phần mềm

PHẦN 2: THIẾT KẾ CẤU TRÚC DỮ LIỆU VÀ CÀI ĐẶT THUẬT TOÁN

1. Thiết kế CTDL

Để giải quyết các vấn đề của đồ thị bằng máy tính chúng ta cần lưu giữ đồ thị trong bộ nhớ của máy tính. Do đó chúng ta cần đưa ra các phương pháp biểu diễn đồ thị bởi các cấu trúc dữ liệu. Có nhiều phương pháp biểu diễn đồ thị: biểu diễn đồ thị bằng ma trận kề, ma trận liên thuộc, danh sách cạnh(cung) và danh sách kề.

Trong đề tài này đồ thị được lưu trữ bởi ma trận vuông COST[n][n], với n là số đỉnh của đồ thị và COST[I][J] là chi phí đi từ đỉnh i đến đỉnh j.

Ví dụ: Đồ thì sau.

Đồ thị trên được lưu vào ma trận như sau:

1 2 3 4

1 20 5 15

2 10 15 20

3 8 5 20

4 5 2 25

2. Thuật toán

Dựa vào phần lý thuyết ở trên thuật toán nhành cận được định nghĩa bởi các chương trình sau:

2.1. Hàm rút gọn

Thủ tục rút gọn:

+ Đầu vào: Ma trận chi phí C = (c_ij)

+ Đầu ra: Ma trận rút gọn và tổng hằng số rút gọn Sum

+ Thuật toán:

(i) Khởi tạo: Sum := 0;

(ii) Rút gọn dòng:

Với mỗi dòng r từ 1 đến n của ma trận C thực hiện :

- Tìm phần tử c_rj = a nhỏ nhất trên dòng.

- Trừ tất cả các phần tử trên dòng đi một lượng a.

- Cộng dồn: Sum := Sum + a

(iii) Rút gọn cột:

Với mỗi cột c từ 1 đến n của ma trận C thực hiện :

- Tìm phần tử c_ic = a nhỏ nhất trên cột.

- Trừ tất cả các phần tử trên cột đi một lượng a.

- Cộng dồn: Sum := Sum + a

+ Ví dụ. Cho ma trận chi phí của bài toán người du lịch với n = 6 như sau

1 2 3 4 5 6 a

1 ¥ 3 93 13 33 9 3

2 4 ¥ 77 42 21 16 4

3 45 17 ¥ 36 16 28 16

4 39 90 80 ¥ 56 7 7

5 28 46 88 33 ¥ 25 25

6 3 88 18 46 92 ¥ 3

Ta tiến hành rút gọn ma trận này để tìm cận dưới cho tất cả hành trình:

- Khởi tạo:

Đặt Sum := 0;

- Rút gọn các dòng:

Các phần tử nhỏ nhất trên các dòng theo thứ tự 1, 2, 3, 4, 5, 6 là 3, 4, 16, 7, 25, 3.

Trừ bớt các phần tử dòng 1, 2, 3, 4, 5, 6 đi các hằng số rút gọn tương ứng trên cột ta được ma trận

1 2 3 4 5 6

1 ¥ 0 90 10 30 6

2 0 ¥ 73 38 17 12

3 29 1 ¥ 20 0 12

4 32 83 72 ¥ 49 0

5 3 21 63 8 ¥ 0

6 0 85 15 43 89 ¥

a 0 0 15 8 0 0

Cộng dồn các hằng số rút gọn ta được

Sum := Sum + 3 + 4 + 16 + 7 + 25 + 3 = 58

- Rút gọn các cột :

Các phần tử nhỏ nhất trên các cột theo thứ tự 1, 2, 3, 4, 5, 6 là 0, 0, 15, 8, 0, 0.

Trừ bớt các phần tử cột 1, 2, 3, 4, 5, 6 đi các hằng số rút gọn tương ứng trên hàng ( ta được ma trận rút gọn) :

1 2 3 4 5 6

1 ¥ 0 75 2 30 6

2 0 ¥ 58 30 17 12

3 29 1 ¥ 12 0 12

4 32 83 58 ¥ 49 0

5 3 21 48 0 ¥ 0

6 0 85 0 35 89 ¥

Cộng dồn các hằng số rút gọn ta được

Sum := Sum + 0 + 0 + 15 + 8 + 0 + 0 = 58 + 15 + 8 = 81

Vậy cận dưới cho tất cả hành trình là b = 0 + sum = 81

(nghĩa là không có hành trình có tổng chi phí nhỏ hơn 81).

2.2. Thủ tục phân nhánh

Giả sử ta chọn cạnh phân nhánh (r, s). Như vậy các hành trình sẽ được chia làm hai tập: P₁ chứa các hành trình qua (r, s) và P₂ chứa các hành trình không qua (r,s).

+ Nhánh tập P₁ : Cận dưới b với giá trị xuất phát có từ thủ tục rút gọn.

- Giảm cấp ma trận chi phí C bằng cách loại dòng r và cột s.

- Ngăn cấm tạo hành trình con:

Cấm cạnh (s, r) bằng cách đặt c_sr = ¥.

Nếu (r, s) là cạnh phân nhánh thứ hai trở đi thì phải xét các cạnh đã chọn nối trước và sau cạnh (r,s) thành dãy nối tiếp các cạnh như hình sau

® ... ® ... ®

(i, j) ... (r, s) ... (k, h)

và cấm tất cả các cạnh dạng (h,i) bằng cách đặt c_hi = ¥.

Rút gọn ma trận chi phí ta có cận dưới b := b + (tổng hằng số rút gọn).

Ta có thể tiếp tục thủ tục phân nhánh theo nhánh này với ma trận chi phí đã được hiệu chỉnh và giảm 1 bậc. Việc chọn cạnh nào để phân nhánh ta sẽ bàn ở mục tiếp theo.

+ Nhánh tập P₂:

- Cấm cạnh (r,s) bằng cách đặt c_rs = ¥.

- Thực hiện thủ tục rút gọn với ma trận chi phí tương ứng và tính cận dưới

b := b + (tổng hằng số rút gọn) cho nhánh.

Ta có thể tiếp tục thủ tục phân nhánh theo nhánh này với ma trận chi phí đã được hiệu chỉnh cùng cận dưới tương ứng. Việc chọn cạnh nào để phân nhánh ta sẽ bàn ở mục tiếp theo.

+ Ví dụ. Xét tiếp ví dụ trên. Giả sử ta chọn cạnh phân nhánh là (r,s) = (6,3). Các hành trình sẽ được phân thành hai nhánh:

P₁ chứa các hành trình qua cạnh (6, 3) và

P₂ chứa các hành trình không qua cạnh (6, 3).

· Xét nhánh tập P₁:

- Giảm cấp ma trận chi phí C bằng cách loại dòng 6 và cột 3.

- Ngăn cấm tạo hành trình con:

Cấm cạnh (3, 6) bằng cách đặt c36 = ¥.

Ta nhận được ma trận chi phí tương ứng cùng cận dưới xuất phát b = 81.

1 2 4 5 6

1 ¥ 0 2 30 6

2 0 ¥ 30 17 12

3 29 1 12 0 ¥

4 32 83 ¥ 49 0

5 3 21 0 ¥ 0

Vì ma trận đã ở dạng rút gọn nên cận dưới vẫn giữ nguyên b = 81.

Ta có thể tiếp tục thủ tục phân nhánh theo nhánh này với ma trận chi phí đã được hiệu chỉnh. Việc chọn cạnh nào để phân nhánh ta sẽ bàn ở mục tiếp theo.

· Nhánh tập P₂ :

- Cấm cạnh (6, 3) bằng cách đặt c₆₃ = ¥.

- Thực hiện thủ tục rút gọn với ma trận chi phí tương ứng và tính cận dưới b:=b+(tổng hằng số rút gọn) cho nhánh:

1 2 3 4 5 6

1 ¥ 0 75 2 30 6

2 0 ¥ 58 30 17 12

3 29 1 ¥ 12 0 12

4 32 83 58 ¥ 49 0

5 3 21 48 0 ¥ 0

6 0 85 ¥ 35 89 ¥

a= 48

Cột thứ 3 có giảm tất cả phần tử đi phần tử nhỏ nhất c₅₃ = 48 và ta nhận được ma trận rút gọn sau:

1 2 3 4 5 6

1 ¥ 0 27 2 30 6

2 0 ¥ 10 30 17 12

3 29 1 ¥ 12 0 12

4 32 83 10 ¥ 49 0

5 3 21 0 0 ¥ 0

6 0 85 ¥ 35 89 ¥

và cận dưới

b = b + a = 81 + 48 = 129

Ta có thể tiếp tục thủ tục phân nhánh theo nhánh này với ma trận chi phí đã được hiệu chỉnh cùng cận dưới tương ứng (129). Việc chọn cạnh nào để phân nhánh ta sẽ bàn ở mục tiếp theo.

2.3. Thủ tục chọn cạnh phân nhánh

Một cách lôgic là ta chọn cạnh phân nhánh (r,s) sao cho cận dưới của nhánh không chứa (r,s) sẽ tăng nhiều nhất.

Thủ tục chọn cạnh phân nhánh (r,s)

+ Đầu vào: Ma trận rút gọn bậc k

+ Đầu ra: Cạnh phân nhánh (r,s).

+ Thuật toán:

(i) Khởi tạo: a := - ¥;

(ii) Với mỗi cặp (i,j) thoả c_ij = 0 (i=1,...,k; j=1,...,k) thực hiện

- Xác định

minr = min{c_ih : h ¹ j }

mins = min{c_hj : h ¹ i }

- Nếu a < minr + mins , đặt

a := minr + mins; r := i; s := j;

+ Ví dụ. Xét tiếp ví dụ trên. Ta đi theo nhánh P₁ , qua cạnh (6,3). Cận dưới b = 81 và ma trận chi phí tương ứng như sau

1 2 4 5 6

1 ¥ 0 2 30 6

2 0 ¥ 30 17 12

3 29 1 12 0 ¥

4 32 83 ¥ 49 0

5 3 21 0 ¥ 0

- Đặt a = - ¥.

- Xét các cặp (i,j) có c_ij = 0.

Cặp (1,2) : minr = 2; mins = 1;

a = -¥ < minr + mins = 3 ® a := 3; r := 1; s := 2;

Cặp (2,1) : minr = 12; mins = 3;

a = 3 < minr + mins = 15 ® a := 15; r := 2; s := 1;

Cặp (3,5) : minr = 1; mins = 17;

a = 15 < minr + mins = 18 ® a := 18; r := 3; s := 5;

Cặp (4,6) : minr = 32; mins = 0;

a = 18 < minr + mins = 32 ® a := 32; r := 4; s := 6;

Các cặp (5,4) và (5,6) có tổng minr + mins < a, cho nên không làm thay đổi a và (r,s).

Kết quả ta chọn được cạnh phân nhánh là (4,6).

Tập hành trình P₁ sẽ được phân thành 2 nhánh:

P₁₁ gồm các hành trình qua cạnh (4,6) và

P₁₂ gồm các hành trình không qua cạnh (4,6).

· Nhánh P₁₂: có ma trận chi phí tương ứng như sau

1 2 4 5 6

1 ¥ 0 2 30 6

2 0 ¥ 30 17 12

3 29 1 12 0 ¥

4 32 83 ¥ 49 ¥ 32

5 3 21 0 ¥ 0

Thực hiện thủ tục rút gọn ta được ma trận rút gọn

1 2 4 5 6

1 ¥ 0 2 30 6

2 0 ¥ 30 17 12

3 29 1 12 0 ¥

4 0 51 ¥ 17 ¥

5 3 21 0 ¥ 0

với tổng hằng số rút gọn a = 32 và cận dưới b = b + a = 81 + 32 = 113.

· Nhánh P₁₁:

- Loại hàng 4 và cột 6 ta có sẽ có ma trận chi phí cấp 4 tương ứng:

1 2 4 5

1 ¥ 0 2 30

2 0 ¥ 30 17

3 29 1 12 0

5 3 21 0 ¥

- Cấm tạo chu trình con:

Cạnh (6,3) chọn trước kế tiếp sau cạnh (4,6)

® ®

(4, 6) (6, 3)

Trong bước này ta cấm cạnh (3,4), bằng cách đặt c₃₄ = ¥. Ta nhận được ma trận

1 2 4 5

1 ¥ 0 2 30

2 0 ¥ 30 17

3 29 1 ¥ 0

5 3 21 0 ¥

Ma trận chi phí đã ở dạng rút gọn nên cận dưới b giữ nguyên b = 81.

Bây giờ ta tiếp tục thủ tục chọn cạnh phân nhánh, phân nhánh và rút gọn đối với P₁₁.

Thực hiện thủ tục chọn cạnh phân nhánh, ta chọn được cạnh phân nhánh (2,1) và tổng hằng số rút gọn tương ứng là 17 + 3 = 20.

Tập P₁₁₂ gồm các hành trình trong P₁₁ không qua cạnh (2,1) sẽ có cận dưới là b = b + 20 = 101.

Tập P₁₁₁ gồm các hành trình trong P₁₁ qua cạnh (2,1) sẽ có ma trận chi phí cấp 3 tương ứng, sau khi đã loại hàng 2 và cột 1:

2 4 5

1 0 2 30

3 1 ¥ 0

5 21 0 ¥

- Ngăn cấm chu trình con:

Đặt c₁₂ =¥ để cấm cạnh (1,2).

Cạnh (2,1) không nối tiếp cùng các cạnh chọn trước là (6,3) và (4,6), nên ta không phải cấm các cạnh khác. Ta có ma trận chi phí

2 4 5

1 ¥ 2 30 2

3 1 ¥ 0

5 21 0 ¥

1 a

Ma trận chi phí được rút gọn như sau

2 4 5

1 ¥ 0 28

3 0 ¥ 0

5 20 0 ¥

Cận dưới b = b + a = 81 + 3 = 84.

Tương tự ta tiếp tục thủ tục chọn cạnh phân nhánh, phân nhánh và rút gọn đối với P₁₁₁.

Chọn cạnh phân nhánh (1,4), tổng hằng số rút gọn tương ứng là 28 + 0 = 28.

Tập P₁₁₁₂ gồm các hành trình trong P₁₁₁ không qua (1,4) sẽ có cận dưới là b = b + 28 = 84 + 28 = 112.

Tập P₁₁₁₁ gồm các hành trình trong P₁₁₁ qua (1,4) sẽ có ma trận chi phí cấp 2 tương ứng:

2 5

3 ¥ 0

5 20 ¥

20 a

Cạnh (1,4) nối tiếp cùng các cạnh chọn trước là (6,3) , (4,6) và (2,1) thành dây

(2,1),(1,4),(4,6),(6,3) ,

nên ta phải cấm cạnh (3,2), bằng cách đặt c₃₂ = ¥.

Rút gọn ma trận này ta được ma trận rút gọn

2 5

3 ¥ 0

5 0 ¥

và cận dưới b = b + a = 84 + 20 = 104.

2.4. Chọn 2 cạnh cuối cùng

Mỗi hành trình có n cạnh. Sau khi đã chọn n-2 cạnh, ta phải chọn nốt 2 cạnh còn lại. Lúc này ma trận rút gọn có bậc 2 và là một trong hai dạng sau:

u v u v

p 0 ¥ p ¥ 0

q ¥ 0 q 0 ¥

(i) (ii)

cùng cận dưới b.

Trong trường hợp (i) ta chọn hai cạnh (p,u) và (q,v), còn trong trường hợp (ii) ta chọn hai cạnh (p,v) và (q,u). Tổng chi phí là b.

+ Ví dụ. Xét tiếp ví dụ trên. Sau khi chọn các cạnh (6,3),(4,6),(2,1),(1,4) ta có ma trận rút gọn

2 5

3 ¥ 0

5 0 ¥

và cận dưới b = 104. Ta chọn nốt hai cạnh còn lại là (3,5) và (5,2) và được hành trình

(1,4),(4,6),(6,3),(3,5),(5,2),(2,1)

với tổng chi phí bằng b = 104.

Quá trình trên có thể biểu diễn bằng sơ đồ sau:

Cận dưới Cận dưới

b= P b =

P₂

Tất cả hành trình

81 hành trình không chứa (6,3) 129

P₁

P₁₂

hành trình hành trình

81 chứa (6,3) không chứa (4,6) 113

P₁₁

hành trình P₁₁₂ hành trình

81 chứa (4,6) không chứa (2,1) 101

P₁₁₁

hành trình P₁₁₁₂ hành trình

84 chứa (2,1) không chứa (1,4) 112

P₁₁₁₁

hành trình

104 chứa (1,4)

Chọn tiếp hai cạnh còn lại ta có hành trình:

p = (1,4),(4,6),(6,3),(3,5),(5,2),(2,1) và chi phí c_p = 104

Qua sơ đồ trên ta thấy các nhánh P₂ , P₁₂ , P₁₁₁₂ có cận dưới lớn hơn c_p = 104, vì thế các hành trình của các nhánh đó có tổng chi phí lớn hơn c_p . Chỉ có nhánh P₁₁₂ có cận dưới là 101 nhỏ hơn c_p . Tiếp theo ta tìm hành trình mới theo nhánh này.

· Nhánh P₁₁₂ sẽ có ma trận chi phí cấp 4 tương ứng:

1 2 4 5

1 ¥ 0 2 30

2 ¥ ¥ 30 17 17

3 29 1 ¥ 0

5 3 21 0 ¥

3 a

ở đây c₂₁ = ¥ để cấm cạnh (2,1). Cận dưới xuất phát của P₁₁ là b = 81.

Rút gọn ma trận chi phí ta được ma trận

1 2 4 5

1 ¥ 0 2 30

2 ¥ ¥ 13 0

3 26 1 ¥ 0

5 0 21 0 ¥

với cận dưới b = b + a = 81 + 20 = 101.

Chọn (5,1) làm cạnh phân nhánh. Nhánh P₁₁₂₂ gồm các hành trình không qua cạnh (5,1) có cận dưới bằng 101 + 26 = 127 > 104 = c_p . Ta loại không xét nhánh này nữa.

· Nhánh P₁₁₂₁ gồm các hành trình qua cạnh (5,1) có ma trận chi phí

2 4 5

1 0 2 ¥

2 ¥ 13 0

3 1 ¥ 0

2 a

( c₁₅ = ¥ để cấm cạnh (1,5) ).

Rút gọn ma trận chi phí ta có ma trận rút gọn

2 4 5

1 0 0 ∞

2 ¥ 11 0

3 1 ¥ 0

với cận dưới b = b + α = 101 + 2 = 103.

Chọn (1,4) làm cạnh phân nhánh. Nhánh P₁₁₂₁₂ gồm các hành trình không qua cạnh (1,4) có cận dưới bằng 103 + 11 = 114 > 104 = c_p . Ta loại không xét nhánh này nữa.

· Nhánh P₁₁₂₁₁ gồm các hành trình qua cạnh (1,4) có ma trận chi phí

2 5

2 ¥ 0