Trong bài viết này, tôi sẽ cùng các bạn tìm hiểu về thuật toán quay lui (Backtracking) trong lập trình, đặc biệt là sử dụng PHP. Chúng ta sẽ đi từ những kiến thức cơ bản nhất đến các ví dụ nâng cao chuyên sâu, giúp các bạn có cái nhìn toàn diện và đầy đủ về thuật toán này.

1. Thuật Toán Quay Lui Là Gì?

Thuật toán quay lui (Backtracking) là một phương pháp tìm kiếm lời giải cho các bài toán lớn bằng cách thử các giải pháp từng bước một, bỏ qua những giải pháp không khả thi ngay khi phát hiện. Đây là một kỹ thuật rất hiệu quả trong việc giải quyết các bài toán tổ hợp phức tạp như tìm đường, phân hoạch biểu thức, hay các bài toán tối ưu.

1.1. Nguyên lý hoạt động

Thuật toán quay lui hoạt động theo nguyên lý sau:

Xuất phát từ một điểm khởi đầu.
Thử từng lựa chọn một theo thứ tự.
Nếu lựa chọn này không dẫn đến kết quả thỏa mãn, quay trở lại và thử lựa chọn tiếp theo.

Ví dụ minh họa

Chúng ta cùng xem lại ví dụ kinh điển về bài toán N-Queens. Đây là bài toán sắp xếp N quân hậu trên bàn cờ N x N sao cho không có hai quân hậu nào ăn nhau.

2. Cài Đặt Thuật Toán Quay Lui Trong PHP

2.1. Bài toán N-Queens

Cách tiếp cận

Giả sử chúng ta cần sắp xếp N quân hậu trên bàn cờ N x N, chúng ta sẽ sử dụng một mảng để lưu vị trí các quân hậu. Mỗi phần tử của mảng biểu thị vị trí của một quân hậu trên mỗi hàng.

Đoạn mã PHP

<?php
function isSafe($board, $row, $col, $N) {
    for ($i = 0; $i < $col; $i++)
        if ($board[$row][$i])
            return false;

    for ($i = $row, $j = $col; $i >= 0 && $j >= 0; $i--, $j--)
        if ($board[$i][$j])
            return false;

    for ($i = $row, $j = $col; $j >= 0 && $i < $N; $i++, $j--)
        if ($board[$i][$j])
            return false;

    return true;
}

function solveNQUtil($board, $col, $N) {
    if ($col >= $N)
        return true;

    for ($i = 0; $i < $N; $i++) {
        if (isSafe($board, $i, $col, $N)) {
            $board[$i][$col] = 1;
            if (solveNQUtil($board, $col + 1, $N))
                return true;
            $board[$i][$col] = 0;
        }
    }
    return false;
}

function solveNQ($N) {
    $board = array();
    for ($i = 0; $i < $N; $i++) {
        $board[$i] = array_fill(0, $N, 0);
    }

    if (!solveNQUtil($board, 0, $N)) {
        echo "Solution does not exist";
        return false;
    }

    for ($i = 0; $i < $N; $i++) {
        for ($j = 0; $j < $N; $j++) {
            echo $board[$i][$j] . " ";
        }
        echo "";
    }
    return true;
}

$N = 4;
solveNQ($N);
?>

2.2. Lời giải chi tiết

Phân tích từng bước của đoạn mã trên:

isSafe: Hàm kiểm tra xem liệu có thể đặt quân hậu tại vị trí này không.
solveNQUtil: Sử dụng hàm này để thử đặt quân hậu tại từng cột một theo cách quay lui.
solveNQ: Hàm này khởi tạo mảng bàn cờ và gọi hàm solveNQUtil để bắt đầu quá trình giải quyết.

3. Những Ứng Dụng Khác Của Thuật Toán Quay Lui

3.1. Tìm đường trong mê cung

