Cara menggunakan algoritma backtracking dalam C++

Cara menggunakan algoritma penjejakan belakang dalam C++

Algoritma penjejakan belakang ialah algoritma yang menyelesaikan masalah dengan mencuba semua penyelesaian yang mungkin. Ia sering digunakan untuk menyelesaikan masalah gabungan, di mana matlamatnya adalah untuk mencari semua kemungkinan kombinasi yang memenuhi satu set kekangan.

Ambil masalah pilih atur sebagai contoh. Katakan terdapat nombor tatasusunan, dan kita perlu mencari semua pilih atur yang mungkin di dalamnya. Berikut akan memperkenalkan cara menggunakan algoritma penjejakan belakang untuk menyelesaikan masalah ini melalui contoh kod C++.

#include <iostream>
#include <vector>

using namespace std;

void backtrack(vector<int>& nums, vector<vector<int>>& res, vector<bool>& visited, vector<int>& permutation) {
    // 如果当前排列的长度等于数组长度，说明已经找到一种解法
    if (permutation.size() == nums.size()) {
        res.push_back(permutation);
        return;
    }
    
    for (int i = 0; i < nums.size(); i++) {
        // 如果当前数字已经被访问过，跳过继续下一次尝试
        if (visited[i]) {
            continue;
        }
        
        // 将当前数字添加到排列中
        permutation.push_back(nums[i]);
        visited[i] = true;
        
        // 继续尝试下一个数字
        backtrack(nums, res, visited, permutation);
        
        // 回溯，从排列中移除当前数字，重新标记为未访问状态
        permutation.pop_back();
        visited[i] = false;
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    vector<bool> visited(nums.size(), false);
    vector<int> permutation;
    backtrack(nums, res, visited, permutation);
    return res;
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> res = permute(nums);
    
    // 打印结果
    for (vector<int> permutation : res) {
        for (int num : permutation) {
            cout << num << " ";
        }
        cout << endl;
    }
    
    return 0;
}

Jalankan kod di atas, hasil output ialah:

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1

Dalam kod di atas, kami menggunakan algoritma penjejakan belakang untuk menyelesaikan masalah pilih atur. Fungsi backtrack backtrack通过深度优先搜索的方式尝试所有可能的排列，同时使用visitedarray untuk menandakan nombor yang telah dilawati untuk mengelakkan pertindihan. Apabila panjang pilih atur adalah sama dengan panjang tatasusunan, pilih atur semasa ditambah kepada hasilnya.

Melalui contoh ini, kita dapat melihat bahawa idea teras algoritma penjejakan ke belakang adalah untuk mencuba semua penyelesaian yang mungkin dan mengundur apabila penyelesaian tidak memenuhi syarat. Dalam aplikasi sebenar, beberapa pengoptimuman boleh dilakukan mengikut keperluan masalah tertentu, seperti operasi pemangkasan untuk mengurangkan percubaan yang tidak perlu. Algoritma penjejakan belakang mempunyai keupayaan penyelesaian yang hebat dalam banyak masalah gabungan Bagi pemula, menguasai algoritma penjejakan belakang sangat bermanfaat.

Atas ialah kandungan terperinci Cara menggunakan algoritma backtracking dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!