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

Chia sẻ: Chu Quang Chien | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

413
lượt xem 81
download

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

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ả

Chủ đề:

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

Lưu

Nội dung Text: CÁC THUẬT TOÁN THAM LAM (GREEDY).

Please purchase a personal license. personal
CÁC THU T TOÁN TO THAM LAM (GREEDY) THAM
Gi i thu t tham lam Gi thu tham Khái ni m: M i bài toán ta có t p h p nh ng l a ch n gi i quy t bài toán. Gi i thu t tham lam x u t vi c l a ch 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 Traveling Bà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ành ph 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 a cá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 Traveling Gi 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ài nh 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ách ch 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 n hư 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 4 T ng ư ng i: (1,4,7,2,3,5,6,1)=53 5 2 17 6 9 ây ch là phương án t t Phươ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 Traveling Bài t p: Tìm ư ng i ng n nh t c a ngư i giao hàng v i dài gi a các thành ph cho b i ma tr n sau: ư ng i ã tìm ra t i ưu chưa?