CÁC THUẬT TOÁN THAM LAM (GREEDY).

Tham khảo tài liệu các thuật toán tham lam (greedy)., công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
CÁC THUẬT TOÁN THAM LAM (GREEDY). Please purchase apersonal license. personal CÁC THU T TOÁN TOTHAM LAM (GREEDY)THAM Gi i thu t tham lam Gi thu thamKhái ni m:M i bài toán ta có t p h p nh ng l a ch n gi iquy t bài toán. Gi i thu t tham lam x u t vi c l ach n kh năng t t nh t cho bài toán ó.Ví d : Bài toán cây khung t i thi u Bài toán ư ng i ng n nh t Traveling Salesperson Problem TravelingBài toán: Bài toán tìm ư ng i c a ngư i giao hàng (TSP)- Ngư i giao hàng c n i giao hàng t i n thành ph .Xu t phát t m t thành ph nào ó, i qua các thànhph khác giao hàng và tr v thành ph ban u.- M i thành ph ch n 1 l n. Kho ng cách gi acác thành ph là xác nh- Hãy tìm m t chu trình sao cho t ng dài ư ng i là nh nh t Traveling Salesperson Problem TravelingGi i quy t bài toán v i phương pháp vét c n:- Xét t t c các chu trình, và ch n chu trình dàinh nh t Ph i xét t t c (n-1)!/2 chu trình???- Ch n 1 nh b t kì, t i nh này có n-1 c nh t i n-1 nh khác, nên có n-1 các ch n c nh u tiên.- Sau khi ch n ư c c nh u tiên, còn n-2 cáchch n c nh th 2.- Ti p t c như v y ta có (n-1)! cách ch n chu trình- Do ch quan tâm n dài, không quan tâm như ng (n-1)!/2 phương án Traveling Salesperson Problem Traveling Gi i quy t bài toán v i gi i thu t tham lam:1. Xét các c nh có dài t nh nl n ưa vào chu trình ( có n(n-1)/2 c nh)2. M i c nh s ư c ưa vào chu trình n u: 1. Không t o thành m t chu trình thi u (t o thành chu trình trư c khi i h t t t c n nh) 2. Không t o thành m t nh có c p >=3 ( không có nhi u hơn 2 c nh xu t phát t m t nh, do yêu c u c a bài toán m i thành ph ch n 1 l n: 1 n, 1 i)3. L p l i bư c 2 cho n khi xây d ng ư c 1 chu trình Traveling Salesperson Problem Traveling Ví d : Cho dài ư ng i gi a các thành ph ư c bi u di n b ng ma tr n k sau. Tìm chu trình ng n nh t gi a các thành ph 1234567• (3,5) = 1 (5,6) = 2 (4,7) = 4 1 16 12 13 6 7 11 2 21 18 8 19 5 (2,7) = 5 (1,6) = 7 (1,4) = 13 3 20 1 3 15 (2,3) =21 4 14 10 4T ng ư ng i: (1,4,7,2,3,5,6,1)=53 5 2 17 6 9 ây ch là phương án t tPhương án t i ưu: (1,4,7,2,5,3,6,1) =41 Traveling Salesperson Problem Traveling Gi i thu t:void TSP (Graph &g){ E – t p h p các c nh; S p x p các c nh trong E theo th t tăng d n; cycle = NULL; length_cycle = 0; while (E !=F) { if ( c nh e th a mãn i u ki n ) { cycle = cycle + e; length_cycle = length_cycle + length(e); } E = E – e; }} Traveling Salesperson Problem Traveling Gi i pháp khác c a thu t toán tham lam:1. Xu t phát t 1 nh b t kỳ, ch n 1 c nh có dài nh nh t t nh ó n nh k ti p.2. T nh k ti p, ch n c nh có dài nh nh t i ra t nh này th a m n 2 i u ki n ( không t o chu trình trư c khi qua n nh, 1 nh không l n hơn 2 ư ng i)3. L p l i bư c 2 cho n khi i n n nh thì quay l i nh xu t phát Traveling Salesperson Problem TravelingBài t p: Tìm ư ng i ng n nh t c a ngư i giaohàng v i dài gi a các thành ph cho b i matr n sau:ư ng i ã tìm ra t i ưu chưa?