Kaedah pelaksanaan algoritma backtracking dalam PHP

Kaedah pelaksanaan algoritma penjejakan belakang dalam PHP

Algoritma penjejakan belakang ialah kaedah yang biasa digunakan untuk menyelesaikan masalah Idea terasnya ialah mencuba semua penyelesaian yang mungkin secara rekursif, dan kemudian menapis mengikut keperluan masalah untuk mencari penyelesaian yang memenuhi syarat. penyelesaian yang optimum.

Dalam PHP, kita boleh menggunakan algoritma penjejakan belakang untuk menyelesaikan satu siri masalah seperti masalah gabungan, masalah pilih atur, labirin, dll. Di bawah ini kami akan memperkenalkan cara melaksanakan algoritma penjejakan belakang dalam PHP dan memberikan contoh kod.

1. Implementasi algoritma penjejakan belakang masalah kombinatorial

Masalah gabungan merujuk kepada memilih beberapa elemen daripada set tertentu supaya elemen yang dipilih memenuhi syarat tertentu. Ambil kombinasi C(n, k) sebagai contoh, di mana n mewakili saiz set yang diberikan dan k mewakili bilangan elemen yang akan dipilih. Berikut ialah contoh pelaksanaan algoritma backtracking dalam PHP untuk menyelesaikan masalah gabungan:

function backtrack($nums, $k, $start, $track, &$res) {
    if (count($track) == $k) {
        $res[] = $track;
        return;
    }
    
    for ($i = $start; $i < count($nums); $i++) {
        $track[] = $nums[$i];
        backtrack($nums, $k, $i + 1, $track, $res);
        array_pop($track);
    }
}

function combine($n, $k) {
    $nums = [];
    for ($i = 1; $i <= $n; $i++) {
        $nums[] = $i;
    }
    
    $res = [];
    backtrack($nums, $k, 0, [], $res);
    return $res;
}

$n = 4;
$k = 2;
$result = combine($n, $k);
print_r($result);

Dalam kod di atas, fungsi backtrack digunakan untuk melakukan carian backtracking. Apabila bilangan elemen yang dipilih adalah sama dengan k, kami merekodkan trek semasa ke dalam tatasusunan hasil $res. Kemudian buat panggilan rekursif dalam gelung for Parameter yang dilalui ialah set $nums yang diberikan, bilangan elemen yang akan dipilih $k, kedudukan permulaan yang dipilih pada masa ini $start, tatasusunan elemen $track yang dipilih dan tatasusunan Hasil. $res.

2. Implementasi algoritma penjejakan belakang untuk masalah pilih atur Ambil susunan P(n, k) sebagai contoh, di mana n mewakili saiz set yang diberikan dan k mewakili bilangan elemen yang akan dipilih. Berikut ialah contoh pelaksanaan algoritma backtracking untuk menyelesaikan masalah pilih atur dalam PHP:

function backtrack($nums, $k, &$visited, $track, &$res) {
    if (count($track) == $k) {
        $res[] = $track;
        return;
    }
    
    for ($i = 0; $i < count($nums); $i++) {
        if (!$visited[$i]) {
            $visited[$i] = true;
            $track[] = $nums[$i];
            backtrack($nums, $k, $visited, $track, $res);
            array_pop($track);
            $visited[$i] = false;
        }
    }
}

function permute($nums, $k) {
    $res = [];
    $visited = array_fill(0, count($nums), false);
    backtrack($nums, $k, $visited, [], $res);
    return $res;
}

$nums = [1, 2, 3];
$k = 2;
$result = permute($nums, $k);
print_r($result);

Dalam kod di atas, fungsi backtrack digunakan untuk melakukan carian backtracking. Apabila bilangan elemen yang dipilih adalah sama dengan k, kami merekodkan trek semasa ke dalam tatasusunan hasil $res. Dalam gelung untuk, kami memilih elemen yang tidak dilawati setiap kali dan menambahkannya pada trek. Kemudian buat panggilan rekursif Parameter yang dihantar adalah set $num yang diberikan, bilangan elemen yang akan dipilih $k, tatasusunan $dilawati yang merekodkan sama ada elemen semasa dilawati, tatasusunan elemen $track yang dipilih dan tatasusunan hasil.

Pelaksanaan algoritma penjejakan belakang untuk masalah labirin

3. Masalah labirin merujuk kepada mencari laluan dari titik permulaan ke titik akhir dalam labirin tertentu. Maze boleh diwakili oleh tatasusunan dua dimensi, di mana 0 mewakili grid boleh dilalui dan 1 mewakili halangan. Berikut ialah contoh pelaksanaan algoritma backtracking dalam PHP untuk menyelesaikan masalah maze:

function backtrack($maze, $i, $j, $path, &$res) {
    if ($i == count($maze) - 1 && $j == count($maze[0]) - 1) {
        $res[] = $path;
        return;
    }
    
    $maze[$i][$j] = -1;
    
    $dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    $dirNames = ['right', 'down', 'left', 'up'];
    
    for ($k = 0; $k < 4; $k++) {
        $ni = $i + $dirs[$k][0];
        $nj = $j + $dirs[$k][1];
        
        if ($ni >= 0 && $ni < count($maze) && $nj >= 0 && $nj < count($maze[0]) && $maze[$ni][$nj] == 0) {
            backtrack($maze, $ni, $nj, $path . ' -> ' . $dirNames[$k], $res);
        }
    }
    
    $maze[$i][$j] = 0;
}

function solveMaze($maze) {
    $res = [];
    backtrack($maze, 0, 0, '(0, 0)', $res);
    return $res;
}

$maze = [
    [0, 1, 0, 0],
    [0, 0, 0, 1],
    [1, 1, 0, 0],
    [0, 0, 0, 0]
];

$result = solveMaze($maze);
print_r($result);

Dalam kod di atas, fungsi backtrack digunakan untuk melakukan carian backtracking. Apabila kita mencapai titik akhir, kita merekodkan laluan laluan semasa ke dalam tatasusunan hasil $res. Dalam gelung for, kami cuba bergerak ke hadapan dalam empat arah: kanan, bawah, kiri dan atas serta membuat panggilan rekursif. Sebelum panggilan rekursif, kita perlu menentukan sama ada grid semasa ialah grid boleh dilalui dan menandakannya sebagai tidak boleh diakses untuk mengelakkan lawatan berulang.

Atas ialah kandungan terperinci Kaedah pelaksanaan algoritma backtracking dalam PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!