Vet can

Vấn đề trong vét cạn và giải pháp
Ngày gửi bài: 24/12/2008 Số lượt đọc: 562
Vét cạn theo nghĩa thông thường là xét hết mọi đối tượng hay mọi trường hợp. Trong lập trình, vét cạn là phương pháp được dùng khi không còn phương pháp nào hiệu quả hơn có thể sử dụng được.
1. Phương pháp vét cạn
Vét cạn theo nghĩa thông thường là xét hết mọi đối tượng hay mọi trường hợp. Trong lập trình, vét cạn là phương pháp được dùng khi không còn phương pháp nào hiệu quả hơn có thể sử dụng được. Phương pháp vét cạn được mô tả chung như sau:
Bài toán: Có một tập Ccác ứng viên và một hàm f để đánh giá/cho điểm các ứng viên. Hãy tìm ứng viên được đánh giá/có điểm cao nhất.
Phương pháp giải: Duyệt tất cả các ứng viên, tính điểm cho từng ứng viên, sau đó lấy ứng viên có điểm cao nhất.
Chúng ta xét một ví dụ đơn giản.
Bài toán: Cho tập Cgồm n số nguyên dương. Hãy tìm số chính phương lớn nhất trong Cbiết rằng số chính phương là số bằng bình phương của một số nguyên khác.
Lời giải của bài toán bằng phương pháp vét cạn:
Tập các ứng viên: C = {c1, c2, …, cn}
Hàm đánh giá ứng viên: f(ci) = 0 nếu cikhông là số chính phương, f(ci) = cinếu ci là số chính phương.
Thủ tục vét cạn:
ungvienDuocChon := 0
diemCaonhat := 0
for i := 1 to n
m := f(ci)
If m > diemCaonhat then
diemCaonhat:= m
ungvienDuocChon := ci
 
2. Vấn đề của vét cạn: Liệt kê các ứng viên
Phương pháp vét cạn tưởng rằng tầm thường nhưng thực sự không tầm thường chút nào bởi vì không phải trong trường hợp nào các ứng viên cũng dễ nhận thấy và đã “sếp hàng” sẵn để được duyệt như trong ví dụ đơn giản nêu trên. Nghĩa là, vấn đề trong phương pháp vét cạn là làm sao để liệt kê được tất cả các ứng viên. Một khi đã liệt kê được các ứng viên, việc chấm điểm cho từng ứng viên và chọn ra ứng viên có điểm cao nhất chỉ còn là việc làm đơn giản.
Một phương pháp hay được dùng để liệt kê các ứng viên là tổ chức không gian ứng viên theo một cấu trúc cây, mỗi ứng viên trên một nút (thường là lá) của cây. Đặc điểm của cây biểu diễn không gian ứng viên là các ứng viên trên các nút có quan hệ cha-con hoặc anh-em giống nhau ở một bộ phận nào đó. Một khi cấu trúc cây biểu diễn không gian ứng viên được thiết lập, chúng ta có thể áp dụng thủ tục duyệt cây (theo chiều rộng hoặc theo chiều sâu) để liệt kê các ứng viên. Cây biểu diễn không gian ứng viên có thể rất lớn và sẽ mất nhiều thời gian để tạo cũng như yêu cầu nhiều không gian để lưu trữ. Tuy nhiên, cây này chỉ mang tính trừu tượng, làm cơ sở cho việc duyệt (chọn nút tiếp theo được thăm), mà không phải được tạo ra và lưu trữ tất cả.
Các bước thiết lập cây biểu diễn không gian ứng viên được mô tả chung như sau:
1.Xác định các tính chất của ứng viên dùng để phân loại ứng viên.
2.Với tính chất thứ nhất, phân hoạch các ứng viên theo tính chất này, nghĩa là chia tập ứng viên thành các tập con theo đó các phần tử thuộc cùng một tập con giống nhau ở tính chất thứ nhất, hai phần tử thuộc hai tập con khác nhau sẽ khác nhau ở tính chất thứ nhất. Tạo các cây con từ gốc, mỗi cây con tương ứng với một tập con vừa nhận được.
3.Với mỗi tập con, sử dụng tính chất thứ hai để phân hoạch tập con này. Kết quả thu được là các tập con nhỏ hơn. Từ gốc của cây con tương ứng với tập con đang xét, tạo các nhánh tương ứng với các tập con nhỏ hơn.
4.Quá trình cứ tiếp tục như vậy cho đến khi chúng ta xét hết các tính chất của ứng viên và thu được một cây biểu diễn không gian ứng viên.
Chúng ta xét một số ví dụ trong Mục 3 sau đây.

3. Một số ví dụ
Ví dụ 1. Cái giá (còn có tên là Knapsack 0/1)
Bài toán: Cho n đồ vật có khối lượng lần lượt là w1, w2, …, wn và một cái giá chịu khối lượng tối đa là W.Hãy để các đồ vật lên giá sao cho tổng khối lượng các đồ vật được để trên giá là lớn nhất có thể.
Ví dụ với 3 vật có khối lượng lần lượt là 6, 4, 3 và một cái giá có thể chịu khối lượng tối đa là