Bagaimana untuk menggunakan backtracking untuk mencapai penyelesaian yang cekap kepada masalah pilih atur penuh dalam PHP?

Bagaimana untuk menggunakan backtracking untuk mencapai penyelesaian yang cekap kepada masalah pilih atur penuh dalam PHP?

Kaedah penjejakan belakang ialah algoritma yang biasa digunakan untuk menyelesaikan masalah pilih atur dan gabungan Ia boleh mencari semua penyelesaian yang mungkin dalam masa yang terhad. Dalam PHP, kita boleh menggunakan backtracking untuk menyelesaikan masalah pilih atur penuh dan mencari penyelesaian yang cekap.

Masalah pilih atur keseluruhan ialah masalah pilih atur dan gabungan klasik Matlamatnya adalah untuk mencari semua pilih atur yang mungkin diberikan satu set elemen berbeza. Sebagai contoh, untuk set elemen {1, 2, 3}, semua susunan yang mungkin ialah {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1 } , {3, 1, 2}, {3, 2, 1}.

Di bawah ini kami akan memperkenalkan cara menggunakan kaedah penjejakan belakang untuk menyelesaikan masalah pilih atur penuh, dan memberikan contoh kod PHP yang sepadan.

Langkah 1: Tentukan fungsi rekursif jumlah pilih atur

Pertama, kita perlu mentakrifkan fungsi rekursif untuk menjana jumlah pilih atur. Fungsi ini akan menerima parameter berikut:

1. Susunan yang dijana $curr: digunakan untuk menyimpan susunan yang dijana semasa
2. Himpunan elemen yang tidak dipilih $left: digunakan untuk menyimpan baki elemen yang tidak dipilih
3. Susunan storan hasil akhir $result: digunakan untuk menyimpan semua pilih atur penuh yang ditemui

Dalam fungsi rekursif, kita perlu menetapkan syarat penamatan. Apabila $left kosong, iaitu semua elemen telah dipilih, $curr ditambahkan pada $result dan dikembalikan.

Langkah 2: Melintasi set elemen yang tidak dipilih

Dalam fungsi rekursif, kita perlu melintasi set elemen yang tidak dipilih $left. Untuk setiap elemen $ele, kita perlu melakukan perkara berikut:

1. Alih keluar $ele dari $left
2. Tambah $ele ke $curr
3. Panggil secara rekursif fungsi yang menjana susunan penuh, menghantar $curr dan $ yang dikemas kini left
4. Tambah $ele kembali ke $left untuk meneruskan gelung seterusnya

Langkah 3: Panggil fungsi rekursif

Dalam fungsi utama kita perlu memulakan $curr dan $left, dan mencipta $result tatasusunan Kosong. Kemudian, panggil fungsi rekursif yang menjana pilih atur penuh.

Akhir sekali, kami mengembalikan $result sebagai hasilnya.

Berikut ialah contoh kod PHP lengkap:

function permute($nums) {
    $result = [];
    backtrack([], $nums, $result);
    return $result;
}

function backtrack($curr, $left, &$result) {
    if (empty($left)) {
        $result[] = $curr;
        return;
    }

    for ($i = 0; $i < count($left); $i++) {
        $ele = $left[$i];
        array_splice($left, $i, 1);
        array_push($curr, $ele);
        backtrack($curr, $left, $result);
        array_pop($curr);
        array_splice($left, $i, 0, $ele);
    }
}

// Usage example
$nums = [1, 2, 3];
$result = permute($nums);
print_r($result);

Dalam kod contoh di atas, kami menghantar koleksi elemen yang diberikan $nums sebagai parameter kepada permute fungsi utama. Backtrack fungsi rekursif dipanggil dalam fungsi utama dan tatasusunan kosong $curr dan $nums dihantar masuk. Dalam fungsi rekursif, kami menyimpan pilih atur penuh yang terhasil dalam $result.

Jalankan kod contoh di atas dan semua pengaturan yang mungkin akan dikeluarkan.

Dengan menggunakan kaedah backtracking, kami boleh menyelesaikan masalah pilih atur penuh dalam PHP dengan cekap. Perlu diingat bahawa apabila menyelesaikan masalah pilih atur dan gabungan, kerumitan masa kaedah menjejak ke belakang ialah O(n!), dengan n ialah bilangan elemen. Oleh itu, masalah pilih atur dan gabungan yang melibatkan sejumlah besar elemen boleh mengakibatkan kerumitan masa yang tinggi.

Atas ialah kandungan terperinci Bagaimana untuk menggunakan backtracking untuk mencapai penyelesaian yang cekap kepada masalah pilih atur penuh dalam PHP?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!