Phương pháp tham lam (greedy) - Bài toán
- Phương pháp
- Lược đồ tổng quát
- Ví dụ minh hoạ
- Bài toán Cái ba lô
- Bài toán tô màu bản đồ
Nhiều vấn đề cần giải quyết qui về bài toán: - Cho trước tập A các đối tượng nào đó, cần phải chọn ra một tập con S các đối tượng thoả mãn một số điều kiện nào đó.
- Bất kỳ tập con S nào thoả mãn điều kiện gọi là nghiệm chấp nhận được của bài toán.
- Một hàm mục tiêu gắn mỗi nghiệm chấp nhận được với một giá trị nào đó.
- Một nghiệm chấp nhận được mà hàm mục tiêu có giá trị lớn nhất (hoặc nhỏ nhất) gọi là nghiệm tối ưu
Phương pháp - Ta xây dựng tập S dần từng bước, bắt đầu từ tập S =∅
- Tại mỗi bước, ta sẽ chọn một phần tử “tốt nhất” trong các phần tử còn lại của A để đưa vào tập S.
- Việc chọn lựa một phần tử như thế ở mỗi bước sẽ được hướng dẫn bởi hàm chọn.
- Phần tử được chọn bị loại khỏi tập A
Nếu khi thêm phần tử được chọn vào tập S mà S vẫn thoả mãn các điều kiện của bài toán, ta tiếp tục mở rộng S bằng cách thêm vào phần tử được chọn
Lược đồ tổng quát - Thamlam(A,S) { A là tập các ứng cử viên, S là tập nghiệm}
- Bước 1: S=∅;
- Bước 2: Khi A ≠ ∅ thực hiện các bước sau:
- Bươc 2.1: X = Select(A);
- Bước 2.2: A = A - {x};
- Bước 2.3: Nếu S ∪ {x} Chấp nhận được thì S=S ∪ {x}
Bài toán cái ba lô - Input:
- Cho n đồ vật
- Đồ vật i khối lượng Wi và trị giá Vi
- Kích thước ba lô Z
- Output:
- Chọn k đồ vật cho vào ba lô sao cho tổng khối lượng W ≤ Z và tổng giá trị V lớn nhất
Ví dụ: Cho 4 loại đồ vật có khối lượng và trị giá: Kích thước ba lô 37 Ý tưởng - Sử dụng phương pháp tham lam
- Ta xây dựng nghiệm dần từng bước
- Ta căn cứ vào tỉ lệ giữa giá trị và khối lượng V/W sắp xếp các đồ vật sẽ chọn lựa theo thứ tự ưu tiên giảm
BALO - S=∅
- Với mỗi đồ vật i ∈ n thực hiện: Nếu tất cả các đồ vật trong S∪ {i} có chấp nhận được S= S ∪ {i}
Trong nhiều trường hợp ta chỉ chọn được nghiệm gần đúng với nghiệm tối ưu - Ví dụ với Z=15
- Ta chọn đồ vật W=15, V=30 “Tối ưu hơn” 2 đồ vật (W= 10,V=25) và (W =2,V=2)
Bài toán tô màu bản đồ Bài toán: - Tô màu các nước trên bản đồ sao cho các nước có chung đường biên giới thì được tô khác màu nhau.
- Cần chọn cách tô tối ưu sao cho số màu dùng để tô là ít nhất
- Input:
- Cho đồ thị G=(V,E) là đồ thị không có hướng
- Cần sơn các đỉnh đồ thị sao cho hai đỉnh kề nhau được sơn bởi hai màu khác nhau
- Output:
- Số màu k tối thiểu phải sử dụng
Ý tưởng: - Sử dụng phương pháp tham lam
- Dùng một màu để tô (ví dụ màu đỏ).
- Chọn một đỉnh chưa được tô, và tô đỉnh đó.
- Sau đó với mỗi đỉnh chưa được sơn, nếu nó không kề với các đỉnh đã tô bởi màu đang dùng, ta tiến hành tô nó bởi màu đang sử dụng.
- Khi không còn đỉnh nào có thể tô bởi màu đó thì ta sử dụng một màu mới
- Quá trình này cứ tiếp tục cho đến khi các đỉnh trên đồ thị đã được tô
Giải thuật - Gọi V là tập đỉnh của đồ thị
- V0 là tập đỉnh chưa được tô
- V1 là tập các đỉnh đã được tô
- Ta kí hiệu các màu là k =1, 2, 3, …
- Bước 1: k=0; V0 = V;
- Bước 2: Khi k <> 0 thực hiện các bước sau:
- Bước 2.1: k=k+1;
- Bước 2.2: Chọn x∈ V0 và tô x bởi màu k;
- Bước 2.3: V1 = V1∪ {x};
- Bước 2.4:Với mỗi v ∈ V0 thực hiện:
- Bước a: Nếu v không kề với mọi w ∈ V1
- Bước a.1: Tô v bởi màu k;
- Bước a.2: V1 = V1 ∪ {v};
- Bước b: V0 = V0 –V1
N G UY N GN G Ễ N Ọ C D Ư Ơ bé gi¸o dôc vµ ®µo t¹o trêng ®¹i häc b¸ch khoa hµ néi ------- NGUYNGNG ỄN ỌC D ƯƠ n gµ nh C NT T ỨỤẬỀ NG DNG THUT TOÁN DI TRUYN GI Ả I BÀI ÁN TO ĐÓNG THÙNG luËn v¨n th¹c sÜ NGµNH C¤NG NGHÖ TH¤NG TIN kh o¸ 2 0 0 7 - 2 0 0 9 Hµ néi – 2009 bé gi¸o dôc vµ ®µo t¹o trêng ®¹i häc b¸ch khoa hµ néi ------- N GUYỄN NGỌC DƯƠNG ỨNG DỤNG THUẬT TOÁN DI TRUYỀN GIẢI BÀI TOÁN ĐÓNG THÙNG luËn v¨n th¹c sÜ C¤NG NGHÖ TH¤NG TIN Ngêi híng dÉn khoa häc : PGS.TS. NGUYÔN §øC NGHÜA Hµ Néi – 2009 L ời cảm ơn Đầỏựết ơn sâu sắầy đã tậu tiên tôi xin bày t s bic PGS. TS. Nguyễn Đức Nghĩa, thn tình ging dy chúng tôi các môn hc chuyên ngành và nhing d ảạọệt tình hướẫn, giúp đỡtôi hoàn thành lu ận văn này. Tôi cũng muốn bày tỏ lòng biết ơn các thầy cô khoa Công nghệ Thông tin trường Đại học Bách khoa Hà Nội đã giảng dạy cho chúng tôi các môn học chuyên đề trong khóa học. Cuối cùng gia đình, đặc biệt người bạn đời của tôi, là những người rất quan trọng đã một lòng động viênvà tạo điều kiện giúp tôi tập trung hoàn thành luận văn này. Mặc dù đã có nhiều cố gắng, nhưng vì kiến thức và thời gian hạn chế nên chắc chắn luận văn này còn nhiều thiếu sót. Tôi xin chân thành cảm ơn và rất mong nhận được những ý kiến đóng góp từ các thầy cô và các bạn. Những góp ý xin gửi về địa chỉ: Nguy ễn Ngọc DươngB môn Khoa hc máy tính, khoa Công ngh ộọệthông tin, trường Đại học Bách Khoa Hà Nội. Email: duongnn@it-c hut.edu.vn hoặ[email protected] Hà Nội, ngày 21 tháng 7 năm 2009 Nguyễn Ngọc Dương Học viên cao học Lớp Công nghệ thông tin 2007 – 2009Trường Đại học Bách Khoa Hà Nội | 
