Vấn đề Vét Cạn Và Giải Pháp

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à 8, phương án tốt nhất là để hai vật có khối lượng 4 và 3 lên giá.

Để giải bài toán này bằng phương pháp vét cạn, trước hết chúng ta phải xác định dạng của ứng viên và hàm đánh giá ứng viên. Mỗi một tập con (bao gồm các vật được chọn để đặt lên giá) của tập tất cả các vật là một ứng viên. Ta có thể biểu diễn mỗi ứng viên bằng một xâu nhị phân c = x1 x2…xnvới ý nghĩa vật thứ i được để trên giá nếu xi = 1 và không được để trên giá nếu xi = 0. Hàm đánh giá ứng viên được xác định như sau:

Trong ví dụ trên, tập các ứng viên là C= {000, 001, 010, 011, 100, 101,110, 111}; điểm đánh giá các ứng viên lần lượt là 0, 3, 4, 7, 6, 0, 0, và 0; ứng viên được chọn là 011.

Tiếp theo, chúng ta cần thiết lập cây biểu diễn không gian ứng viên. Chúng ta sử dụng n tính chất để phân hoạch các ứng viên đó là: vật thứ nhất được đưa lên giá (x1=1), vật thứ hai được đưa lên giá (x2=1), …, vật thứ n được đưa lên giá (xn=1). Với n tính chất này, thực hiện thủ tục thiết lập cây biểu diễn không gian ứng viên được mô tả ở trên, chúng ta thu được một cây nhị phân đầy đủ có chiều cao n, bao gồm 2n lá, mỗi lá biểu diễn một ứng viên. Trong ví dụ trên, cây biểu diễn không gian ứng viên có dạng như sau:

Hình 1. Cây biểu diễn không gian ứng viên của bài toán Cái giá với n =3.

Cuối cùng, chúng ta áp dụng thủ tục duyệt cây theo chiều sâu (không nên sử dụng duyệt theo chiều rộng trong trường hợp này vì phải lưu trữ nhiều thông tin đồng thời) để tìm ứng viên tốt nhất (phương án đặt vật lên giá tốt nhất). Thủ tục duyệt được mô tả đệ quy như sau:

ungvienDuocChon := ‘0….0’

diemCaonhat := 0

duyet(1, ‘’)

procedure duyet(i, c)

if i = n+1 then

m := f(c)

ifm >diemCaonhat then

diemCaonhat := m

ungvienDuocChon := c

else

duyet(i+1, c & ‘1’)

duyet(i+1, c & ‘0’)

Ví dụ 2. Tìm đường đi dài nhất

Bài toán: Cho một lưới các ô vuông, mỗi ô được tô một màu: tím hoặc vàng. Hai ô được gọi là liền kề nếu chúng có chung cạnh. Một đường đi trong lưới là một dãy liên tiếp các ô vàng trong đó hai ô liên tiếp bất kỳ liền kề với nhau và không có ô nào xuất hiện trong dãy quá một lần. Hãy tìm đường đi dài nhất (có nhiều ô nhất) xuất phát từ ô ở góc trên trái và kết thúc tại ô ở góc dưới phải.

Hình 2 cho chúng ta một ví dụ về lưới và đường đi dài nhất xuất phát từ ô ở góc trên trái và kết thúc tại ô ở góc dưới phải.

Hình 2. Một đường đi dài nhất trên lưới.

Cũng như trên, để giải bài toán này bằng phương pháp vét cạn, trước hết chúng ta phải xác định dạng của ứng viên và hàm đánh giá ứng viên. Mỗi ứng viên là một đường đi xuất phát từ ô ở góc trên trái và kết thúc tại ô ở góc dưới phải. Chúng ta sẽ biểu diễn mỗi ứng viên cbằng một lưới kích thước m×n như lưới ban đầu trong đó các ô trên đường đi được đánh số thứ tự liên tiếp bắt đầu từ ô xuất phát. Hàm đánh giá ứng viên được xác định là f(c) = c(m, n) (giá trị ô (m, n)).

Hình 3. Biểu diễn một ứng viên có điểm đánh giá f(c) = 9.

