Bài giảng cơ sở lập trình nâng cao

Ch

ng 7

ươ

PH

ƯƠ

Ế

Ậ

NG PHÁP THI T K Ế THU T TOÁN – THAM LAM –

N i dung

ộ

u đi m và khuy t đi m

ế

ể

§ Gi i thi u ệ ớ § Ph ng pháp ươ § S đ cài đ t ặ ơ ồ § Các ví dụ § Ư ể

Hình nhả

5

2

1

3

4

i thi u

ớ

ệ

ể

ậ ằ

ệ ệ

§ Đ nh nghĩa [Tham lam – Greedy]: Tham lam là ị t k thu t toán đ tìm m t ph ng pháp thi ế ế ươ ộ i u b ng cách xây d ng nghi m c a bài toán t ự ố ư ủ nghi m d n d n t ng b ướ ầ ừ ầ • Chúng ta luôn luôn ch n giá tr t ọ

c: ỗ ướ i th i t nh t t ấ ạ ờ i ng lai (t ố

c. T i m i b ạ ị ố đi m đó mà không quan tâm đ n t ế ươ ư

ể u c c b ) ộ ụ

ọ i u c c b ộ ụ

• Chúng ta hy v ng vi c ch n các t ệ ọ c s cho t ẽ

i m i b ố ư i u toàn c c ụ ỗ ướ ố ư t ạ

ng pháp

ươ

s bài toán yêu c u

ả ử

§ Phát bi u bài toán: Gi

tìm ph • xi đ

ể ươ ượ

•

ừ ậ

ầ ng án X=(x1, x2, …, xn), trong đó c ch n ra t ọ f(X) là hàm đánh giá s t ươ án X (f là hàm m c tiêu hay hàm chi phí)

ng t p Di. ự ố t nh t c a ph ấ ủ

ụ

ng pháp

ươ

§ Ph

ng pháp Tham lam ươ

c (k-1) thành ph n c a

ự

ủ

ầ

ta m r ng nghi m thành (x1, x2, …, xk-1,

ở ộ

ờ

t nh t trong t p

ươ • Ph c a bài toán: ủ – Ban đ u X=( ) ầ s đã xây d ng đ – Gi ượ ả ử nghi m (x1, x2, …, xk-1) ệ – Bây gi ệ ằ

ọ

ị ố

ấ

ậ

xk) b ng cách ch n xk là giá tr t Dk

ng pháp Tham lam xây d ng d n nghi m X ự ệ ầ

ng pháp

ươ

§ Ph

• Thông th

ườ ượ ắ

ầ

– B c 1 [S p x p]: S p x p d li u D tăng d n

ng pháp Tham lam c s p theo m t tr t t ng t p D đ ộ ậ ự ậ tăng d n hay gi m d n theo tiêu chí nào đó t ừ ầ ả đó giúp vi c ch n giá tr t t nh t cho xi s d ẽ ễ ọ dàng h nơ ướ

ế

ắ

ầ

ế

ữ ệ hay gi m d n theo tiêu chí nào đó

ả

ớ

ấ ấ

t nh t]: V i m i thành t nh t trong d li u đã c 1 và th a đi u ki n

ắ

ỏ

ỗ ữ ệ ề

ệ

