mẹo hay

Giải bài toán bin packing bằng thuật toán tham lam

LÝ THUYẾT TỔ HỢP Combinatorial Theory Nguyễn Khánh Phương Bộ môn Khoa học Máy tính, Viện CNTT và Truyền thông, Đại học Bách khoa Hà nội, E‐mail: [email protected]

Nội dung phần 1

Chương 0. Tập hợp Chương 1. Bài toán đếm Chương 2. Bài toán tồn tại Chương 3. Bài toán liệt kê tổ hợp Chương 4. Bài toán tối ưu tổ hợp

Nội dung chi tiết

1. Giới thiệu bài toán 2. Duyệt toàn bộ 3. Thuật toán nhánh cận

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

1. Giới thiệu bài toán

1.1 Bài toán tổng quát 1.2 Bài toán người du lịch 1.3 Bài toán cái túi 1.4 Bài toán đóng thùng

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

1.1. Bài toán tổng quát • Trong rất nhiều vấn đề ứng dụng thực tế của tổ hợp, các cấu hình tổ hợp được gán cho một giá trị bằng số đánh giá giá trị sử dụng của cấu hình đối với mục đích sử dụng cụ thể nào đó. • Khi đó xuất hiện bài toán: Hãy lựa chọn trong số các cấu hình tổ hợp chấp nhận được cấu hình có giá trị sử dụng tốt nhất. Các bài toán như vậy chúng ta sẽ gọi là bài toán tối ưu tổ hợp.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Phát biểu bài toán tối ưu tổ hợp Dưới dạng tổng quát bài toán tối ưu tổ hợp có thể phát biểu như sau: Tìm cực tiểu [hay cực đại] của hàm f[x]  min [max], với điều kiện x  D, trong đó D là tập hữu hạn phần tử. Các thuật ngữ: • f[x] - hàm mục tiêu của bài toán, • x  D - phương án • D - tập các phương án của bài toán. • Thông thường tập D được mô tả như là tập các cấu hình tổ hợp thoả mãn một số tính chất cho trước nào đó. • Phương án x*D đem lại giá trị nhỏ nhất [lớn nhất] cho hàm mục tiêu được gọi là phương án tối ưu, khi đó giá trị f*=f[x*] được gọi là giá trị tối ưu của bài toán.

1. Giới thiệu bài toán

1.1 Bài toán tổng quát 1.2 Bài toán người du lịch 1.3 Bài toán cái túi 1.4 Bài toán đóng thùng

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

• •

Bài toán người du lịch [Traveling Salesman Problem – TSP] Một người du lịch muốn đi tham quan n thành phố T1, T2, ..., Tn. Hành trình là cách đi xuất phát từ một thành phố nào đó đi qua tất cả các thành phố còn lại, mỗi thành phố đúng một lần, rồi quay trở lại thành phố xuất phát. Biết cij là chi phí đi từ thành phố Ti đến thành phố Tj [i, j = 1, 2,..., n], Tìm hành trình với tổng chi phí là nhỏ nhất.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Bài toán người du lịch Ta có tương ứng 1-1 giữa một hành trình T[1]  T[2] ...  T[n]  T[1] với một hoán vị  = [[1], [2],..., [n]] của n số tự nhiên 1, 2,..., n. Đặt chi phí hành trình f[] = c[1],[2] +... + c[n-1],[n] + c[n],[1]. Ký hiÖu:  - tËp tÊt c¶ c¸c ho¸n vÞ cña n sè tù nhiªn 1, 2, ..., n.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Bài toán người du lịch • Khi đó bài toán người du lịch có thể phát biểu dưới dạng bài toán tối ưu tổ hợp sau: min { f[] :    }. • Có thể thấy rằng tổng số hành trình của người du lịch là n!, trong đó chỉ có [n-1]! hành trình thực sự khác nhau [bởi vì có thể xuất phát từ một thành phố bất kỳ, nên có thể cố định một thành phố nào đó là thành phố xuất phát].

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

1. Giới thiệu bài toán