Để phân loại ứng viên, chúng ta sử dụng hướng đi tại mỗi ô được định nghĩa như sau:

Với (i, j) là một ô thuộc đường đi, đường đi được gọi là hướng xuống tại (i, j) nếu ô kế tiếp trên đường đi là (i+1, j), là hướng lên tại (i, j) nếu ô kế tiếp trên đường đi là (i-1, j), là hướng trái tại (i, j) nếu ô kế tiếp trên đường đi là (i, j-1), là hướng phải tại (i, j) nếu ô kế tiếp trên đường đi là (i, j+1). Với các hướng đi được định nghĩa như vậy, thực hiện thủ tục thiết lập cây biểu diễn không gian ứng viên, chúng ta thu được một cây tứ phân. Hình 4 cho chúng ta một ví dụ về cây biểu diễn không gian ứng viên với lưới được vẽ trong Hình 2.

Hình 4. Một cây biểu diễn không gian ứng viên của bài toán Tìm đường đi dài nhất.

Ký hi.ệu (i)m×n là lưới kích thước m×n với các ô vàng có giá trị bằng i, các ô màu tím có giá trị bằng -1. Thủ tục duyệt cây biểu diễn không gian ứng viên được mô tả như sau:

ungvienDuocChon := c := (0)m×n

c(1, 1) = 1

duyet(1, 1)

procedure duyet(i, j)

if i=m and j=n then

if c(m, n) > ungvienDuocChon(m, n) then

ungvienDuocChon := c

else

if c(i+1, j) = 0 and i < m then ‘Đi xuống

c(i+1, j) := c(i, j) + 1

duyet(i+1, j)

c(i+1, j) := 0

if c(i-1, j) = 0 and i > 1 then ‘Đi lên

c(i-1, j) := c(i, j) + 1

duyet(i-1, j)

c(i-1, j) := 0

if c(i, j+1) = 0 and j < n then ‘Sang phải

c(i, j+1) := c(i, j) + 1

duyet(i, j+1)

c(i, j+1) := 0

if c(i, j-1) = 0 and j > 1 then ‘Sang trái

c(i, j-1) := c(i, j) + 1

duyet(i, j-1)

c(i, j-1) := 0

4. Kết luận

Vấn đề chính trong sử dụng phương pháp vét cạn để giải toán là liệt kê các ứng viên. Một phương pháp hay được sử dụng là thiết lập cây biểu diễn không gian ứng viên rồi áp dụng một thủ tục duyệt cây để liệt kê các ứng viên. Bài viết đã đưa ra một phương pháp chung để thiết lập cây biểu diễn không gian ứng viên. Phương pháp này gợi ý cho chúng ta sử dụng một số tính chất để phân loại ứng viên và thủ tục thiết lập cây biểu diễn không gian ứng viên.

Vét cạn là cơ sở cho hai phương pháp khác là quay lui và nhánh cận. Cả vét cạn, quay lui và nhánh cận đều thực hiện duyệt cấu trúc cây biểu diễn không gian ứng viên. Điểm phân biệt giữa vét cạn, quay lui và nhánh cận là trong quá trình duyệt (theo chiều sâu) cây, phương pháp quay lui sử dụng một hàm điều kiện, tại mỗi nút nếu hàm điều kiện không thỏa mãn, toàn bộ cây con có gốc tại nút hiện tại được bỏ qua; phương pháp nhánh cận sử dụng một hàm tính cận để tính trước điểm tối đa (cận) có thể đạt được đối với các ứng viên thuộc cây con có gốc tại nút hiện tại, nếu cận này không cao hơn điểm của ứng viên đã biết thì toàn bộ cây con có gốc tại nút hiện tại được bỏ qua. Có thể tóm tắt hai phương pháp quay lui và nhánh cận theo các công thức:

Vét cạn + Hàm điều kiện = Quay lui,

Vét cạn + Hàm tính cận = Nhánh cận.

Như vậy, vấn đề chúng ta đã xét trong vét cạn cũng là vấn đề của hai phương pháp quay lui và nhánh cận.