C++ 遞迴函式在回溯演算法中的應用？

遞歸函數在回溯演算法中透過深度優先搜尋決策樹來解決問題：函數呼叫自身，探索決策樹的分支。針對問題，函數會不斷深入探索樹狀結構，並在做出錯誤決策後進行回溯。實戰案例：八皇后問題中，函數透過遞歸放置皇后，並透過回溯來撤銷錯誤放置的皇后，最終找到符合要求的解。

C 遞歸函數在回溯演算法中的應用

#是一種基於深度優先搜尋的演算法，它透過在決策樹上深度探索，並在做出錯誤的決策後回溯來解決問題。遞歸函數在回溯演算法中發揮著至關重要的作用，它允許函數呼叫自身來探索決策樹的分支。

程式碼：

在C 中，我們可以使用遞迴函數來實作回溯演算法，例如求解八皇后問題：

#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;
}

實戰案例：

八女王問題是一個著名的組合最佳化問題，它需要在8x8 棋盤上放置8 個皇后，使得它們彼此都不互相攻擊。本程式碼示範如何使用遞歸函數和回溯演算法來求解此問題，並以棋盤的形式輸出解。

以上是C++ 遞迴函式在回溯演算法中的應用？的詳細內容。更多資訊請關注PHP中文網其他相關文章！