1.1 Bài toán tổng quát 1.2 Bài toán người du lịch 1.3 Bài toán cái túi 1.4 Bài toán đóng thùng

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

1.3. Bài toán cái túi [Knapsack Problem] • Một nhà thám hiểm cần đem theo một cái túi có trọng lượng không quá b. • Có n đồ vật có thể đem theo. Đồ vật thứ j có – trọng lượng là aj và – giá trị sử dụng là cj [ j = 1, 2,..., n].

• Hỏi rằng nhà thám hiểm cần đem theo các đồ vật nào để cho tổng giá trị sử dụng của các đồ vật đem theo là lớn nhất?

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Phát biểu bài toán • Một phương án đem đồ của nhà thám hiểm có thể biểu diễn bởi vectơ nhị phân độ dài n: x = [x1, x2,..., xn], trong đó xj = 1 nếu đồ vật thứ j được đem theo và xj = 0 nếu trái lại. • Với phương án x, giá trị đồ vật đem theo là n

f [ x]   c j x j , j 1

tổng trọng lượng đồ vật đem theo là n

g [ x]   a j x j j 1

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

1.3. Bài toán cái túi Bài toán cái túi có thể phát biểu dưới dạng bài toán tối ưu tổ hợp sau: Trong số các vectơ nhị phân độ dài n thỏa mãn điều kiện g[x]  b, hãy tìm vectơ x* cho giá trị lớn nhất của hàm mục tiêu f[x]: max { f[x]: xBn, g[x]  b }.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

1. Giới thiệu bài toán

1.1 Bài toán tổng quát 1.2 Bài toán người du lịch 1.3 Bài toán cái túi 1.4 Bài toán đóng thùng

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

1.4. Bài toán đóng thùng [Bin packing] • Có n đồ vật với trọng lượng là w1, w2, ..., wn. Cần tìm cách xếp các đồ vật này vào các cái thùng có cùng dung lượng là b sao cho số thùng cần sử dụng là nhỏ nhất có thể được.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Phát biểu bài toán • Ta có thể giả thiết là: wi  b, i = 1, 2,.., n. • Do đó số thùng cần sử dụng để chứa tất cả n đồ vật là không quá n. Vấn đề là cần số thùng ít nhất. Ta sẽ mở sẵn n cái thùng. Bài toán đặt ra là hãy xác định xem mỗi một trong số n đồ vật cần được xếp vào cái thùng nào trong số n cái thùng đã mở để cho số thùng chứa đồ là ít nhất.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

1.4. Bài toán đóng thùng [Bin packing] • Đưa vào biến Bun xij = 1, nếu đồ vật i được xếp vào thùng j, 0, nếu trái lại. Khi đó bài toán đóng thùng có thể phát biểu dưới dạng: n

 sign[ x ]  min, j 1

i 1

x j 1

 1, i  1, 2,..., n

w x i 1

i ij

 b,

j  1, 2,..., n;

xij  {0,1}, i, j  1, 2,..., n. NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Nội dung chi tiết

1. Giới thiệu bài toán 2. Duyệt toàn bộ 3. Thuật toán nhánh cận

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Mô tả phương pháp • Một trong những phương pháp hiển nhiên nhất để giải bài toán tối ưu tổ hợp đặt ra là: Trên cơ sở các thuật toán liệt kê tổ hợp ta tiến hành duyệt từng phương án của bài toán, đối với mỗi phương án ta đều tính giá trị hàm mục tiêu tại nó, sau đó so sánh giá trị hàm mục tiêu tại tất cả các phương án được liệt kê để tìm ra phương án tối ưu. • Phương pháp xây dựng theo nguyên tắc như vậy có tên gọi là phương pháp duyệt toàn bộ.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Ví dụ: Giải bài toán cái túi • XÐt bμi to¸n c¸i tói biến 0-1: n

m ax{ f [ x]   c j x j : x  D}, j 1

trong ®ã D  {x  [ x1 , x2 ,..., xn ]  B n :  w j x j  b} j 1

 cj ,

