Thuật toán cơ bản đến nâng cao #1: duyệt vét cạn

Bài viết sẽ giới thiệu về thuật toán duyệt vét cạn, phương pháp thường được sử dụng để giải quyết các bài toán mức độ dễ hoặc để ghi điểm ở những subtask với giới hạn nhỏ của các bài mức độ khó.

Giới thiệu thuật toán duyệt vét cạn

Trong lập trình thi đấu, khi đối mặt với một bài có độ khó cao, sẽ có lúc ta không thể nghĩ ra được một thuật toán tốt (có độ phức tạp thỏa mãn giới hạn của bài toán). Khi đó, một chiến lược hiệu quả sẽ là nghĩ ra một thuật toán có độ phức tạp không tốt lắm nhưng phải chắc chắn đúng để ghi điểm ở các testcase với giới hạn nhỏ. Và duyệt vét cạn chính là kỹ thuật thường được nghĩ đến trong những tình huống như thế này.

Duyệt vét cạn hiểu đơn giản là sẽ duyệt – kiểm tra qua tất cả các trường hợp, các trạng thái có thể có của bài toán.

Ví dụ 1: Cho dãy số A gồm n phần tử (n <= 10⁶, A_i <= 10⁹), tìm 3 phần tử trong dãy số sao cho chúng có tổng lớn nhất.

Với bài toán này, thuật toán duyệt vét cạn mà ta nghĩ đến là duyệt mọi bộ 3 phần tử trong dãy số bằng cách sử dụng 3 vòng for lồng nhau. Độ phức tạp của cách giải này là sẽ là O(n³). Với giới hạn của bài toán đã cho là n <= 10⁶ thì chắc chắn đây chưa phải là một cách làm tốt, nhưng sẽ là một cách làm đúng là nên sử dụng nếu ta không thể nghĩ ra cách làm nào khác. (Giải thích thêm: giải thuật tốt cho bài toán ở ví dụ 1 là tìm 3 phần tử lớn nhất, bằng cách duyệt 1 vòng for từ đầu đến cuối dãy kết hợp với queue để lưu 3 phần tử lớn nhất, độ phức tạp O(n))

Sẽ có những bài toán mà implement thuật toán duyệt vét cạn cũng không hề đơn giản, không phải chỉ duyệt mấy vòng for lồng nhau mà vét cạn được.

Phần tiếp theo, bài viết sẽ giới thiệu về duyệt hoàn vị, tổ hợp, và tổng quát là sử dụng đệ quy để duyệt vét cạn. Các kỹ thuật duyệt này khá cơ bản, nhưng lại không phải ai cũng biết sử dụng để vét cạn.

Vét cạn bằng cách duyệt hoán vị

Bài toán

Ví dụ 2: Cho một đội n binh sĩ (n <= 11), cho một ma trận 2 chiều (n x n) P trong đó P[i][j] là sức mạnh của binh sĩ i nếu được đặt ở vị trí thứ j. Tìm cách sắp xếp n binh sĩ sao cho sức mạnh của cả đội là lớn nhất.

Nhận thấy ở ví dụ 2 này để vét cạn được ta phải duyệt qua tất cả các hoán vị của n binh sĩ ở n vị trí, rồi tính ra tổng power cho từng hoán vị để tìm ra hoán vị nào có tổng power lớn nhất.

Giải thích thuật toán

Tư tưởng của thuật toán duyệt hoán vị rất tự nhiên: ta sẽ chọn binh sĩ cho từng vị trí từ 1 đến n, vị trí sau không chọn trùng các binh sĩ đã chọn ở vị trí trước là được, cụ thể như sau:

• Ta sẽ chọn binh sĩ cho từng vị trí: tại một vị trí k nào đó, ta sẽ lần lượt thử chọn một trong các binh sĩ chưa được chọn
• Khi thử chọn một binh sĩ ta sẽ tạm đánh dấu binh sĩ đó là đã chọn phục vụ cho việc chọn ở các vị trí sau
• Tiếp tục chọn cho vị trí thử k+1 cho đến khi chọn cho vị trí cuối cùng (sử dụng đệ quy)
• Khi đến vị trí cuối cùng, ta sẽ thu được 1 hoán vị, tại đây sẽ tính tổng power của binh sĩ cho hoán vị này (cho các bài toán khác thì sẽ apply logic khác để validate trên hoán vị này)
• Lưu ý rằng sau mỗi lần đệ quy vào bước tiếp theo cần trả lại việc đánh dấu binh sĩ đã chọn

Dưới đây sẽ là code mẫu và giải thích cho việc duyệt hoán vị để bạn đọc dễ hình dung, trong đó:

• result: là tất cả các hoán vị có thể có.
• current: lưu hoán vị đang xét đến.
• hasChosen: là mảng đánh dấu số nào đã được chọn trong current.
• configurationByIndex là hàm chính của chương trình, index là vị trí đang được xét đến trong hoán vị, hàm được viết đệ quy khi đã chọn được 1 số ở vị trí index sẽ gọi tiếp đệ quy đến index + 1.
• Khi đã chọn được hết các số vào tất cả vị trí cho 1 hoán vị (index >= nums.length, hoặc chỉ cần index == nums.length), ta ghi nhận current vào result.
• Chú ý: sau mỗi bước gọi đệ quy đều cần có thao tác quay lui.

class Permutations {
    List<List<Integer>> result;
    List<Integer> current;
    boolean[] hasChosen;
    
    public List<List<Integer>> permute(int[] nums) {
        result = new ArrayList<>();
        current = new ArrayList<>();
        hasChosen = new boolean[nums.length];
        configurationByIndex(0, nums);
        return result;
    }

