C++ 递归函数在回溯算法中的应用？-C++-PHP中文网

递归函数在回溯算法中通过深度优先搜索决策树来解决问题：函数调用自身，探索决策树的分支。针对问题，函数会不断深入探索树状结构，并在做出错误决策后进行回溯。实战案例：八皇后问题中，函数通过递归放置皇后，并通过回溯来撤销错误放置的皇后，最终找到符合要求的解。

C++ 递归函数在回溯算法中的应用？

C++ 递归函数在回溯算法中的应用

回溯算法是一种基于深度优先搜索的算法，它通过在决策树上深度探索，并在做出错误的决策后回溯来解决问题。递归函数在回溯算法中发挥着至关重要的作用，它允许函数调用自身来探索决策树的分支。

代码：

在 C++ 中，我们可以使用递归函数来实现回溯算法，例如求解八皇后问题：

Omneky

用最先进的深度学习为客定制个性化的广告

下载

立即学习“C++免费学习笔记（深入）”；

#include 
#include 
using namespace std;

// 八皇后问题
bool solveNQueens(vector>& 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>& 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> board(n, vector(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;
}

实战案例：

八皇后问题是一个著名的组合优化问题，它需要在 8x8 棋盘上放置 8 个皇后，使得它们彼此都不互相攻击。本代码演示了如何使用递归函数和回溯算法来求解此问题，并以棋盘的形式输出解。