wj, b là các số nguyên dương, j=1,2,…, n.

 CÇn

cã thuËt to¸n liÖt kª c¸c phÇn tö cña D NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Thuật toán quay lui liệt kê các phương án chất đồ • Xây dựng Sk: – S1={ 0, t1 }, với t1=1 nếu bw1; t1 = 0, nếu trái lại – Giả sử đã có phương án [x1, …, xk-1]. Khi đó: • Dung lượng còn lại là: bk-1= b - w1x1- …-wk-1xk-1 • Giá trị của các đồ vật chất vào túi là

fk-1= c1x1 + … + ck-1xk-1 Do đó: Sk = {0, tk}, với tk=1 nếu bk-1wk; tk = 0, nếu trái lại

• Mô tả Sk? for [y = 0; y++;y=w[i]] t=1 else t=0; //if: Trọng lượng còn lại của túi >= trọng lượng đồ vật i for [j= t; j--; j>=0] { x[i] = j; //j = 1  x[i] = 1 tức là cho đồ vật i vào túi; j = 0 x[i] = 0 tức là không cho đồ vật i vào túi bk= bk-w[i]*x[i]; //bk: trọng lượng còn lại của túi fk= fk + c[i]*x[i]; //fk: giá trị hiện tại của túi if [i == n] //nếu tất cả n đồ vật đều đã được xét { if [fk>fopt] { //nếu giá trị hiện tại của túi > giá trị tốt nhất của túi hiện có xopt:=x; fopt:=fk; //Cập nhật giá trị tốt nhất } } else KP[i+1]; //xét tiếp đồ vật thứ i+1 bk= bk+w[i]*x[i]; fk= fk - c[i]*x[i]; } } NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Bình luận • Duyệt toàn bộ là khó có thể thực hiện được ngay cả trên những máy tính điện tử hiện đại nhất. Ví dụ để liệt kê hết 15! = 1 307 674 368 000 hoán vị trên máy tính điện tử với tốc độ tính toán 1 tỷ phép tính một giây, nếu để liệt kê một hoán vị cần phải làm 100 phép tính, thì ta cần một khoảng thời gian là 130767 giây > 36 tiếng đồng hồ! 20! ===> 7645 năm NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Bình luận • Vì vậy cần phải có những biện pháp nhằm hạn chế việc tìm kiếm thì mới có hy vọng giải được các bài toán tối ưu tổ hợp thực tế. Tất nhiên để có thể đề ra những biện pháp như vậy cần phải nghiên cứu kỹ tính chất của bài toán tối ưu tổ hợp cụ thể. • Nhờ những nghiên cứu như vậy, trong một số trường hợp cụ thể ta có thể xây dựng những thuật toán hiệu quả để giải bài toán đặt ra.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Bình luận • Tuy nhiên phải nhấn mạnh rằng trong nhiều trường hợp [ví dụ trong các bài toán người du lịch, bài toán cái túi, bài toán đóng thùng] chúng ta chưa thể xây dựng được phương pháp hữu hiệu nào khác ngoài phương pháp duyệt toàn bộ.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Bình luận • Khi đó, một vấn đề đặt ra là trong quá trình liệt kê lời giải ta cần tận dụng các thông tin đã tìm được để loại bỏ những phương án chắc chắn không phải là tối ưu. • Trong mục tiếp theo chúng ta sẽ xét một sơ đồ tìm kiếm như vậy để giải các bài toán tối ưu tổ hợp mà trong tài liệu tham khảo được biết đến với tên gọi: thuật toán nhánh cận.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Nội dung chi tiết

1. Giới thiệu bài toán 2. Duyệt toàn bộ 3. Thuật toán nhánh cận

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

3. THUẬT TOÁN NHÁNH CẬN [Branch and Bound Algorithm]

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

3. Thuật toán nhánh cận

3.1. Sơ đồ chung 3.2. Ví dụ 3.2.1. Bài toán cái túi 3.2.2. Bài toán người du lịch

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

