Thuật toán quay lui trong java

Thuật toán quay lui trong Java là một phương pháp giải quyết các bài toán tìm kiếm bằng cách liệt kê tất cả các trường hợp có thể xảy ra. Thuật toán này có thể được sử dụng để giải quyết nhiều bài toán khác nhau như xếp hộp, sắp xếp thùng hàng, tìm đường đi ngắn nhất, tô màu đồ thị, và nhiều hơn nữa.

Các bước chính của thuật toán quay lui trong Java như sau:

Chọn một giá trị khởi tạo cho bài toán.
Kiểm tra xem giá trị đã chọn có thỏa mãn các điều kiện của bài toán hay không.
Nếu giá trị đã chọn thỏa mãn các điều kiện của bài toán, tiến hành tìm kiếm giá trị tiếp theo.
Nếu giá trị đã chọn không thỏa mãn các điều kiện của bài toán, quay lui trở lại bước trước đó và chọn giá trị khác để thử.
Lặp lại các bước 2 đến 4 cho đến khi tìm được giá trị thỏa mãn hoặc không còn giá trị nào để thử.

Dưới đây là một ví dụ về thuật toán quay lui trong Java để giải bài toán xếp n quân hậu trên bàn cờ vua kích thước n x n sao cho không có hai quân hậu nào cùng đứng trên một hàng, một cột hoặc một đường chéo:

public class NQueensProblem {
    int n;
    int[] cols;
 
    public NQueensProblem(int n) {
        this.n = n;
        cols = new int[n];
    }
 
    public void solve() {
        if (placeQueens(0)) {
            printQueens();
        } else {
            System.out.println("Không có giải pháp cho bài toán");
        }
    }
 
    private boolean placeQueens(int row) {
        if (row == n) {
            return true;
        }
        for (int col = 0; col < n; col++) {
            cols[row] = col;
            if (isValid(row)) {
                if (placeQueens(row + 1)) {
                    return true;
                }
            }
        }
        return false;
    }
 
    private boolean isValid(int row) {
        for (int i = 0; i < row; i++) {
            if (cols[row] == cols[i] || (row - i) == Math.abs(cols[row] - cols[i])) {
                return false;
            }
        }
        return true;
    }
 
    private void printQueens() {
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                if (cols[row] == col) {
                    System.out.print("Q ");
                } else {
                    System.out.print("- ");
                }
            }
            System.out.println();
        }
    }
}

Trong ví dụ này, thuật toán quay lui được sử dụng để liệt kê tất cả các trường hợp có thể xếp n quân hậu trên bàn cờ vua. Hàm placeQueens() đưa ra một giải pháp cho mỗi hàng của bàn cờ và tiếp tục đệ quy để tìm giải pháp cho hàng tiếp theo. Hàm isValid() được sử dụng để kiểm tra xem một vị trí trên bàn cờ có hợp lệ cho quân hậu hay không. Nếu tìm thấy giải pháp hợp lệ, thuật toán sẽ in ra bàn cờ với các quân hậu được đánh dấu là ‘Q’. Nếu không tìm thấy giải pháp hợp lệ, thuật toán sẽ thông báo rằng không có giải pháp cho bài toán.

Lập trình Java

Thuật toán quay lui trong java

Trả lời Hủy