BÀI TẬP LỚN MÔN HỌC PHÂN TÍCH ĐÁNH GIÁ THUẬT TOÁN

Người ta may sẵn cái áo với các kích thước vai V(1), V(2), …, V(n) cho n học sinh. Các học sinh này được đánh số từ 1 tới n và có kích thước vai là p(1), p(2), …, p(n). Nếu học sinh i được nhận áo j thì độ lệch vai cho trường hợp này sẽ là |V(i)-p(j)|. Một phương án phân phối áo cho các học sinh 1, 2, ...n được mô tả như một hoán vị p1, p2, ..., pn với hàm ý học sinh i nhận được áo pi. Độ lệch của phương án này được định nghĩa bằng...
Nội dung trích xuất từ tài liệu:
BÀI TẬP LỚN MÔN HỌC PHÂN TÍCH ĐÁNH GIÁ THUẬT TOÁN MỤ C L Ụ C I. Bài toán (Đ ề 24) .................................................................................................. 2 I I. Phân tích bài toán ...............................................................................................2 I II. Xây d ựng gi ải thu ậ t .........................................................................................5 a . T ư t ưở ng gi ả i thu ật ............................................................................................................... 5 b . Ph ươ ng án th ự c hi ện ............................................................................................................. 5 I V. Đánh giá gi ải thu ật xây d ựng đ ượ c ..............................................................7 1 Hoµng Anh TuÊn - C H21CNTT Vinh BÀI TẬP LỚN MÔN HỌC PHÂN TÍCH ĐÁNH GIÁ THU ẬT TOÁN I. Bài toán (Đ ề 24) Ngườ i ta may s ẵ n n c ái áo v ớ i các kích th ướ c vai V(1), V(2), …, V(n) cho n họ c sinh. Các h ọc sinh này đ ượ c đánh s ố t ừ 1 t ới n và có kích th ướ c vai là p (1), p(2), …, p( n). Nế u h ọc sinh i đ ượ c nhậ n áo j thì đ ộ l ệch vai cho tr ườ ng h ợ p này s ẽ là |V( i )-p( j )|. Mộ t ph ươ ng án phân ph ối áo cho các h ọc sinh 1, 2, ... n đ ượ c mô t ả nh ư mộ t hoán v ị π 1 , π 2 , ..., π n vớ i hàm ý h ọ c sinh i nhậ n đ ượ c áo π i . Đ ộ l ệ ch c ủ a ph ươ ng án này đ ượ c đ ịnh nghĩa b ằng max { |V(i) – p( π i )|, i=1,2,..., n} II. Phân tích bài toán Không mấ t tính t ổ ng quát ta gi ả s ử: − Các c ỡ vai áo đôi m ột khác nhau − Các c ỡ vai c ủa h ọ c sinh đôi m ột khác nhau. Sắ p x ế p n cái áo theo chi ều không gi ảm c ủa kích c ỡ vai, s ắp x ếp các h ọc s inh theo chi ều không gi ảm c ủa kích c ỡ vai. S ử d ụng đ ồ th ị v ới đ ườ ng nét đ ậm b i ể u th ị giá tr ị kích c ỡ vai áo, đ ườ ng nét m ảnh bi ểu th ị kích c ỡ vai c ủa h ọc s inh. Ta có các tr ườ ng h ợp sau có th ể x ảy ra: − Tr ườ ng hợ p 1: Size Ma p Ma v Mi p Mi v 1 n Tr ườ ng h ợ p 1 * Miv − Tr ườ ng hợ p 2: Size Ma p Ma v Mi p Mi v 1 n Tr ườ ng h ợ p 2 * |Miv Size Ma p Ma v Mi v Mi p 1 n Tr ườ ng h ợ p 5 Trong đó − Mav : Là giá tr ị l ớn nh ấ t c ủa vai áo − Mi v: Là giá tr ị nh ỏ nh ấ t c ủa vai áo − Map : Là kích th ướ c l ớ n nh ất c ủa vai h ọc sinh − Mi p : Là kích th ướ c nh ỏ nh ất c ủa vai h ọc sinh Nh ậ n xét r ằng trong khi đ ổi vai trò c ủa áo và h ọc sinh ta s ẽ đ ượ c các t r ườ ng h ợ p t ươ ng t ự . Từ các tình hu ố ng trên ta d ự đoán m ột ph ươ ng án phân phát áo cho h ọc s inh nh ư sau: − S ắ p x ếp n họ c sinh theo th ứ t ự không gi ảm c ủa kích th ướ c vai, đ ánh s ố t ừ 1 đ ến n theo th ứ t ự đó . (1) − S ắ p x ếp n cái áo theo th ứ t ự không gi ảm c ủa kích th ước vai, đánh s ố t ừ 1 đ ế n n theo th ứ t ự đó. (2) − Lầ n l ượ t phát áo cho h ọc sinh theo quy t ắc: H ọc sinh th ứ 1 đ ược nhậ n áo th ứ 1… Họ c sinh th ứ n nh ận áo th ứ n. (3) Rõ ràng ph ươ ng án phân ph ối áo nh ư trên là tho ả mãn yêu c ầu đ ầu bài, v ới đ ộ l ệ c có th ể là |Mip-Miv| ho ặc |Map-Mav| tuỳ t ừng tr ườ ng h ợp. Nh ư v ậy c húng ta có th ể tìm ra m ột l ời gi ải cho bài toán theo cách trên. Nh ưng gi ải thu ật n ày có nh ững h ạ n ch ế là: − Mộ t là: Vi ệ c s ắp x ếp h ọc sinh và áo theo m ột tr ật t ự nào đó là m ột v ấ n đ ề khó khăn và t ốn kém (O(n 2 )). Gi ả s ử ta ph ả i phân ph ối kho ả ng 10000 chi ếc áo cho 10000 h ọc sinh. Thông th ườ ng đ ể s ắp x ế p họ c sinh và áo nh ư trên chúng ta th ườ ng dùng ph ươ ng pháp s ắ p x ế p chèn ho ặc ch ọn. Khi đó, tr ườ ng h ợp x ấu nh ất ta ph ải 4 Hoµng Anh TuÊn - C H21CNTT Vinh dùng đ ế n 10000(10000-1) phép duy ệt qua các ph ần t ử (H ọc sinh và áo) ch ư a kể thao tác chèn và phân ph ối áo cho h ọc sinh.  49995000 phép duy ệt. Gi ả s ử m ỗi phép duy ệt m ất ½ giây ta s ẽ mấ t x ấ p x ỉ 578 ngày (Hơn một năm r ưỡ i) cho 1 ng ườ i th ực hi ện vi ệ c này. − Hai là: M ộ t h ọc sinh i không nh ất thi ết ph ải nh ận đ ượ c áo i mà có th ể nhậ n mộ t cái áo j b ất kỳ nào đó mi ễn là đ ộ l ệch |V(j)-P(i)| không v ượ t quá đ ộ l ệch c ủa ph ươ ng án. Nh ư v ậy vi ệc s ắp x ếp t ất c ả c ác ph ần t ử áo vào h ọc sinh s ẽ là không c ần thi ết trong đa s ố c ác tr ườ ng hợ p c ủa d ữ li ệu đ ầu vào. − Ba là: Ph ả i s ắp x ếp c ả hai dãy.  Từ nh ữ ng nh ận xét trên chúng ta nghĩ đ ến vi ệc phân nhóm h ọc sinh, phân nhóm áo sao cho m ột h ọc sinh b ất kỳ trong nhóm h ọc sinh có th ể nh ậ n bấ t kỳ mộ t cái áo nào trong nhóm áo ...