3.1. Sơ đồ chung • Thuật toán bao gồm hai thủ tục: – Phân nhánh [Branching Procedure] – Tính cận [Bounding Procedure] • Phân nhánh: Quá trình phân hoạch tập các phương án ra thành các tập con với kích thước càng ngày càng nhỏ cho đến khi thu được phân hoạch tập các phương án ra thành các tập con một phần tử • Tính cận: Cần đưa ra cách tính cận cho giá trị hàm mục tiêu của bài toán trên mỗi tập con A trong phân hoạch của tập các phương án.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

3.1. Sơ đồ chung • Ta sẽ mô tả tư tưởng của thuật toán trên mô hình bài toán tối ưu tổ hợp tổng quát sau min { f[x] : x  D }, trong đó D là tập hữu hạn phần tử. • Giả thiết rằng tập D được mô tả như sau D = {x = [x1, x2, ..., xn]  A1 A2 ...  An: x thoả mãn tính chất P}, với A1, A2, ..., An là các tập hữu hạn, còn P là tính chất trên tích Đề các A1  A2  ...  An. NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Nhận xét • Yêu cầu về mô tả của tập D là để có thể sử dụng thuật toán quay lui để liệt kê các phương án của bài toán. • Bài toán max {f[x]: x  D} là tương đương với bài toán min {g[x]: x  D}, trong đó g[x] = -f[x] Do đó ta có thể hạn chế ở việc xét bài toán min.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Phân nhánh Quá trình phân nhánh được thực hiện nhờ thuật toán quay lui:

[] D a11 1 1

[a ] D [ a11 ]

n1 1

... a [a12 ] . . . 2 2 1

D [ a1 ]

n1 1

[a ] D [ a1n1 ]

trong ®ã D[a1i ]  {x  D : x1  a1i }, i  1, 2,..., n1 i 1

lμ tËp c¸c ph−¬ng ¸n cã thÓ ph¸t triÓn tõ pabp [a ] Ta có phân hoạch:

D  D[a11 ]  D[a12 ]  ...  D[a1n1 ]

Ph©n nh¸nh • Như vậy ta có thể đặt tương ứng mỗi phương án bộ phận [a1, a2, ..., ak] với một tập con các phương án của bài toán: D[a1,..., ak]= { xD: xi = ai , i = 1,..., k }. • Ở bước tổng quát của thuật toán quay lui ta sẽ làm việc với phương án bộ phận [a1, a2, ..., ak] và xét các cách tiếp tục phát triển phương án này. • Điều đó tương đương với việc phân hoạch tập D ra thành các tập con nhỏ hơn.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Ph©n nh¸nh • Quá trình phân nhánh có thể diễn tả như sau: [ ] D[a1,…,ak]

ak21

a1k 1

...

p k 1

D[a1 ,..., ak , a1k 1 ] 

Ta cã ph©n ho¹ch: p

D[a1 ,..., ak ]   D[a1 ,..., ak , aki 1 ] i 1

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Tính cận • Cần có hàm g xác định trên tập tất cả các phương án bộ phận của bài toán thoả mãn bất đẳng thức sau: Giá trị hàm mục tiêu của mọi lời giải có k thành phần đầu tiên là [a1, a2,…,ak]

