17/04/2023 11:06:13 PM

Lập trình

BÀI 1: GIỚI THIỆU VỀ BÀI TOÁN NGƯỜI DU LỊCH VÀ THUẬT TOÁN NHÁNH CẬN

1.Giới thiệu bài toán người du lịch

Một người du lịch trên hệ thống n thành phố. Giữa các thành phố có thể có hoặc không các đường nối, mỗi đường nối có chi phí xác định từ trước. Người du lịch xuất phát từ một thành phố, đi tới tất cả các thành phố khác và mỗi thành phố đi qua một lần và quay trở lại thành phố ban đầu. Hãy xác định một hành trình sao cho tổng chi phí trên đường đi là nhỏ nhất.

Xét đồ thị đầy đủ G=(V,E), với V={1, 2, ..., n}, có trọng số với trọng số Cij= C(i,j) có thể khác Cji = C(j,i). Như vậy, ta có thể xem G như là một đồ thị có hướng đầy đủ “mạnh” theo nghĩa với mọi i, j=1, 2, ..., n, với mọi i<>j, luôn có (i,j), (j,i) thuộc E. Bài toán trở thành tìm chu trình Hamilton có độ dài ngắn nhất trong G.

Bài toán nổi tiếng này đã có lời giải bằng cách sử dụng phương pháp “nhánh và cận”.

2.Phương pháp nhánh và cận

Thuật toán nhánh cận là một trong các phương pháp chủ yếu giải bài toán tối ưu tổ hợp. Tư tưởng cơ bản của nó là trong quá trình tìm kiếm ta phân hoạch các phương án của bài toán ra thành hai hay nhiều tập con như là các nút của cây tìm kiếm và cố gắng đánh giá cận cho các nút, loại bỏ những nhánh mà ta biết chắc chắn là không chứa phương án tối ưu.

Xét bài toán người du lịch. Gọi

C = { c_ij : i, j = 1,2,...,n}

là ma trận chi phí. Mỗi hành trình

v = v(1)®v(2)® ... ®v(n-1)®v(n)®v(1)

có thể viết dưới dạng

v = (v(1),v(2)), (v(2),v(3)), ..., (v(n-1),v(n)), (v(n),v(1))

trong đó mỗi thành phần (v(i-1),v(i)) gọi là một cạnh của hành trình.

Trong bài toán người du lịch khi tiến hành tìm kiếm lời giải ta sẽ phân tập hành trình thành hai tập con: Một tập chứa cạnh (i,j) và tập không chứa cạnh này. Ta gọi việc đó là phân nhánh, mỗi tập con nói trên gọi là nhánh. Việc phân nhánh được minh hoạ bởi cây tìm kiếm:

Tập tất cả hành trình

Các hành trình qua (i,j)

Các hành trình không qua (i,j)

Việc phân nhánh sẽ được dựa trên qui tắc hợp lý nào đó cho phép ta rút ngắn quá trình tìm kiếm phương án tối ưu. Sau khi phân nhánh ta sẽ tính cận dưới của hàm mục tiêu trong mỗi tập con nói trên. Việc tìm kiếm sẽ tìm trên tập con có cận dưới nhỏ hơn. Thủ tục sẽ tiếp tục cho đến khi thu được hành trình đầy đủ, tức là phương án của bài toán người du lịch. Sau đó ta chỉ cần xét những tập con có cận dưới nhỏ hơn giá trị hàm mục tiêu tìm được.

3.Ma trận rút gọn

Rõ ràng tổng chi phí của một hành trình sẽ chứa đúng một phần tử trên mỗi dòng và mỗi cột của ma trận chi phí C = (c_ij). Do đó nếu ta trừ bớt mỗi phần tử của một dòng (hay một cột) đi cùng một giá trị thì chi phí của tất cả hành trình sẽ giảm đi một lượng, vì thế hành trình tối ưu sẽ không thay đổi. Vì vậy nếu tiến hành trừ bớt các phần tử của mỗi dòng và mỗi cột đi một hằng số sao cho thu được ma trận không âm và mỗi cột cũng như mỗi dòng chứa ít nhất một số 0 , thì tổng các hằng số trừ đi đó sẽ cho ta cận dưới của mọi hành trình. Thủ tục trừ bớt này gọi là thủ tục rút gọn, các hằng số trừ ở mỗi dòng (cột) gọi là hằng số rút gọn dòng (cột), ma trận thu được gọi là ma trận 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 ; (chỉ áp dụng cho ma trận chi phí ban đầu)

(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

4.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 chu 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.

5.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;

6.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 cùng cận dưới b.