Thuật toán quay lui trong C++

Lập trình C++

Thuật toán quay lui là một phương pháp giải quyết bài toán bằng cách liệt kê tất cả các trường hợp có thể xảy ra và kiểm tra từng trường hợp để tìm ra kết quả chính xác. Thuật toán này thường được sử dụng khi ta cần tìm tất cả các giải pháp có thể cho một bài toán, ví dụ như bài toán xếp hậu, xếp túi, tô màu đồ thị, hoặc tìm kiếm đường đi ngắn nhất trên đồ thị.

Cách thức hoạt động của thuật toán quay lui là liệt kê tất cả các khả năng có thể xảy ra bằng cách sử dụng phương pháp đệ quy để duyệt qua tất cả các trường hợp. Khi duyệt đến một trường hợp nào đó, ta kiểm tra xem trường hợp này có thể là một giải pháp chính xác hay không. Nếu đúng, ta lưu lại giải pháp đó và tiếp tục duyệt đến các trường hợp khác. Nếu sai, ta quay lại trạng thái trước đó và thử các khả năng khác.

Các bước thực hiện thuật toán quay lui như sau:

  1. Khởi tạo trạng thái ban đầu của bài toán.

  2. Sử dụng phương pháp đệ quy để duyệt qua tất cả các trường hợp có thể xảy ra.

  3. Kiểm tra xem trạng thái hiện tại có phải là một giải pháp chính xác hay không. Nếu đúng, lưu lại giải pháp và tiếp tục duyệt đến các trạng thái khác.

  4. Nếu trạng thái hiện tại không phải là một giải pháp chính xác, quay lại trạng thái trước đó và thử các khả năng khác.

  5. Nếu đã duyệt qua tất cả các trường hợp mà không tìm thấy giải pháp chính xác, kết thúc thuật toán.

Các ưu điểm của thuật toán quay lui là có thể tìm ra tất cả các giải pháp có thể cho một bài toán và có thể dễ dàng hiểu và triển khai. Tuy nhiên, nhược điểm của thuật toán này là độ phức tạp tính toán và thời gian thực thi có thể rất lớn, đặc biệt là đối với các bài toán lớn và phức tạp.

Để triển khai thuật toán quay lui trong C++, ta có thể sử dụng các hàm đệ quy và các cấu trúc dữ liệu như mảng hoặc vector để lưu trữ các trạng thái và các giải pháp. Sau đây là một ví dụ về cách triển khai thuật toán quay lui để giải bài toán xếp hậu:

#include <iostream>
using namespace std;

const int N = 8; // số quân hậu và kích thước bàn cờ
int x[N], y[N]; // lưu trữ vị trí các quân hậu

bool check(int i, int j) {
    for (int k = 0; k < i; k++) {
        if (y[k] == j || abs(i - k) == abs(j - y[k])) {
            return false; // kiểm tra xem quân hậu ở vị trí (i,j) có bị tấn công bởi các quân hậu khác hay không
        }
    }
    return true;
}

void solve(int i) {
    if (i == N) { // nếu đã đặt được N quân hậu
        for (int j = 0; j < N; j++) {
            cout << "(" << x[j] << ", " << y[j] << ") "; // in ra giải pháp
        }
        cout << endl;
        return;
    }
    for (int j = 0; j < N; j++) {
        if (check(i, j)) { // kiểm tra xem có thể đặt quân hậu ở vị trí (i,j) hay không
            x[i] = i;
            y[i] = j;
            solve(i + 1); // tiếp tục đặt quân hậu ở vị trí tiếp theo
        }
    }
}

int main() {
    solve(0); // bắt đầu tìm kiếm giải pháp từ quân hậu đầu tiên
    return 0;
}

Trong ví dụ trên, hàm check được sử dụng để kiểm tra xem quân hậu ở vị trí (i,j) có bị tấn công bởi các quân hậu khác hay không. Hàm solve được sử dụng để duyệt qua tất cả các trường hợp và tìm ra tất cả các giải pháp có thể. Khi đã đặt được N quân hậu, hàm sẽ in ra giải pháp tìm được. Hàm main được sử dụng để bắt đầu tìm kiếm giải pháp từ quân hậu đầu tiên./.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *