Thuật toán và giải thuật - Hoàng Kiếm Part 1

Chia sẻ: Mr Yukogaru | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

216
lượt xem 60
download

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

Tổng quan thuật toán thuật giải trong qua trình nghiêng cứu giải quyết các vấn đề - bài taosn, người ta đã dưa ra những nhận xét sau : Có nhiều bài toán cho đến nay vẫn chưa tìm ra một cách giải theo kiểu thuật toán và cũng không biết có tồn tại thuật toán hay không có nhiều bài toán đã có thuật toán để giải nhưng không chấp nhận được vì thời gian giải theo thuật toán đó quá lớn hoặc các điều kiện cho thuật toán khó đáp ứng....

Chủ đề:

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

Lưu

Nội dung Text: Thuật toán và giải thuật - Hoàng Kiếm Part 1

CHƯƠNG 1 : THU T TOÁN – THU T GI I I. KHÁI NI M THU T TOÁN – THU T GI I II. THU T GI I HEURISTIC III. CÁC PHƯƠNG PHÁP TÌM KI M HEURISTIC III.1. C u trúc chung c a bài toán tìm ki m III.2. Tìm ki m chi u sâu và tìm ki m chi u r ng III.3. Tìm ki m leo i III.4. Tìm ki m ưu tiên t i ưu (best-first search) III.5. Thu t gi i AT III.6. Thu t gi i AKT III.7. Thu t gi i A* III.8. Ví d minh h a ho t ng c a thu t gi i A* III.9. Bàn lu n v A* III.10. ng d ng A* gi i bài toán Ta-canh III.11. Các chi n lư c tìm ki m lai I. T NG QUAN THU T TOÁN – THU T GI I Trong quá trình nghiên c u gi i quy t các v n – bài toán, ngư i ta ã ưa ra nh ng nh n xét như sau: Có nhi u bài toán cho n nay v n chưa tìm ra m t cách gi i theo ki u thu t toán và cũng không bi t là có t n t i thu t toán hay không. Có nhi u bài toán ã có thu t toán gi i nhưng không ch p nh n ư c vì th i gian gi i theo thu t toán ó quá l n ho c các i u ki n cho thu t toán khó áp ng. Có nh ng bài toán ư c gi i theo nh ng cách gi i vi ph m thu t toán nhưng v n ch p nh n ư c. T nh ng nh n nh trên, ngư i ta th y r ng c n ph i có nh ng i m i cho khái ni m thu t toán. Ngư i ta ã m r ng hai tiêu chu n c a thu t toán: tính xác nh và tính úng n. Vi c m r ng tính xác nh i v i thu t toán ã ư c th hi n qua 1 Sưu t m b i: www.daihoc.com.vn
các gi i thu t quy và ng u nhiên. Tính úng c a thu t toán bây gi không còn b t bu c i v i m t s cách gi i bài toán, nh t là các cách gi i g n úng. Trong th c ti n có nhi u trư ng h p ngư i ta ch p nh n các cách gi i thư ng cho k t qu t t (nhưng không ph i lúc nào cũng t t) nhưng ít ph c t p và hi u qu . Ch ng h n n u gi i m t bài toán b ng thu t toán t i ưu òi h i máy tính th c hiên nhi u năm thì chúng ta có th s n lòng ch p nh n m t gi i pháp g n t i ưu mà ch c n máy tính ch y trong vài ngày ho c vài gi . Các cách gi i ch p nh n ư c nhưng không hoàn toàn áp ng y các tiêu chu n c a thu t toán thư ng ư c g i là các thu t gi i. Khái ni m m r ng này c a thu t toán ã m c a cho chúng ta trong vi c tìm ki m phương pháp gi i quy t các bài toán ư c t ra. M t trong nh ng thu t gi i thư ng ư c c p n và s d ng trong khoa h c trí tu nhân t o là các cách gi i theo ki u Heuristic II. THU T GI I HEURISTIC Thu t gi i Heuristic là m t s m r ng khái ni m thu t toán. Nó th hi n cách gi i bài toán v i các c tính sau: Thư ng tìm ư c l i gi i t t (nhưng không ch c là l i gi i t t nh t) Gi i bài toán theo thu t gi i Heuristic thư ng d dàng và nhanh chóng ưa ra k t qu hơn so v i gi i thu t t i ưu, vì v y chi phí th p hơn. Thu t gi i Heuristic thư ng th hi n khá t nhiên, g n gũi v i cách suy nghĩ và hành ng c a con ngư i. Có nhi u phương pháp xây d ng m t thu t gi i Heuristic, trong ó ngư i ta thư ng d a vào m t s nguyên lý cơ b n như sau: Nguyên lý vét c n thông minh: Trong m t bài toán tìm ki m nào ó, khi không gian tìm ki m l n, ta thư ng tìm cách gi i h n l i không gian tìm ki m ho c th c hi n m t ki u dò tìm c bi t d a vào c thù c a bài toán nhanh chóng tìm ra m c tiêu. Nguyên lý tham lam (Greedy): L y tiêu chu n t i ưu (trên ph m vi toàn c c) c a bài toán làm tiêu chu n ch n l a hành ng cho ph m vi c c b c a t ng bư c (hay t ng giai o n) trong quá trình tìm ki m l i gi i. Nguyên lý th t : Th c hi n hành ng d a trên m t c u trúc th t h p lý c a không gian kh o sát nh m nhanh chóng t ư c m t l i gi i t t. Hàm Heuristic: Trong vi c xây d ng các thu t gi i Heuristic, ngư i ta thư ng dùng các hàm Heuristic. ó là các hàm ánh già thô, giá tr c a hàm ph thu c vào tr ng thái hi n t i c a bài toán t i m i bư c gi i. Nh giá tr này, ta có th ch n ư c cách hành ng tương i h p lý trong t ng bư c c a thu t gi i. Bài toán hành trình ng n nh t – ng d ng nguyên lý Greedy 2 Sưu t m b i: www.daihoc.com.vn
Bài toán: Hãy tìm m t hành trình cho m t ngư i giao hàng i qua n i m khác nhau, m i i m i qua m t l n và tr v i m xu t phát sao cho t ng chi u dài o n ư ng c n i là ng n nh t. Gi s r ng có con ư ng n i tr c ti p t gi a hai i m b t kỳ. T t nhiên ta có th gi i bài toán này b ng cách li t kê t t c con ư ng có th i, tính chi u dài c a m i con ư ng ó r i tìm con ư ng có chi u dài ng n nh t. Tuy nhiên, cách gi i này l i có ph c t p 0(n!) (m t hành trình là m t hoán v c a n i m, do ó, t ng s hành trình là s lư ng hoán v c a m t t p n ph n t là n!). Do ó, khi s i lý tăng thì s con ư ng ph i xét s tăng lên r t nhanh. M t cách gi i ơn gi n hơn nhi u và thư ng cho k t qu tương i t t là dùng m t thu t gi i Heuristic ng d ng nguyên lý Greedy. Tư tư ng c a thu t gi i như sau: T i m kh i u, ta li t kê t t c quãng ư ng t i m xu t phát cho nn i lý r i ch n i theo con ư ng ng n nh t. Khi ã i nm t i lý, ch n i n i lý k ti p cũng theo nguyên t c trên. Nghĩa là li t kê t t c con ư ng t i lý ta ang ng n nh ng i lý chưa i n. Ch n con ư ng ng n nh t. L p l i quá trình này cho n lúc không còn i lý nào i. B n có th quan sát hình sau th y ư c quá trình ch n l a. Theo nguyên lý Greedy, ta l y tiêu chu n hành trình ng n nh t c a bài toán làm tiêu chu n cho ch n l a c c b . Ta hy v ng r ng, khi i trên n o n ư ng ng n nh t thì cu i cùng ta s có m t hành trình ng n nh t. i u này không ph i lúc nào cũng úng. V i i u ki n trong hình ti p theo thì thu t gi i cho chúng ta m t hành trình có chi u dài là 14 trong khi hành trình t i ưu là 13. K t qu c a thu t gi i Heuristic trong trư ng h p này ch l ch 1 ơn v so v i k t qu t i ưu. Trong khi ó, ph c t p c a thu t gi i Heuristic này ch là 0(n2). 3 Sưu t m b i: www.daihoc.com.vn
Hình : Gi i bài toán s d ng nguyên lý Greedy T t nhiên, thu t gi i theo ki u Heuristic ôi lúc l i ưa ra k t qu không t t, th m chí r t t như trư ng h p hình sau. Bài toán phân vi c – ng d ng c a nguyên lý th t M t công ty nh n ư c h p ng gia công m chi ti t máy J1, J2, … Jm. Công ty có n máy gia công l n lư t là P1, P2, … Pn. M i chi ti t u có th ư c gia công trên b t kỳ máy nào. M t khi ã gia công m t chi ti t trên m t máy, công vi s ti p t c cho n lúc hoàn thành, không th b c t ngang. gia công m t vi c J1 trên m t máy b t kỳ ta c n dùng m t th i gian tương ng là t1. Nhi m v c a công ty là ph i làm sao gia công xong toàn b n chi ti t trong th i gian s m nh t. Chúng ta xét bài toán trong trư ng h p có 3 máy P1, P2, P3 và 6 công vi c v i th i gian là t1=2, t2=5, t3=8, t4=1, t5=5, t6=1. ta có m t phương án phân công (L) như hình sau: 4 Sưu t m b i: www.daihoc.com.vn
Theo hình này, t i th i i m t=0, ta ti n hành gia công chi ti t J2 trên máy P1, J5 trên P2 và J1 t i P3. T i th i i m t=2, công vi c J1 ư c hoàn thành, trên máy P3 ta gia công ti p chi ti t J4. Trong lúc ó, hai máy P1 và P2 v n ang th c hi n công vi c u tiên mình … Sơ phân vi c theo hình trên ư c g i là lư c GANTT. Theo lư c này, ta th y th i gian hoàn thành toàn b 6 công vi c là 12. Nh n xét m t cách c m tính ta th y r ng phương án (L) v a th c hi n là m t phương án không t t. Các máy P1 và P2 có quá nhi u th i gian rãnh. Thu t toán tìm phương án t i ưu L0 cho bài toán này theo ki u vét c n có ph c t p c O(mn) (v i m là s máy và n là s công vi c). Bây gi ta xét n m t thu t gi i Heuristic r t ơn gi n ( ph c t p O(n)) gi i bài toán này. S p x p các công vi c theo th t gi m d n v th i gian gia công. L n lư t s p x p các vi c theo th t ó vào máy còn dư nhi u th i gian nh t. V i tư tư ng như v y, ta s có m t phương án L* như sau: Rõ ràng phương án L* v a th c hi n cũng chính là phương án t i ưu c a trư ng h p này vì th i gian hoàn thành là 8, úng b ng th i gian c a công vi c J3. Ta hy v ng r ng m t gi i Heuristic ơn gi n như v y s là m t thu t gi i t i ưu. Nhưng ti c thay, 5 Sưu t m b i: www.daihoc.com.vn
ta d dàng ưa ra ư c m t trư ng h p mà thu t gi i Heuristic không ưa ra ư c k t qu t i ưu. N u g i T* là th i gian gia công xong n chi ti t máy do thu t gi i Heuristic ưa ra và T0 là th i gian t i ưu thì ngư i ta ã ch ng minh ư c r ng , M là s máy V i k t qu này, ta có th xác l p ư c sai s mà chúng ta ph i gánh ch u n u dùng Heuristic thay vì tìm m t l i gi i t i ưu. Ch ng h n v i s máy là 2 (M=2) ta có , và ó chính là sai s c c i mà trư ng h p trên ã gánh ch u. Theo công th c này, s máy càng l n thì sai s càng l n. Trong trư ng h p M l n thì t s 1/M xem như b ng 0 . Như v y, sai s t i a mà ta ph i ch u là T* 4/3 T0, nghĩa là sai s t i a là 33%. Tuy nhiên, khó tìm ra ư c nh ng trư ng h p mà sai s úng b ng giá tr c c i, dù trong trư ng h p x u nh t. Thu t gi i Heuristic trong trư ng h p này rõ ràng ã cho chúng ta nh ng l i gi i tương i t t. III. CÁC PHƯƠNG PHÁP TÌM KI M HEURISTIC Qua các ph n trư c chúng ta tìm hi u t ng quan v ý tư ng c a thu t gi i Heuristic (nguyên lý Greedy và s p th t ). Trong m c này, chúng ta s i sâu vào tìm hi u m t s k thu t tìm ki m Heuristic – m t l p bài toán r t quan tr ng và có nhi u ng d ng trong th c t . III.1. C u trúc chung c a bài toán tìm ki m 6 Sưu t m b i: www.daihoc.com.vn
ti n l i cho vi c trình bày, ta hãy dành chút th i gian làm rõ hơn " i tư ng" quan tâm c a chúng ta trong m c này. M t cách chung nh t, nhi u v n -bài toán ph c t p u có d ng "tìm ư ng i trong th " hay nói m t cách hình th c hơn là "xu t phát t m t nh c a m t th , tìm ư ng i hi u qu nh t n m t nh nào ó". M t phát bi u khác thư ng g p c a d ng bài toán này là : Cho trư c hai tr ng thái T0 và TG hãy xây d ng chu i tr ng thái T0, T1, T2, ..., Tn-1, Tn = TG sao cho : th a mãn m t i u ki n cho trư c (thư ng là nh nh t). Trong ó, Ti thu c t p h p S (g i là không gian tr ng thái – state space) bao g m t t c các tr ng thái có th có c a bài toán và cost(Ti-1, Ti) là chi phí bi n it tr ng thái Ti-1 sang tr ng thái Ti. Dĩ nhiên, t m t tr ng thái Ti ta có nhi u cách bi n i sang tr ng thái Ti+1. Khi nói n m t bi n i c th t Ti-1 sang Ti ta s dùng thu t ng hư ng i (v i ng ý nói v s l a ch n). Hình : Mô hình chung c a các v n -bài toán ph i gi i quy t b ng phương pháp tìm ki m l i gi i. Không gian tìm ki m là m t t p h p tr ng thái - t p các nút c a th . Chi phí c n thi t chuy n t tr ng thái T này sang tr ng thái Tk ư c bi u di n dư i d ng các con s n m trên cung n i gi a hai nút tư ng trưng cho hai tr ng thái. a s các bài toán thu c d ng mà chúng ta ang mô t u có th ư c bi u di n dư i d ng th . Trong ó, m t tr ng thái là m t nh c a th . T p h p S bao g m t t c các tr ng thái chính là t p h p bao g m t t c nh c a th . Vi c bi n i t tr ng thái Ti-1 sang tr ng thái Ti là vi c i t nh i di n cho Ti-1 sang nh i di n cho Ti theo cung n i gi a hai nh này. III.2. Tìm ki m chi u sâu và tìm ki m chi u r ng b n c có th hình dung m t cách c th b n ch t c a thu t gi i Heuristic, chúng ta nh t thi t ph i n m v ng hai chi n lư c tìm ki m cơ b n là tìm ki m theo chi u sâu (Depth First Search) và tìm ki m theo chi u r ng (Breath First Search). S dĩ chúng ta dùng t chi n lư c mà không ph i là phương pháp là b i vì trong th c t , 7 Sưu t m b i: www.daihoc.com.vn
ngư i ta h u như ch ng bao gi v n d ng m t trong hai ki m tìm ki m này m t cách tr c ti p mà không ph i s a i gì. 8 Sưu t m b i: www.daihoc.com.vn