ắ ầ – B c 2 [Ch n giá tr t ướ ị ố ọ ph n xi. Ta tìm giá tr t ị ố ầ c s p x p trong b đ ướ ế ượ c a bài toán đ gán cho xi ủ

ể

ị ố ệ ấ

S đ cài đ t ặ

ơ ồ

§ S đ 1: ơ ồ

void Greedy1() {

X=(); for (i=1; i<=n; i++) {

ị Xác đ nh Di; xi = SelectBest(Di); }

}

S đ cài đ t ặ

ơ ồ

§ S đ 2: ơ ồ

void Greedy2() {

Sort(D); for (i=1; i<=n; i++) {

ọ

ị ố - Ch n v là giá tr t t nh t trong D và

ỏ

ề

ệ

ấ th a đi u ki n bài toán

ỏ

- xi = v; - B v kh i D

}

Chú ý

ng pháp

ớ

§ M t ý t ộ

ng “trông r ng”:

ng đ i ngh ch v i ph ươ ị ộ

ố ưở “tham lam” là ý t ưở • Gom nh thành to ỏ • Năng nh t ch t b ặ ị ặ

Chú ý

i bài toán b ng ph

ng pháp tham lam,

ằ

ươ

§ Đ gi ể ả

chúng ta c n:ầ • Xác đ nh các t p giá tr Di ậ ị • Hàm m c tiêu f • Hàm ch n SelectBest đ ch n giá tr cho xi

ị

ụ ọ ể ọ ị

Các ví d : {1} Bài toán thu nh c ạ

ụ

ộ

ượ

ể

c các bài hát v i ớ ng là T. Có N bài hát, bài th i có

ứ

ờ ượ ng là hi khi l u trên đĩa (i=1, 2, …, N)

§ Ví d 1 [Bài toán thu nh c] ạ M t băng đĩa có th thu đ t ng th i l ổ th i l ờ ượ

ọ

ầ ỗ

ổ

ố

ỉ

§ Yêu c u: Hãy ch n m t cách thu các bài hát sao ộ cho m i bài ch thu m t l n và t ng s bài thu ộ ầ đ ề

c trên băng là nhi u nh t ấ

ượ

Các ví d : {1} Bài toán thu nh c ạ

ụ

i gi

i c a bài toán là 1 vector đ dài k:

ả ủ

ộ

§ Bi u di n l ễ ờ ể

X=(x1, x2, …, xk). Trong đó xi =1, 2, …, n

•

h xi

•

f(X)=|X|  max

§ Bài toán: Tìm vector X

ậ

c, bài có th i l

§ Thu t toán tham lam: • Ch n bài có th i l ờ ượ

ọ

ng nh thu tr ỏ

ướ

ờ ượ

l n thu sau n u còn ch ớ

ế

ổ

£ (cid:229)

Các ví d : {1} Bài toán thu nh c ạ

ụ

cài đ tặ

void ThuNhac_Greedy() {

}

Các ví d : {2} Bài toán cái túi

ụ

1 đ n n, đ v t

c đánh s t

§ Ví d 2 [Bài toán cái túi – 0-1 Knapsack problem] ồ ậ

ạ ồ ậ ượ

ố ừ

ế

ồ ậ ng đ v t i

Cho n lo i đ v t đ th i có ứ • vi – giá tr c a đ v t i ị ủ • wi – tr ng l ồ ậ ượ

ọ

ồ ậ ỏ

§ Yêu c u: Tìm m t s đ v t đ b vào túi sao cho ầ ộ ố ồ ậ ể ỏ t ng tr ng l t ượ ượ ọ ổ quá W và t ng giá tr c a các đ v t là l n nh t. ổ

ng các đ v t b vào túi không v ấ

ồ ậ

ị ủ

ớ

Các ví d : {2} Bài toán cái túi

ụ

i gi

ể

ả ủ

i c a bài toán là 1 vector nh ị

phân đ dài n: X=(x1, x2, …, xn). (xi{0, 1})

§ Bi u di n l ễ ờ ộ

ồ ậ ọ

ồ ậ ệ

– xi=1: Ch n đ v t i ọ – xi=0: Không ch n đ v t i • Tr ng l ầ ủ ọ • Giá tr c a nghi m thành ph n: xi*vi ệ

ng c a nghi m thành ph n: xi*wi

ượ ị ủ ầ

§ Bài toán: Tìm vector X

Các ví d : {2} Bài toán cái túi

ụ

§ Thu t toán tham lam 1:

ắ ầ ế ị ả ồ ậ

• B c 3: Xét tu n t V i đ v t th i:

các đ v t t trái sang ph i. ồ ậ ừ ầ ự ả

ọ

ậ • B c 1: S p x p các đ v t có giá tr gi m d n ướ • B c 2: ướ – TrongLuong=0 – xi=0 i ướ ớ ồ ậ – N u TrongLuong + wi < W thì ế § Ch n đ v t i: xi=1 ồ ậ § TrongLuong = TrongLuong + wi

ứ

Các ví d : {2} Bài toán cái túi

ụ

§ Thu t toán tham lam 2:

• S p x p các đ v t có giá tr tăng d n

ậ ắ

ồ ậ ế ầ ị

§ Thu t toán tham lam 3:

• S p x p các đ v t có giá tr trên 1 đ n v tr ng

ị ọ ế ơ ị

ậ ắ ượ

ậ

ng (vi/wi) gi m d n l ầ ồ ậ ả

§ Thu t toán tham lam 4:

Các ví d : {2} Bài toán cái túi

ụ

cài đ tặ

void KnapSack_Greedy() {

}

Các ví d : {3} Bài toán ng

i du l ch

ụ

ườ

ị

i du l ch – Traveling

ụ

ườ

ị

§ Ví d 3 [Bài toán ng

ố ừ

ế

c đánh s t ố

ố ượ ữ

ố

Salesman Problem – TSP] 1 đ n n và Cho n thành ph đ kho ng cách gi a thành ph i và thành ph j đ

ả c cho b i cij (chú ý: cij=cji) ượ

ở

ộ

ầ

ấ

ế

ố

ắ ỗ ề

ế

ầ

Yêu c u: Tìm m t hành trình ng n nh t cho phép vi ng thăm n thành ph , m i thành ph ố vi ng thăm đúng 1 l n và quay v thành ph ố ban đ u.ầ

Các ví d : {3} Bài toán ng

i du l ch

ụ

ườ

ị

i gi

ể

ả ủ

i c a bài toán là 1 vector đ ộ

§ Bi u di n l ễ ờ

dài n: X=(x1, x2, …, xn). (x1 =1). Trong đó (x1, x2, …, xn) là m t hoán v c a (1, 2, …, n)

ị ủ

ộ

§ Bài toán: Tìm vector X

Các ví d : {3} Bài toán ng

i du l ch

ụ

ườ

ị

thành ph s 1, t ưở

§ Thu t toán tham lam: ng: Xu t phát t ừ ấ

ố ố ạ

i m i ỗ c ta s ch n thành ph ti p theo là thành ố ế ẽ ọ

ướ ố ế

ậ • Ý t b ph ch a vi ng thăm và có kho ng cách t ư thành ph hi n t nh t ấ

• B c 1: x1=1; xn=1 • B c 2: Ch n xi là thành ph ch a đi qua và

ừ i đ n thành ph đó là nh ỏ ố ệ ạ ế ả ố

ướ ướ ư ố ọ

có kho ng cách đ n xi-1 là nh nh t. ế ấ ả ỏ

Các ví d : {3} Bài toán ng

i du l ch

ụ

ườ

ị

cài đ tặ

void TSP_Greedy() {

}

Các ví d : {4} Bài toán mã đi tu n

ụ

ầ

ụ

có m t con mã n m t

§ Ví d 4 [Bài toán mã đi tu n] ầ ộ

ờ

ạ

ằ

i m t ộ

ố ế ỉ

ể

ậ

Trên bàn c qu c t ô nào đó. Hãy ch ra 1 cách di chuy n con mã trên bàn c theo lu t đi con mã sao cho m i ô trên bàn c , con mã nh y đ n đúng m t l n. ả

ỗ ộ ầ

ờ ờ

ế

Các ví d : {4} Bài toán mã đi tu n

ụ

ầ

•

c đi h n các ô bên ẽ ướ ơ