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

Chia sẻ: Hoangtuan Hoangtuan | Ngày: | Loại File: DOC | Số trang:7

Thêm vào BST

Báo xấu

189
lượt xem 27
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 t ươ ng ứng mà đ ộ l ệch không v ượ t quá đ ộ l ệch c ủa ph ươ ng án. Trong đó các h ọc sinh và áo trong các nhóm này không nh ất thi ết ph ải đ ượ c s ắp x ếp. V ới t ư t ưở ng này, bài t oán c ủ a chúng ta bây gi ờ s ẽ tr ở thành: − Xác đ ị nh đ ộ l ệch nh ỏ nh ất c ủa các ph ươ ng án tho ả mãn đ ầu bài. Mà theo nh ậ n xét trên, đ ộ l ệch này có th ể là là |Mip-Miv| ho ặc | Map-Mav|. T ươ ng đ ươ ng v ới vi ệc tìm ph ần t ử l ớn nh ất và nh ỏ nhấ t cho mỗ i dãy kích c ỡ vai h ọc sinh và dãy kích c ỡ vai áo. − Xác đ ị nh giá tr ị kích th ướ c vai h ọc sinh (vai áo) làm tiêu trí đ ể phân nhóm. III. Xây dự ng gi ải thu ật a. T ư tưở ng gi ả i thu ậ t Tìm cách phân các cái áo và h ọc sinh vào cùng m ột nhóm sao cho h ọc m ột h ọ c sinh bấ t kỳ trong nhóm có th ể đ ượ c phân ph ối b ất kỳ m ột áo nào trong n hóm mà đ ộ l ệ ch không v ượ t quá đ ộ l ệch c ủa d ph ươ ng án. b. Ph ư ơ ng án thự c hi ện Ở đ ây tôi ch ỉ đi phân tích và xây d ựng gi ải thu ật cho tr ường h ợp 1 khi Mi v Map . Các tr ườ ng h ợp khác t ươ ng t ự. Mi p Mav B1: Tìm các giá tr ị Ma v , Map , Mi v , Mi p . Trong đó  5 Hoµng Anh TuÊn - C H21CNTT Vinh
* 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 − Tìm Ma v , Map , Mi v , Mi p . Gi ả i thu ậ t tìm c ỡ l ớn nh ất và bé nh ất n ày c ó đ ộ ph ứ c t ạ p O(n). Th ực t ế có s ố phép duy ệt là 2n. − Tậ p các ph ươ ng án tho ả mãn đ ầu bài s ẽ có đ ộ l ệch là d=Map-Mav. − Ta sẽ đi tìm m ộ t ph ươ ng án trong t ập này. B2: Phân nhóm.  − Nh ậ n th ấ y r ằng vi ệc phân nhóm ph ải tho ả mãn yêu c ầu sau: * Đ ộ l ệch gi ữ a kích c ỡ vai áo nh ỏ nh ất và kích c ỡ vai h ọc sinh l ớ n nhấ t trong nhóm (th ực ch ất là 2 nhóm áo và h ọc sinh có th ể ghép đôi v ớ i nhau) không v ượ t quá d. * Đ ộ l ệch gi ữ a kích c ỡ vai h ọc sinh nh ỏ nh ất và kích c ỡ vai áo l ớ n nhấ t cũng không v ượ t quá d. * Số l ượ ng cái áo và h ọc sinh trong cùng nhóm ph ải b ằng nhau Size Ma p d Ma v d d Mi p Mi v 1 i j n − Nhóm th ứ i s ẽ ch ứa cái áo có kích c ỡ bé Miv i ( có th ể đ ượ c xác đ ịnh nhờ b ướ c xác đ ịnh đo ạn tr ướ c), ch ứa h ọc sinh có c ỡ vai l ớn nh ất l à Map i = Miv i +d. Ch ứ a h ọc sinh có c ỡ vai bé nh ất Mip i ( có th ể đ ượ c xác đ ị nh nh ờ b ướ c xác đ ịnh đo ạn tr ướ c). V ấn đ ề ở đây là xác đ ị nh kích c ỡ l ớn nh ất Mav i củ a nh ữ ng cái áo trong đo ạn này. Mav i có th ể đ ượ c xác đ ịnh b ằng cách duy ệt h ết các cái áo ch ưa đ ượ c phân nhóm xem c ỡ vai c ủa cái áo nào g ần v ới c ỡ vai Map i nhấ t nh ư ng v ẫn nh ỏ h ơ n Map i thì đó chính là Mav i 6 Hoµng Anh TuÊn - C H21CNTT Vinh
IV. Đánh giá gi ải thu ật xây d ựng đ ượ c Ta v ẫn ch ỉ xét tr ườ ng h ợp 1 Mi v Mi p Mav Map . Vớ i gi ả i thuậ t xây d ựng nh ư trên ta có m ột s ố nh ận xét sau  − Vớ i d=Map-Mav − Khi d=0 s ẽ suy bi ến sang tr ườ ng h ợp 5 nh ưng lúc này hai đ ườ ng trùng nhau, t ức là v ới m ỗi h ọc sinh ta đ ều tìm đ ượ c m ột cái áo có c ùng c ỡ vai. (Vì ta đa gi ả thi ết các c ỡ vai áo đôi m ột khác nhau và c ỡ vai c ủa h ọ c sinh đôi m ột khác nhau). Gi ải thu ật này không có l ờ i gi ả i. Ta ph ả i th ực hi ện gi ải thu ật nh ư ở ph ần II ho ặc gi ải thuậ t t ươ ng đ ươ ng v ớ i s ố phép duy ệt là (n-1)n (O(n 2 )). − Khi d=1. Gi ả i thu ật có l ời gi ải nh ưng v ới s ố phép duy ệt là (n-1)n ( O(n 2 )). − Khi d > 1. Gi ải thu ật có l ời gi ải v ới phép duy ệt càng nh ỏ khi d c àng l ớ n. 7 Hoµng Anh TuÊn - C H21CNTT Vinh