Application de la fonction récursive C++ dans l'algorithme de backtracking ?

Les fonctions récursives résolvent les problèmes en recherchant d'abord en profondeur l'arbre de décision dans l'algorithme de backtracking : la fonction s'appelle elle-même, explorant les branches de l'arbre de décision. En réponse au problème, la fonction continuera à explorer en profondeur la structure arborescente et à revenir en arrière après avoir pris de mauvaises décisions. Cas pratique : Dans le problème des huit reines, la fonction place les reines de manière récursive et revient en arrière pour annuler les reines mal placées, et trouve finalement une solution qui répond aux exigences.

Application C++ de la fonction récursive dans l'algorithme de retour en arrière

L'algorithme de retour en arrière est un algorithme basé sur la recherche en profondeur d'abord, qui résout les problèmes en explorant en profondeur l'arbre de décision et en revenant en arrière après avoir pris de mauvaises décisions. Les fonctions récursives jouent un rôle crucial dans les algorithmes de backtracking, permettant à la fonction de s'appeler pour explorer les branches d'un arbre de décision.

Code :

En C++, on peut utiliser des fonctions récursives pour implémenter des algorithmes de backtracking, comme la résolution du problème des huit reines :

#include <iostream>
#include <vector>
using namespace std;

// 八皇后问题
bool solveNQueens(vector<vector<int>>& board, int n, int row) {
  if (row == n) {
    return true; // 找到一个解
  }

  for (int col = 0; col < n; col++) {
    if (isSafe(board, row, col)) {
      board[row][col] = 1;  // 放置皇后

      if (solveNQueens(board, n, row + 1)) {
        return true; // 在该分支中找到解
      }

      board[row][col] = 0;  // 回溯：移除皇后
    }
  }

  return false; // 未找到解
}

bool isSafe(vector<vector<int>>& board, int row, int col) {
  for (int i = 0; i < row; i++) {
    if (board[i][col] == 1) {
      return false; // 列冲突
    }
    if (board[i][col - row + i] == 1) {
      return false; // 左对角线冲突
    }
    if (board[i][col + row - i] == 1) {
      return false; // 右对角线冲突
    }
  }
  return true; // 该位置安全
}

int main() {
  int n;
  cout << "请输入棋盘大小：";
  cin >> n;

  vector<vector<int>> board(n, vector<int>(n, 0));

  if (solveNQueens(board, n, 0)) {
    cout << "找到解：\n";
    for (auto& row : board) {
      for (auto& cell : row) {
        cout << cell << " ";
      }
      cout << "\n";
    }
  } else {
    cout << "未找到解\n";
  }

  return 0;
}

Cas pratique :

Le problème des huit reines est une optimisation combinatoire bien connue problème. Vous devez placer 8 reines sur un échiquier 8x8 pour qu'elles ne s'attaquent pas. Ce code montre comment utiliser une fonction récursive et un algorithme de retour en arrière pour résoudre ce problème et afficher la solution sous forme de damier.

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!