Luận văn:Nghiên cứu kết hợp thuật toán cặp ghép và tham lam giải quyết bài toán thời khóa biểu trường chuyên

Chia sẻ: Nguyen Vang | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

128
lượt xem 21
download

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

Thuật toán ghép cặp của Edmonds (còn gọi là thuật toán bông hoa) là một thuật toán trong lý thuyết đồ thị để tìm cặp ghép cực đại trong đồ thị. Thuật toán được tìm ra bởi Jack Edmonds năm 1961,[1] và xuất bản năm 1965.[2] Cho trước một đồ thị vô hướng G = (V, E), thuật toán tìm ra cặp ghép M sao cho mỗi đỉnh trong V kề với tối đa một cạnh trong M và |M| là lớn nhất có thể. Cặp ghép được xây dựng bằng cách khởi đầu từ cặp ghép rỗng và tăng...

Chủ đề:

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

Lưu

Nội dung Text: Luận văn:Nghiên cứu kết hợp thuật toán cặp ghép và tham lam giải quyết bài toán thời khóa biểu trường chuyên

1 B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG ĐOÀN CƯ NG NGHIÊN C U K T H P THU T TOÁN C P GHÉP VÀ THAM LAM GI I QUY T BÀI TOÁN TH I KHÓA BI U TRƯ NG CHUYÊN Chuyên ngành : KHOA H C MÁY TÍNH Mã s : : 60.48.01 TÓM T T LU N VĂN TH C SĨ K THU T Đà N ng - Năm 2011
2 Công trình ñư c hoàn thành t i Đ I H C ĐÀ N NG Ngư i hư ng d n khoa h c: TS. Nguy n Thanh Bình Ph n bi n 1: PGS.TS. Lê Văn Sơn Ph n bi n 2: TS. Trương Công Tu n Lu n văn ñư c b o v trư c H i ñ ng ch m Lu n văn t t nghi p th c sĩ k thu t h p t i Đ i h c Đà N ng vào ngày 18 tháng 06 năm 2011 * Có th tìm hi u lu n văn t i: - Trung tâm Thông tin - H c li u, Đ i h c Đà n ng - Trung tâm H c li u, Đ i h c Đà N ng.
3 M Đ U 1. LÝ DO CH N Đ TÀI Vi c chia th i khóa bi u (TKB) cho các Trư ng THPT Chuyên trên toàn qu c là v n ñ h t s c khó khăn. Vì trư ng chuyên có nh ng ñ c thù riêng bi t: ñ i v i trư ng chuyên m i h c kỳ ph i chia thành nhi u giai ño n, t i m i giai ño n s ti t d y c a t ng b môn ph i có s thay ñ i ñ ñáp ng ñư c ti n ñ c a t ng b môn chuyên, nên t t c các trư ng chuyên ñ u ph i làm th công, d n ñ n k t qu không m y kh quan. Hi n có m t s ph n m m x p TKB c a C c Công ngh Thông tin, hay m t s t ch c khác dành cho trư ng THPT bình thư ng nhưng hi u qu không cao, không ñáp ng ñư c nhu c u c a t ng giáo viên. Vì v y, các trư ng này ph i t làm th công, còn n u áp d ng cho trư ng chuyên thì không th ñư c. Công ngh Thông tin ñã và ñang trên ñà phát tri n m nh m trên toàn c u, nhưng vi c chia th i khóa bi u cho t t c các trư ng THPT trên toàn qu c nói chung, trư ng THPT chuyên nói riêng v n ph i làm th công, nên hi u qu không cao, l i m t r t nhi u th i gian và công s c. Bài toán ñ t ra là v n ñ x p th i khóa bi u cho trư ng THPT chuyên, v i nhi u cơ s khác nhau. C n có s s p x p l ch h c cho các l p t i các phòng m i ñ a ñi m, sao cho v a h p lý l i v a ti n d ng nh t, phù h p v i t ng b môn chuyên. Bài toán bao g m t t c các v n ñ có liên quan ñ n vi c x p th i khóa bi u trư ng THPT chuyên, ch ng h n ñ t l p h c vào m t phòng sao cho tương ng v s c ch a c a nó, tránh vi c h c trùng gi t i m t phòng c a các l p; giáo viên s d y theo gi quy ñ nh trong b ng phân công, ñ m b o quy ch c a B Giáo d c &
4 Đào t o. Thông thư ng, công vi c này ñư c làm b ng tay, t t nhiên chúng ta luôn th c hi n ñư c và cho ra k t qu tương ñ i t t, nhưng ph i m t nhi u th i gian và ít nh t ph i có kinh nghi m x p l ch n u không mu n có sai sót x y ra, ch ng h n như: ch này th a phòng, ch khác l i thi u, sai ch , sai gi ,... V n ñ c a bài toán là ngoài vi c th c hi n ñúng, chính xác, còn ph i t t hơn, nhanh hơn và hi u qu hơn công vi c x p l ch b ng tay mà chúng ta v n ph i làm. Trư ng THPT chuyên Lê Quý Đôn có nhi u ñ c trưng riêng. Nhu c u ñ n l p c a giáo viên khác nhau, m t s ngư i thích ñ n l p trong m t s ngày nào ñó trong tu n, nên vi c x p TKB cũng có nhi u ñi m khác so v i các Trư ng THPT khác. Chính vì lý do này, ñ tài nghiên c u thu t toán c p ghép và áp d ng nó ñ làm sao th a mãn m t cách t t nh t các nhu c u c a giáo viên. Ví d khi chia TKB cho l p ghép là m t v n ñ , gi s có l p v a chuyên Anh v a chuyên Pháp, thì t i m t s th i ñi m ph i có 2 giáo viên cùng d y cho l p này nhưng ph i ñ m b o các tính ch t c a m t l p chuyên. Xu t phát t nh ng lý do trên mà tôi ñã ch n ñ tài “Nghiên c u k t h p thu t toán c p ghép và tham lam gi i quy t bài toán th i khóa bi u trư ng chuyên” ng d ng t i Trư ng THPT chuyên Lê Quý Đôn, có gi i pháp và chương trình, s n ph m c th làm ñ tài lu n văn t t nghi p th c sĩ c a mình. Chương trình ñư c xây d ng và ng d ng s giúp hoàn thi n hơn ki n th c ñư c h c và có ý nghĩa khoa h c, th c ti n cao. 2. M C TIÊU VÀ NHI M V NGHIÊN C U - M c tiêu
5 o Hoàn thành s n ph m là m t chương trình chia th i khóa bi u Trư ng THPT Chuyên Lê Quý Đôn. o Ti p t c phát tri n ng d ng chia th i khóa bi u cho t t c các trư ng THPT Chuyên, THPT trên toàn qu c. - Nhi m v o Phân tích các ñ c thù riêng bi t có s li u c a t t c các trư ng chuyên trên toàn qu c, ñ ra gi i pháp h p lý trong vi c xây d ng và tri n khai h th ng. o Nghiên c u k t h p thu t toán c p ghép và tham lam gi i quy t bài toán th i khóa bi u Trư ng THPT chuyên Lê Quý Đôn. o Phân tích, ñánh giá và ñ ra gi i pháp chia th i khoá bi u m t cách t ñ ng và chính xác. o Nghiên c u, ng d ng công ngh dotNet, ngôn ng C# trong ti n trình xây d ng h th ng. o Xây d ng s n ph m hoàn thi n s d ng t i Trư ng THPT chuyên Lê Quý Đôn. 3. PHƯƠNG PHÁP NGHIÊN C U - Tư li u: T ng h p các tài li u liên quan ñ n thu t toán c p ghép và tham lam, cũng như các quy ch trư ng chuyên. - Phân tích: Phân tích quy ch trư ng chuyên, xác ñ nh các yêu c u c a t ng ñ i tư ng c th . - Th c nghi m: Xây d ng chương trình chia th i khóa bi u và xu t ra t p Excel, tích h p v i CSDL c a Phòng giáo v .
6 T ng h p l i h th ng ñ ñưa th i khóa bi u lên WebSite c a Trư ng chuyên Lê Quý Đôn Đà N ng. 4. Ý NGHĨA KHOA H C VÀ TH C TI N C A Đ TÀI - V m t lý thuy t: Đ tài nghiên c u giúp hi u rõ hơn v s k t h p thu t toán c p ghép và thu t toán tham lam. - V m t th c ti n: Xây d ng m t chương trình ph c v nhu c u th c hi n chia th i khóa bi u t ñ ng nh m gi m th i gian và chi phí b ng tay như hi n nay. 5. N I DUNG C A LU N VĂN Lu n văn ñư c trình bày có 3 chương chính. Chương 1: Mô hình bài toán th i khóa bi u trư ng chuyên Chương này trình bày t ng quan bài toán th i khóa bi u t i các trư ng THPT, THPT chuyên trên toàn qu c, cũng như các ph n m m th i khóa bi u hi n có t i Vi t Nam và trên th gi i. Chương 2: K t h p thu t toán c p ghép và tham lam gi i quy t bài toán th i khóa bi u Trong chương này trình bày cơ s lý thuy t c a thu t toán c p ghép và thu t toán tham lam, gi i pháp k t h p c a hai thu t toán này vào vi c gi i quy t bài toán th i khóa bi u trư ng chuyên. Chương 3: Xây d ng chương trình và th nghi m Tri n khai m t chương trình máy tính cài ñ t ph n m m th i khóa bi u trư ng chuyên ñư c th hi n chi ti t; th nghi m và ñánh giá các k t qu ñ t ñư c thông qua vi c áp d ng thu t toán c p ghép và tham lam, t ñ ng hóa bài toán TKB
7 trư ng chuyên và các ch c năng tinh ch nh th công, nh m t o ra m t th i khóa bi u tinh v ch t, áp d ng t t cho trư ng chuyên trên toàn qu c.
8 CHƯƠNG 1 – BÀI TOÁN TH I KHÓA BI U TRƯ NG THPT CHUYÊN Bài toán x p th i khóa bi u ñã t lâu tr thành m t bài toán n i ti ng và thu hút ñư c s quan tâm c a r t nhi u nhà nghiên c u, nhi u chuyên gia trong các lĩnh v c liên quan. S "n i ti ng" c a bài toán này không ch ñư c ño b i ñ ph c t p c a v n ñ , mà còn tính th c ti n, kh năng áp d ng r t cao trên th c t . B t c m t nhà trư ng nào, th i khóa bi u h c t p c a h c sinh và gi ng d y c a giáo viên ñã và luôn là b xương s ng cơ b n nh t k t n i h u như toàn b các ho t ñ ng c a nhà trư ng. Chính vì l ñó bài toán x p th i khóa bi u tr thành m t trong nh ng v n ñ chính và quan tr ng vào b c nh t c a m i nhà trư ng. Hi n nay Vi t Nam có kho ng 25 000 trư ng ph thông t Ti u h c ñ n THCS và THPT và có nghĩa là s có t i thi u t ng ñó giáo viên ñang làm nhi m v x p th i khóa bi u. X p th i khóa bi u th c s là m t công vi c khó. Cái khó ñây ñư c th hi n theo 3 lý do sau: Th nh t, vi c x p TKB là m t vi c ñòi h i tư duy, suy lu n, tính toán r t ph c t p, r t d nh m l n, trùng gi trùng ti t. Ph i là ngư i có kinh nghi m và hi u bi t v công vi c này m i làm ñư c. Th hai, ngư i x p th i khóa bi u là ngư i "làm dâu trăm h ", r t khó có th ñáp ng ñư c các nhu c u khác nhau c a toàn b ñ i ngũ giáo viên trong trư ng. Các ràng bu c c a giáo viên trong nhà trư ng l i r t mâu thu n, ch ng chéo l n nhau. Th ba, công vi c x p TKB ñòi h i m t s tư duy ñ c bi t, r t ñ c thù c a "ngh x p TKB". Không ph i ai cũng có th rèn luy n ñ có nh ng kinh nghi m và tư duy này. Ngư i x p TKB, ngoài vi c ph i
9 r t am hi u v các chương trình môn h c, hi u rõ tính n t và yêu c u c a các giáo viên trong nhà trư ng, còn ph i có ñư c nh ng tư duy ngh nghi p c a công vi c x p th i khóa bi u [16]. Trong chương này chúng tôi trình bày các v n ñ s p x p TKB t i các trư ng THPT trên toàn qu c, gi i thi u t ng quan bài toán TKB trư ng chuyên, các ph n m m th i khóa bi u hi n có t i Vi t Nam và th gi i. 1.1. V N Đ S P X P TH I KHÓA BI U TRƯ NG THPT 1.1.1. Dùng phương pháp th công ñ s p x p th i khóa bi u Trư ng THPT 1.1.2. Dùng ph n m m ñ s p x p TKB Trư ng THPT 1.2. S P X P TH I KHÓA BI U TRƯ NG THPT CHUYÊN Bài toán s p x p TKB là m t bài toán khó. Vi c chia th i khóa bi u cho các Trư ng THPT Chuyên trên toàn qu c l i càng h t s c khó khăn. Vì trư ng chuyên có nh ng ñ c thù riêng bi t; ñ i v i trư ng chuyên m i h c kỳ ph i chia thành nhi u giai ño n, t i m i giai ño n s ti t d y c a t ng b môn ph i có s thay ñ i ñ ñáp ng ñư c ti n ñ c a t ng b môn chuyên, nên t t c các trư ng chuyên ñ u ph i làm th công, d n ñ n k t qu không m y kh quan. M c dù hi n nay Công ngh Thông tin phát tri n r t m nh, ñã gi i quy t ñư c nhi u ng d ng trong cu c s ng, nhưng chưa có thu t toán nào t i ưu ñ gi i quy t ñư c bài toán th i khóa bi u. Các ph n m m s p x p TKB hi n nay, chưa có ph n m m nào áp d ng ñư c cho trư ng THPT chuyên trên toàn qu c nói chung, trư ng THPT chuyên Lê Quý Đôn nói riêng. Vì v y, t i các trư ng này ph i dùng tay ñ s p x p TKB nên t n r t nhi u th i gian và
10 công s c, nh t là ngư i s p x p TKB ph i hi u sâu s c v chuyên môn, cách phân chia s ti t c th cho t ng b môn chuyên, n m ñư c quy ch trư ng chuyên cũng như các ñ c thù c a t ng giáo viên d y chuyên, h ph i bi t phân chia theo t ng giai ño n ñ ñáp ng k p th i ti n ñ và theo k p yêu c u c a B Giáo d c và Đào t o. T ñó m i th c hi n vi c chia TKB cho phù h p, cu i cùng cho ra ñư c m t TKB tương ñ i t t, tuy nhiên ph i m t r t nhi u th i gian và công s c. 1.2.1. Gi i thi u bài toán T nh ng hi n tr ng khó khăn trong v n ñ gi i quy t bài toán TKB trư ng THPT chuyên cũng như h th ng THPT chuyên trong ñ i h c (g i t t là trư ng chuyên), chúng tôi ch n “Nghiên c u k t h p thu t toán c p ghép và tham lam gi i quy t bài toán th i khóa bi u trư ng chuyên” v i b d li u th c c a trư ng THPT chuyên Lê Quý Đôn làm d li u c s ñ gi i quy t bài toán TKB trong lu n văn này. Bài toán ñ t ra là v n ñ x p th i khóa bi u cho trư ng THPT chuyên Lê Quý Đôn v i nhi u c s khác nhau, c n có s s p x p l ch h c cho các l p t i các phòng m i ñ a ñi m, sao cho v a h p lý l i v a ti n d ng nh t, phù h p v i t ng b môn chuyên. Bài toán ñ t ra bao g m t t c các v n ñ có liên quan ñ n vi c x p th i khóa bi u trư ng THPT chuyên Lê Quý Đôn, ch ng h n như: ñ t l p h c vào m t phòng sao cho tương ng v s c ch a c a nó, tránh vi c h c trùng gi t i m t phòng c a các l p, nh t là nh ng l p ghép; giáo viên s d y theo gi qui ñ nh trong b ng phân công. Thông thư ng, công vi c này ñư c làm b ng tay, t t nhiên chúng ta luôn th c hi n ñư c và luôn cho ra k t qu tương ñ i t t, nhưng ph i m t nhi u th i gian và ít nh t ph i có kinh nghi m x p l ch n u
11 không mu n có sai sót x y ra, ch ng h n như: ch này th a phòng, ch khác l i thi u, sai ch , sai gi ... .V n ñ c a bài toán là ngoài vi c th c hi n ñúng, chính xác, còn ph i t t hơn, nhanh hơn và hi u qu hơn công vi c x p l ch b ng tay mà chúng ta v n ph i làm. Trư ng THPT chuyên Lê Quý Đôn là trư ng có nhi u ñ c trưng riêng, nên vi c x p TKB cũng có nhi u ñi m khác so v i các trư ng THPT khác. Khi chia TKB cho l p ghép là m t v n ñ c n quan tâm. L p ghép chuyên Anh - Pháp, thì t i m t th i ñi m ph i có hai giáo viên cùng d y cho l p này t i hai phòng khác nhau nhưng ph i ñ m b o các tính ch t c a m t l p chuyên. Đ i v i giáo viên là nam có ñ tu i t 50 tr lên ho c giáo viên n có ñ tu i l n hơn 40 thì không ñư c phép d y 4 ti t liên t c trên m t bu i. Hay ñ i v i giáo viên là n có con nh hơn 18 tháng tu i thì không ñư c d y ti t ñ u hay ti t cu i m i bu i. Đi u ñáng nói ñây là ph i làm th nào ñó mà TKB cho m i giáo viên ph i ñư c cho là t t nh t. 1.2.2. Phát bi u bài toán Ngay khi v n ñ ñư c ñ t ra, chúng ta ñã th y bài toán ph i ñư c gi i quy t trên hai n n t ng cơ b n: nghi p v và k thu t. Mu n ñ c hi u ñư c m t thông tin c a th i khóa bi u, yêu c u d li u ph i ñư c hi n th ñ y ñ , không thi u sót, không b sai l ch, ph i phù h p v i nghi p v ñ ra. Ph n k thu t cũng v y, ph i x lý t t c nh ng yêu c u riêng bi t t các ñ i tư ng g i ñ n, chúng ñư c xem như là thành ph n ràng bu c c a bài toán, b t bu c v n ñ ph i th a mãn và ñáp ng hoàn toàn. Vì v y, chúng tôi s phân tích bài toán trên hai thành ph n ñó.
12 1.2.3. D li u bài toán Như ñã nói trên, thông tin s phát sinh t các ñ i tư ng chính trong bài toán. Do ñó, các d li u luôn có m i liên h v i nhau, ph n l n vì nhu c u nghi p v mà d li u xu t hi n tương ñ i nhi u. Trong bài toán x p th i khóa bi u c a trư ng THPT chuyên Lê Quý Đôn, c th s ñòi h i các thông tin sau: - Danh sách cơ s o Danh sách giáo viên. o Danh sách khóa h c (Kh i 10, Kh i 11, Kh i 12). o Danh sách l p h c: o Danh sách phòng h c (30 phòng, chia làm khu A, khu B và khu C). o Danh sách môn h c và s ti t h c do B Giáo d c và Đào t o quy ñ nh. o Danh sách môn h c và s ti t h c do trư ng ñi u ch nh (theo t ng giai ño n). o Danh sách 12 môn h c b t bu c cho các l p: Toán, Lý, Hóa, Sinh, Tin, Văn, S , Đi , Anh, Pháp, Công Dân, Nông Nghi p/Công Nghi p. o Danh sách môn chuyên cho t ng l p: Toán h c,V t Lý, Hóa h c, Sinh h c, Tin h c, Ng Văn, L ch S , Đi Lí,Ti ng Anh, Ti ng Pháp. - B ng phân công giáo viên gi ng d y t i các l p. - B ng yêu c u ràng bu c c a giáo viên v i l ch d y. - B ng yêu c u ràng bu c c a l p v i l ch h c. - B ng yêu c u ràng bu c c a phòng v i l ch s d ng.
13 1.2.3.1. Các ñ i tư ng s d ng Các ñ i tư ng chính y u xung quanh mô hình x p th i khóa bi u, chính là thành ph n ñ y ñ tính năng c a chương trình trong bài toán. T t c ñư c li t kê như sau: - Giáo viên, - L p h c, - Môn h c, - Phòng h c, - S ti t. 1.2.3.2. M i quan h gi a các ñ i tư ng Trên l ch l p h c, th hi n rõ thông tin các ñ i tư ng liên quan nhau t i th i ñi m ti t h c, t t c cùng n m trong m t b ng này. Hay nói cách khác b ng l ch l p h c là ph n th hi n m i quan h c a các ñ i tư ng: giáo viên, l p h c và môn h c. Sau này l p h c ñ t trong m t l ch cơ s c th , gây phát sinh m i, t o quan h th hai, gi a l p h c và phòng h c. Đó là m i quan h l ch cơ s . 1.2.4. Các ràng bu c bài toán Trong mô hình bài toán, các ñ i tư ng có nh ng yêu c u, ràng bu c riêng bi t khác nhau v i công vi c c a mình, và ñư c nh p vào kèm theo ngay khi ñ i tư ng xu t hi n. Song song ñó, v i nghi p v l ch th c thi, có r t nhi u thông s , và m i quan h các ñ i tư ng t o ra m t ràng bu c chung, như là b lu t th ng nh t trong toàn h th ng. Ph n m m TKB ph i th a mãn các ràng bu c dư i ñây: - M i giáo viên có ràng bu c riêng. - M i l p h c có ràng bu c riêng.
14 - M i phòng h c có ràng bu c riêng. - Môn h c t i m t l p không xu t hi n trong b ng l ch l p nhi u l n. - Giáo viên và môn h c trong cùng m t l p không xu t hi n trong b ng l ch l p nhi u l n. - T i m t th i ñi m không xu t hi n nhi u l p h c t i m t phòng trong b ng l ch cơ s . - S c ch a c a phòng ph i l n hơn ho c b ng s h c sinh có trong l p h c mà ñư c x p h c phòng ñó. - T i m t th i ñi m l p duy nh t h c m t môn. - M i l p h c ch h c trong m t bu i. - S ti t h c c a m t môn trong 1 l n, ph i theo qui ñ nh; t i ña 2 ti t trong m t l n h c, còn ñ i v i l p h c các môn chuyên thì ph i h c liên ti p 4 ti t. 1.2.4.1. Ràng bu c d li u nh p vào 1.2.4.2. Ràng bu c nghi p v - th i gian 1.2.4.3. Ràng bu c nghi p v - chuyên môn 1.2.4.4. Các yêu c u ch c năng 1.2.5. Các yêu c u phi ch c năng 1.3. CÁC CÔNG C H TR HI N T I 1.3.1. Ph n m m th i khóa bi u t i Vi t Nam 1.3.2. Ph n m m th i khóa bi u trên th gi i
15 1.4. T NG K T CHƯƠNG 1 T hi n tr ng c a bài toán th i khóa bi u trư ng THPT nói chung, trư ng chuyên trên toàn qu c nói riêng, ñã cho chúng ta th y ñư c: Hi n nay, Công ngh Thông tin ñang trên ñà phát tri n r t m nh và ñã ng d ng nhi u vào trong cu c s ng, nhưng v n chưa có thu t toán nào t i ưu ñ gi i quy t bài toán th i khóa bi u. Vì v y, chúng tôi ch n k t h p thu t toán c p ghép và thu t toán tham lam gi i quy t bài toán TKB trư ng chuyên. CHƯƠNG 2 – K T H P THU T TOÁN C P GHÉP VÀ THAM LAM GI I QUY T BÀI TOÁN TH I KHÓA BI U T nh ng yêu c u b c thi t c a trư ng THPT chuyên Lê Quý Đôn nói riêng, trư ng chuyên trên toàn qu c nói chung, áp d ng các ph n m m TKB hi n có trên th trư ng vào vi c s p x p TKB cho các trư ng chưa ñư c t t, chúng tôi ñã ch n k t h p thu t toán c p ghép và thu t toán tham lam gi i quy t bài toán TKB v i hai lý do chính sau: th nh t, thu t toán c p ghép dùng ñ th a mãn ràng bu c c a t ng giáo viên; Th hai, thu t toán tham lam dùng ñ ch n các c p giáo viên bư c x p thô TKB ñ u tiên. Trong chương này chúng ta trình bày cơ s lý thuy t c a thu t toán c p ghép và thu t toán tham lam, gi i pháp k t h p c a hai thu t toán này vào vi c gi i quy t bài toán th i khóa bi u trư ng chuyên. 2.1. THU T TOÁN C P GHÉP 2.1.1. Bài toán phân công 2.1.2. Phân tích bài toán 2.1.3. Thu t toán
16 2.1.3.1. Các khái ni m - Đư ng pha (Alternating Path) - M t ñư ng m (Augmenting Path) 2.1.3.2. Thu t toán Hungari (c p ghép) Bư c 1: Kh i t o: M t b ghép M := Ø Bư c 2: V i m i ñ nh x* ∈ X, ta tìm cách ghép x* như sau: B t ñ u t ñ nh x* chưa ghép, th tìm ñư ng m b t ñ u x* b ng thu t toán tìm ki m trên ñ th (BFS ho c DFS - thông thư ng nên dùng BFS ñ tìm ñư ng qua ít c nh nh t) có hai kh năng x y ra: - Ho c tìm ñư c ñư ng m thì d c theo ñư ng m , ta lo i b nh ng c nh ñã ghép kh i M và thêm vào M nh ng c nh chưa ghép, ta ñư c m t b ghép m i nhi u hơn b ghép cũ 1 c nh và ñ nh x* tr thành ñã ghép. - Ho c không tìm ñư c ñư ng m thì do ta s d ng thu t toán tìm ki m trên ñ th nên có th xác ñ nh ñư c hai t p: o VisitedX = {T p nh ng X_ñ nh có th ñ n ñư c t x* b ng m t ñư ng pha} o VisitedY = {T p nh ng Y_ñ nh có th ñ n ñư c t x* b ng m t ñư ng pha} G i ∆ là tr ng s nh nh t c a các c nh n i gi a m t ñ nh thu c VisitedX v i m t ñ nh không thu c VisitedY. D th y ∆ > 0 b i n u ∆ = 0 thì t n t i m t 0_c nh (x, y) v i x ∈ VisitedX và y ∉ VisitedY. Vì x* ñ n ñư c x b ng m t ñư ng pha và (x, y) là m t 0_c nh nên x* cũng ñ n ñư c y b ng m t ñư ng pha, d n t i y ∈ VisitedY, ñi u này vô lý.
17 Bi n ñ i ñ th G như sau: V i ∀ x ∈ VisitedX, tr ∆ vào tr ng s nh ng c nh liên thu c v i x, V i ∀ y ∈ VisitedY, c ng ∆ vào tr ng s nh ng c nh liên thu c v i y. L p l i th t c tìm ki m trên ñ th th tìm ñư ng m xu t phát x* cho t i khi tìm ra ñư ng m . Bư c 3: Sau bư c 2 thì m i X_ñ nh ñ u ñư c ghép, in k t qu v b ghép tìm ñư c. Mô hình cài ñ t c a thu t toán Hungari có th vi t như sau: ; for (x* ∈ X) do begin repeat ; if then ; until ; ; end; ;[4] 2.1.3.3. Cài ñ t thu t toán - Phương pháp ñ i ng u Kuhn-Munkres - Sơ ñ cài ñ t phương pháp Kuhn-Munkres 2.1.3.4. Bi u di n b ghép 2.1.3.5. Tìm ñư ng m 2.2. THU T TOÁN THAM LAM 2.2.1. Khái ni m
18 2.2.2. Thu t toán 2.2.2.1. Phương pháp 2.2.2.2. C u trúc t ng quát c a thu t toán Thamlam(C:t p h p các ng c viên) // hàm tr v gi i pháp t i ưu, g m các ng c viên Begin S=Ø //S là gi i pháp t i ưu While ( C ≠ Ø và S chưa là gi i pháp) do X = ch n( C) // ch n x t t p c theo tiêu chí c a hàm ch n C = C – {x} If (S U {x} có tri n v ng là gi i pháp) then S:=S U {x} Endif Endwhile if (S là l i gi i) then return S else return 0 endif end 4 [1] 2.2.2.3. Ví d áp d ng[1] 2.2.2.4. Tính ch t c a chi n lư c tham lam [1] 2.3. GI I PHÁP T NG TH CHO BÀI TOÁN TKB Thu t toán c p ghép ñóng vai trò quan tr ng trong quá trình gi i quy t bài toán TKB trư ng chuyên. Vì v y, trư c tiên chúng ta c n c i ti n thu t toán c p ghép. 2.3.1. C i ti n thu t toán c p ghép 2.3.2. Đánh giá ñ ph c t p
19 2.3.3. Gi i pháp k t h p Bài toán th i khóa bi u có th ñư c ñ nh nghĩa là m t bài toán tìm ki m chu i t i ưu ñ th c hi n m t t p các ho t ñ ng ch u tác ñ ng c a m t t p các ràng bu c c n ph i ñư c th a mãn. Ngư i làm nhi m v chia th i khóa bi u thư ng c g ng th ñ n m c t i ña s s d ng các cá th , máy móc và t i thi u th i gian ñòi h i ñ hoàn thành toàn b quá trình nh m s p x p l ch. Vì th bài toán th i thóa bi u là m t v n ñ r t khó ñ gi i quy t. Hi n nay có nhi u kh năng ñ phát tri n các k thu t hi n ñ i ñ gi i quy t bài toán này. Nh ng k thu t ñó bao g m: các ti p c n Trí tu nhân t o như h th ng tri th c cơ s (knowledge-based systems), bài toán tho mãn ràng bu c, h chuyên gia, m ng Nơron và các ti p c n c a các Nghiên c u ho t ñ ng: l p trình tính toán, quy ho ch ñ ng, tìm ki m nhánh và ñư ng biên, k thu t mô ph ng, tìm ki m Tabu và phương pháp nút c chai. ñây chúng tôi ch n k t h p thu t toán c p ghép và thu t toán tham lam nh m gi i quy t bài toán th i khóa bi u trư ng chuyên v i b d li u th c c a Trư ng THPT chuyên Lê Quý Đôn làm cơ s ñ gi i quy t bài toán th i khóa bi u. - Trong khi gi i quy t bài toán th i khóa bi u trư ng chuyên c n chú ý ñ n gi i pháp k t h p thu t toán c p ghép và tham lam ñ gi i quy t tùy theo t ng trư ng h p c th mà có th s d ng thu t toán tham lam hay k t h p tính tham lam trong khi dùng thu t toán c p ghép. - Bư c ñ u ta ch n nh ng c p ghép g m các giáo viên có cùng chung s ti t là l n nh t trong m t bu i d y ñ ghép l i v i nhau trư c theo t ng c p c th . Nh m ñưa các c p ghép này
20 vào cho vi c chia th i khóa bi u trư c, nh m t o ñư c s ưu tiên s m t cho các c p ghép này. - Bư c ti p theo ta ch n các giáo viên có s ti t d y ít d n t o nên c p ghép ñ ng th i ta s d ng thu t toán tham lam ñ quét t t c các giáo viên có s ti t d y ñơn trên m t l p trong t ng bu i c th ñ t o nên gi i pháp t t hơn. - T i bư c này ta s d ng thu t toán c p ghép cùng v i tham lam ñ t o nên vi c tinh ch nh t t d n, t c làm m n d n. - Sau cùng ta ch n t t c s ti t còn l i c a t ng giáo viên c th ñ t o nên c p ghép t t hơn, ñ ng th i t ñó ta ñưa ra ñư c k t qu ñ u ra tương ñ i t t hơn. - Vi c gi i quy t bài toán th i khóa bi u trư ng chuyên là nhu c u c n thi t nh t hi n nay, tuy nhiên chúng ta c n v n d ng các thu t toán ñã nêu trên m t cách thu n th c nh t. Cũng như k t h p tri t ñ thu t toán c p ghép và tham lam thì m i có th cho ra k t qu t t hơn t các t p ng viên ñã ch n. Đ u vào là danh sách c a giáo viên theo t b môn, s ti t th c d y theo t ng bu i c a giáo viên ñó. Sau khi ñưa vào x lý b i s k t h p c a hai thu t toán trên thì ph i cho ra k t qu ñ u ra t t hơn k t qu hi n nay ñang có. Xu t phát t nh ng ý tư ng trên, chúng tôi ñã ch n s k t h p thu t toán c p ghép và tham lam nh m tìm ra gi i pháp t t hơn cho vi c gi i quy t bài toán th i khóa bi u trư ng chuyên. V i b d li u c a trư ng THPT chuyên Lê Quý Đôn làm d li u cơ s . 2.4. T NG K T CHƯƠNG 2 Trong chương này, chúng tôi ñã trình bày ñư c cơ s lý thuy t cũng như các gi i pháp k t h p c a thu t toán c p ghép và tham lam