    private void configurationByIndex(int index, int[] nums) {
        if (index >= nums.length) { // Đã chọn đủ cho tất cả vị trí
            List<Integer> des = new ArrayList<>(current); // Ghi nhận hoán vị current là  1 kết quả
            result.add(des);
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (hasChosen[i]) continue; // Bỏ qua những số đã chọn
            hasChosen[i] = true; // Đánh dấu là đã chọn số i, để vị trí sau không bị chọn trùng
            current.add(nums[i]); // Ghi nhận vào hoán vị hiện tại
            configurationByIndex(index+1, nums); // Gọi đệ quy đến vị trí tiếp theo
            current.remove(Integer.valueOf(nums[i])); // Quay lui
            hasChosen[i] = false; // Quay lui
        }
    }
}

Code bên trên là cách để bạn duyệt đủ tất cả các hoán vị của n số. Còn để giải quyết bài toán ở ví dụ 2 thì kết quả của các bạn phải là 1 biến maxSum nào đó để lưu tổng lớn nhất, và ở bước ghi nhận kết quả các bạn cần tính tổng tương đương với hoán vị này rồi compare với maxSum. Phần lời giải này mới bạn đọc tự code nốt.

Nếu đến đây các bạn đã hiểu được cách duyệt hoán vị thì có thể “xơi ngon” được 2 bài trên leetcode là Permutations và Permutations II rồi. Cùng thử sức nhé!

Phần tiếp theo ta sẽ cùng tìm hiểu thuật toán duyệt tổ hợp con của 1 tập hợp cho trước.

Vét cạn bằng cách duyệt tổ hợp

Bài toán

Ta có một yêu cầu hơi khác đi 1 chút từ ví dụ 2.

Ví dụ 2: Cho n binh sĩ (n <= 20), yêu cầu thành lập 1 đội bằng cách chọn ra k binh sĩ (k <= n/2) sao cho sức mạnh của đội là lớn nhất, sức mạnh của đội là tổng sức mạnh của các cặp binh sĩ trong k binh sĩ. Cho một ma trận 2 chiều (n x n) P trong đó P[i][j] là sức mạnh của binh sĩ i nếu được làm việc cùng binh sĩ j.

Giải thích thuật toán

Thuật toán duyệt vét cạn cho bài trên là duyệt tất cả tổ hợp chập k của n binh sĩ, với mỗi tổ hợp tính ra tổng để so sánh với kết quả tốt nhất.

Cũng khá giống với duyệt hoán vị, ta sẽ đi chọn cho từng vị trí. Tuy nhiên khác với hoán vị (hoặc chỉnh hợp), tổ hợp chỉ quan tâm đến số được chọn, thay vì quan tâm đến cả vị trí được chọn. Ví dụ: hoán vị 1-2-3 và 1-3-2 và 3-2-1 là khác nhau, nhưng với tổ hợp nó chỉ là 1 tổ hợp của 3 số 1-2-3

Vì vậy, duyệt tổ hợp sẽ luôn chọn các số theo thứ tự từ điển luôn và không cần mảng hasChosen để đánh dấu nữa.

Dưới đây sẽ là code tham khảo. Các bạn đọc chú ý đoạn config cho vị trí index sẽ chỉ xét các số từ current[index-1]+1, tức là các số lớn hơn số đã chọn ở vị trí trước, nên sẽ không cần mảng đánh dấu.

public class Combinations {

    List<List<Integer>> result;
    int[] current;

    public List<List<Integer>> combine(int n, int k) {
        result = new ArrayList<>();
        current = new int[k];
        config(0, n, k);
        return result;
    }

    private void config(int index, int n, int k) {
        if (index == k) {
            List<Integer> combination = new ArrayList<>();
            for (int item : current) combination.add(item);
            result.add(combination);
            return;
        }

        int left = (index > 0) ? current[index-1]+1 : 1;
        int right = n-(k-1)+index;

        for (int i = left; i <= right; i++) {
            current[index] = i;
            config(index+1, n, k);
        }
    }
}

Bạn đọc có thể thử sức với các bài tập Combinations, Combination Sum trên leetcode nhé.

Đệ quy và quay lui (Backtracking)

Bên trên chỉ là 2 ví dụ kinh điển và 2 kĩ thuật duyệt rất điển hình để duyệt vét cạn. Nhìn chung nó đều dựa trên thuật toán đệ quy và quay lui.

Ta sẽ thực hiện chọn cho từng vị trí. Tại mỗi vị trí, ta lại thử từng phương án có thể có cho nó, chú ý lưu lại giá trị hay những đánh dấu cần thiết. Ta tiếp tục cho các vị trí tiếp theo, và sau khi chọn xong cho 1 phương án ta cần chú ý đến thao tác quay lui để thử tiếp phương án tiếp theo.

Dựa trên ý tưởng này mời bạn đọc thử sức bài Sudoku Solver một bài Hard trên leetcode nhưng ý tưởng hoàn toàn là vét cạn, đệ quy – quay lui.

Lời kết

Vét cạn là một thuật toán khá dễ để nghĩ ra, nhưng lại cần “tay khá to”. Vì phải duyệt qua hết các trường hợp nên đây thường không phải là 1 thuật toán tốt, tuy nhiên cũng nên biết vì trong trường hợp bí quá thì vẫn cần dùng.

Để tối ưu việc đệ quy và backtracking ta sẽ thường dùng đến các kĩ thuật như nhánh cận, đệ quy có nhớ (caching), bitmask (một dạng quy hoạch động), mình xin phép được giới thiệu ở các bài sau và xin phép dừng bài viết này tại đây.