g[a1,..., ak]  min{f[x]: xD[a1, ..., ak]} [*] với mỗi phương án bộ phận cấp k [a1, a2, ..., ak], và với mọi k = 1, 2, ...

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Tính cận • Bất đẳng thức [*] có nghĩa là giá trị của hàm g tại phương án bộ phận [a1, a2, ..., ak] là không vượt quá giá trị nhỏ nhất của hàm mục tiêu của bài toán trên tập con các phương án D[a1,..., ak]= { xD: xi = ai , i = 1,..., k }, hay nói một cách khác, g[a1, a2, . . . , ak] là cận dưới của giá trị hàm mục tiêu trên tập D[a1, a2, ..., ak].

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Tính cận • Vì lẽ đó, hàm g được gọi là hàm cận dưới, và giá trị g[a1, a2, . . . , ak] được gọi là cận dưới của tập D[a1, a2, ..., ak]. • Do có thể đồng nhất tập D[a1,..., ak] với phương án bộ phận [a1,..., ak], nên ta cũng gọi giá trị g[a1,..., ak] là cận dưới của phương án bộ phận [a1,..., ak].

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Cắt nhánh nhờ sử dụng cận dưới • Giả sử đã có hàm g. Ta xét cách sử dụng hàm này để giảm bớt khối lượng duyệt trong quá trình duyệt tất cả các phương án theo thuật toán quay lui. • Trong quá trình liệt kê các phương án có thể đã thu được một số phương án của bài toán. Gọi x là phương án với giá trị hàm mục tiêu nhỏ nhất trong số các phương án đã tìm được, ký hiệuf = f[x ]. • Ta sẽ gọi • x là phương án tốt nhất hiện có [phương án kỷ lục], • f là giá trị tốt nhất hiện có [giá trị kỷ lục].

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Cắt nhánh nhờ sử dụng cận dưới • Giả sử đã có f , khi đó nếu g[a1, a2, ..., ak] > f , thì từ bất đẳng thức [*] suy ra

f < g[a1,..., ak]  min{f[x]: x  D[a1,...,ak]}, Vì thế tập D[a1,..., ak] chắc chắn không chứa phương án tối ưu và có thể loại bỏ khỏi quá trình duyệt.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Cắt nhánh nhờ sử dụng cận dưới

[a1,…,ak-1] 1 k

1 k 1

2 k 1

ak2

...

akp

akq1

g[a1,..., ak] là cận dưới của phương án bộ phận [a1,..., ak]