Vấn đề là tìm đường đi từ điểm khởi đầu đến điểm kết thúc trong một mê cung với các bức tường chặn đường đi. Thuật toán quay lui có thể giúp chúng ta thử từng con đường từ điểm xuất phát đến điểm kết thúc và quay lại nếu gặp vật cản.

Ví dụ PHP

<?php
define('N', 4);

function isSafeMaze($maze, $x, $y) {
    return ($x >= 0 && $x < N && $y >= 0 && $y < N && $maze[$x][$y] == 1);
}

function printSolution($sol) {
    for ($i = 0; $i < N; $i++) {
        for ($j = 0; $j < N; $j++) {
            echo $sol[$i][$j] . " ";
        }
        echo "";
    }
}

function solveMazeUtil($maze, $x, $y, $sol) {
    if ($x == N - 1 && $y == N - 1 && $maze[$x][$y] == 1) {
        $sol[$x][$y] = 1;
        return true;
    }

    if (isSafeMaze($maze, $x, $y)) {
        if ($sol[$x][$y] == 1)
            return false;

        $sol[$x][$y] = 1;

        if (solveMazeUtil($maze, $x + 1, $y, $sol))
            return true;

        if (solveMazeUtil($maze, $x, $y + 1, $sol))
            return true;

        if (solveMazeUtil($maze, $x - 1, $y, $sol))
            return true;

        if (solveMazeUtil($maze, $x, $y - 1, $sol))
            return true;

        $sol[$x][$y] = 0;
        return false;
    }
    return false;
}

function solveMaze($maze) {
    $sol = array();
    for ($i = 0; $i < N; $i++)
        $sol[$i] = array_fill(0, N, 0);

    if (!solveMazeUtil($maze, 0, 0, $sol)) {
        echo "No solution";
        return false;
    }

    printSolution($sol);
    return true;
}

$maze = array(
    array(1, 0, 0, 0),
    array(1, 1, 0, 0),
    array(0, 1, 0, 0),
    array(1, 1, 1, 1)
);

solveMaze($maze);
?>

3.2. Bài toán phân hoạch (Subset Sum)

Bài toán là tìm một tập con của một tập hợp các số nguyên sao cho tổng các phần tử trong tập con đó bằng một giá trị cho trước. Thuật toán quay lui có thể giải quyết bài toán này bằng cách thử từng phần tử, thêm nó vào tập con hay bỏ qua nó, và quay lui khi không đạt yêu cầu.

Ví dụ PHP

<?php
function findSubsetSum($arr, $n, $sum) {
    if ($sum == 0)
        return true;
    if ($n == 0 && $sum != 0)
        return false;

    if ($arr[$n - 1] > $sum)
        return findSubsetSum($arr, $n - 1, $sum);

    return findSubsetSum($arr, $n - 1, $sum) || findSubsetSum($arr, $n - 1, $sum - $arr[$n - 1]);
}

$arr = array(3, 34, 4, 12, 5, 2);
$sum = 9;
$n = count($arr);
if (findSubsetSum($arr, $n, $sum))
    echo "Found a subset with given sum";
else
    echo "No subset with given sum";
?>

3.3. Chuỗi khác biệt nhỏ nhất (Shortest Common Supersequence)

Bài toán này tìm một chuỗi ngắn nhất có chứa tất cả các chuỗi đã cho là các chuỗi con. Đây là một bài toán phức tạp và có thể được giải bằng cách quay lui từng bước thử ghép các chuỗi với nhau.

Kết Luận

Như vậy, thuật toán quay lui là một công cụ mạnh mẽ trong việc giải quyết các bài toán tổ hợp phức tạp. Bằng cách hiểu rõ nguyên lý và áp dụng vào các bài toán cụ thể như N-Queens, tìm đường trong mê cung, và bài toán phân hoạch, các bạn đã nắm được cách thức hoạt động và ứng dụng của nó trong thực tế. Tôi hy vọng bài viết này sẽ giúp các bạn củng cố kiến thức và áp dụng thành công trong lập trình.