Comment utiliser l'algorithme de backtracking en C++

Comment utiliser l'algorithme de backtracking en C++

L'algorithme de backtracking est un algorithme qui résout un problème en essayant toutes les solutions possibles. Il est souvent utilisé pour résoudre des problèmes combinatoires, où le but est de trouver toutes les combinaisons possibles satisfaisant un ensemble de contraintes.

Prenons le problème de permutation comme exemple. Supposons qu'il existe un tableau nums et que nous devons y trouver toutes les permutations possibles. Ce qui suit présentera comment utiliser l'algorithme de backtracking pour résoudre ce problème à travers un exemple de code 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;
}

Exécutez le code ci-dessus, le résultat de sortie est :

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

Dans le code ci-dessus, nous utilisons l'algorithme de retour en arrière pour résoudre le problème de permutation. Fonction Backtrack backtrack通过深度优先搜索的方式尝试所有可能的排列，同时使用visitedtableau pour marquer les numéros qui ont été visités afin d'éviter la duplication. Lorsque la longueur de la permutation est égale à la longueur du tableau, la permutation actuelle est ajoutée au résultat.

À travers cet exemple, nous pouvons voir que l'idée centrale de l'algorithme de backtracking est d'essayer toutes les solutions possibles et de revenir en arrière lorsque la solution ne remplit pas les conditions. Dans les applications réelles, certaines optimisations peuvent être effectuées en fonction des exigences de problèmes spécifiques, telles que des opérations d'élagage pour réduire les tentatives inutiles. L’algorithme de backtracking possède de puissantes capacités de résolution de nombreux problèmes combinatoires. Pour les débutants, la maîtrise de l’algorithme de backtracking est très bénéfique.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!