Thuật toán nhánh cận void Branch[int k] { // Phát triển phương án bộ phận [x1, x2, ..., xk‐1] for akAk if [akSk ] { xk = ak; if [k == n] ; else if [g[x1,..., xk]  f ] Branch[k+1]; } } NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Thuật toán nhánh cận void BranchAndBound [ ] { f = +; // Nếu biết p/ánx nào đó thì đặtf = f[x ] Branch[1]; if [f ; else if [g[a1,..., ak]  f ] Branch[k+1]; bởi if [k == n] then < Cập nhật kỷ lục>; else Branch[k+1]; thì ta thu được thuật toán duyệt toàn bộ.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Chú ý: g[a1,..., ak]  min{f[x]: xD[a1, ..., ak]} [*] • Việc xây dựng hàm g phụ thuộc vào từng bài toán tối ưu tổ hợp cụ thể. Thông thường ta cố gắng xây dựng nó sao cho: – Việc tính giá trị của g phải đơn giản hơn việc giải bài toán tối ưu tổ hợp ở vế phải của [*]. – Giá trị của g[a1,..., ak] phải sát với giá trị của vế phải của [*]. • Rất tiếc là hai yêu cầu này trong thực tế thường đối lập nhau.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

3. Thuật toán nhánh cận

3.1. Sơ đồ chung 3.2. Ví dụ 3.2.1. Bài toán cái túi 3.2.2. Bài toán người du lịch

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

3.2.1. Bài toán cái túi [Knap sack] • Có n loại đồ vật. • Đồ vật loại j có – trọng lượng aj và – giá trị sử dụng là cj [j = 1, 2,..., n] .

• Cần chất các đồ vật này vào một cái túi có trọng lượng là b sao cho tổng giá trị sử dụng của các đồ vật chất trong túi là lớn nhất.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

3.2.1. Bài toán cái túi [Knap sack] • Đưa vào biến số xj – số lượng đồ vật loại j được chất vào túi, j=1,2, ..., n • Mô hình toán học của bài toán có dạng sau: Tìm n

j 1

f  max { f [ x]   c j x j :  a j x j  b, x j  Z  , j  1, 2,..., n } *

trong đó Z+ là tập các số nguyên không âm Bài toán cái túi biến nguyên

• Kí hiệu D là tập các phương án của bài toán: n

D  {x  [ x1 ,..., xn ] :  a j x j  b, x j  Z  , j  1, 2,..., n } j 1

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Xây dựng hàm cận trên • Giả thiết rằng các đồ vật được đánh số sao cho bất đẳng thức sau được thoả mãn: c1 /a1  c2 / a2  . . .  cn / an . [có nghĩa là các đồ vật được xếp theo thứ tự không tăng của giá trị một đơn vị trọng lượng] • Để xây dựng hàm tính cận trên, cùng với bài toán cái túi [KP] ta xét bài toán cái túi biến liên tục [KPC] sau đây: Tìm n

j 1

g  max { f [ x]   c j x j :  a j x j  b, x j  0, j  1, 2,..., n } *

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Xây dựng hàm cận trên • Mệnh đề. Phương án tối ưu của bài toán KPC là vectơx = [x1 ,x2 , ...,xn ] với các thành phần được xác định bởi công thức:  x1 = b / a1 , x2 = x3 = . . . = xn = 0. và giá trị tối ưu là g* = c1b /a1.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Chứng minh. Xét x = [x1,..., xn] là một phương án tuỳ ý của bài toán KPC. Khi đó cj  [c1 / a1 ] aj , j = 1, 2, ..., n do xj  0, ta suy ra cj xj  [c1 / a1 ] aj xj , j = 1, 2, ..., n. • Từ đó ta có n

 c x   [c / a ] a x j 1

j 1

 [c1 / a1 ] a j x j j 1

 [c1 / a1 ]b  g *

Mệnh đề được chứng minh.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Tính cận trên • Bây giờ, giả sử ta có phương án bộ phận cấp k: [u1, u2, ..., uk]. Khi đó giá trị sử dụng của các đồ vật đang có trong túi là k = c1u1 + c2u2 + . . . + ckuk và trọng lượng còn lại của cái túi là bk = b – [a1u1 + a2u2 + . . . + akuk].

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Tính cận trên • Ta có

max{ f [ x] : x  D, x j  u j , j  1, 2,..., k}  max { k 

cx :ax

j  k 1 n

  k  max {  c j x j : j  k 1

j  k 1

 bk , x j  Z  , j  k  1, k  2,..., n}

 bk , x j  0, j  k  1, k  2,..., n}

ax

j  k 1

  k  ck 1bk / ak 1.

• Vậy ta có thể tính cận trên cho phương án bộ phận [u1, u2, ..., uk] bởi công thức g[u1, u2,..., uk] = k + ck+1 bk / ak+1.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Tính cận trên • Chó ý: Khi tiÕp tôc x©y dùng thμnh phÇn thø k+1 cña lêi gi¶i, c¸c ứng cö viên cho xk+1 sÏ lμ 0, 1, ..., [bk / ak+1 ]. • Do cã kÕt qu¶ cña mÖnh ®Ò, khi chän gi¸ trÞ cho xk+1 ta sÏ duyÖt c¸c ứng cö viên theo thø tù gi¶m dÇn.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Ví dụ

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

• Quá trình giải bài toán được mô tả trong cây tìm kiếm. Thông tin về một phương án bộ phận trên cây được ghi trong các ô trên hình vẽ tương ứng theo thứ tự sau: – các thành phần của phương án bộ phận, –  - giá trị của các đồ vật đang chất trong túi, – w – trọng lượng còn lại của túi, – g – cận trên của phương án bộ phận.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

f[x] = 10 x1 + 5 x2 + 3 x3 + 6 x4  max, 5 x1 + 3 x2 + 2 x3 + 4 x4  8, xj  Z+ , j =1, 2, 3, 4.

Gốc,

Chọn đồ vật 1: 8/5 = 1

x1 = 0

x1 = 1

[0];  = 0 w = 8; g = 0 +5*8/3 = 40/3

[1]  = 10 w = 8‐5=3; g = 10 +5*3/3 = 15

x2 = 1 Chọn đồ vật 2: 3/3 = 1 [1,1];  = 10+5=15 w = 3-3 = 0; g = 15

x2 = 0 [1,0];  = 10+0=10 w = 3; g = 10+3*3/2=14.5

x3 = 0 Chọn đồ vật 3: 0/2 = 0

[1,1,0];  = 15 w = 0; g = 15

x4 = 0

• Chọn đồ vật 4: 0/4 = 0

Kết thúc thuật toán, ta thu được: – Phương án tối ưu: x* = [1, 1, 0, 0], – Giá trị tối ưu: f* = 15.

3. Thuật toán nhánh cận

3.1. Sơ đồ chung 3.2. Ví dụ 3.2.1. Bài toán cái túi 3.2.2. Bài toán người du lịch Sir William Rowan Hamilton 1805 - 1865 NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

• •

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

3.2.2. Bài toán người du lịch Cố định thành phố xuất phát là T1, bài toán người du lịch dẫn về bài toán: • Tìm cực tiểu của hàm f[1,x2,..., xn] = c[1,x2]+c[x2,x3]+...+c[xn-1,xn] + c[xn,1] với điều kiện [1, x2, x3, ..., xn] là hoán vị của các số 1, 2, ..., n.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Hàm cận dưới • Ký hiệu cmin = min { c[i, j] , i, j = 1, 2, ..., n, i  j } là chi phí đi lại nhỏ nhất giữa các thành phố. • Cần đánh giá cận dưới cho phương án bộ phận [1, u2, ..., uk] tương ứng với hành trình bộ phận đã đi qua k thành phố: T1  T[u2]  . . .  T[uk-1]  T[uk].

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Hàm cận dưới • Chi phí phải trả theo hành trình bộ phận này là  = c[1,u2] + c[u2, u3] + ... + c[uk-1, uk]. • Để phát triển thành hành trình đầy đủ: 1

T1  T[u2]  . . .  T[uk-1]  T[uk]  T[uk+1]  T[uk+2]  …..  T[un]  T1

ta còn phải đi qua n-k+1 đoạn đường nữa, mỗi đoạn có chi phí không ít hơn cmin, nên cận dưới cho phương án bộ phận [1, u2, ..., uk] có thể tính theo công thức: g[1, u2, ..., uk] =  + [n-k+1] cmin .

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Ví dụ Giải bài toán người du lịch với ma trận chi phí sau:

C =

0 3 14 3 0 4 17 9 0 9 20 7 9 15 11

18 22 16 0 5

15 20 4 18 0

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

• Ta có cmin = 3. Quá trình thực hiện thuật toán được mô tả bởi cây tìm kiếm lời giải. • Thông tin được ghi trong các ô trên hình vẽ theo thứ tự sau: – các thành phần của phương án bộ phận, –  là chi phí theo hành trình bộ phận, – g – cận dưới của phương án bộ phận.

NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN

Gốc,

[2]  = 3 g = 3 + 4*3 = 15 [2,3];  =3 + 4 = 7 g = 7 + 3*3 = 16

[3];  = 14 g = 14 +4*3 = 26 [2,4];  =3 + 22 = 25 g = 25 + 3*3 = 34

[2,3,4];  =7 +16 = 23 g = 23 + 2*3 = 29

[2,3,5];  =7 +4 = 11 g = 11 + 2*3 = 17

[2,3,4,5];  =23 + 18 = 41

[2,3,5,4];  =11 + 5 = 16

[4];  = 18 g = 18 +4*3 = 30

[5];  = 15 g = 15 +4*3 = 27

[2,5];  =3 + 20 = 23 g = 23 + 3*3 = 32

0 3 14 18 15 3 0 4 22 20 17 9 0 16 4 9 20 7 0 18 9 15 11 5 0

Kết quả Kết thúc thuật toán, ta thu được: - phương án tối ưu [1, 2, 3, 5, 4, 1] tương ứng với hành trình T1  T2  T3  T5  T4  T1 , - chi phí nhỏ nhất là 25.

Bài Viết Liên Quan

Toplist mới

Bài mới nhất

Chủ Đề