C++ 再帰関数をバックトラッキング アルゴリズムに適用しますか?

再帰関数は、バックトラッキング アルゴリズムでデシジョン ツリーを深さ優先検索することで問題を解決します。関数はそれ自体を呼び出し、デシジョン ツリーの分岐を探索します。この問題に対応して、関数はツリー構造を深く調査し続け、誤った決定を下した場合には後戻りします。実際のケース: 8 クイーン問題では、関数はクイーンを再帰的に配置し、間違って配置されたクイーンを元に戻すためにバックトラックし、最終的に要件を満たす解を見つけます。

#C バックトラッキング アルゴリズムにおける再帰関数の適用

バックトラッキング アルゴリズムは、デシジョン ツリーを深く探索する深さ優先探索に基づくアルゴリズムです。そして、間違った決定を下した後、問題を解決するために後戻りすることもあります。再帰関数はアルゴリズムのバックトラッキングにおいて重要な役割を果たし、関数がそれ自体を呼び出してデシジョン ツリーの分岐を探索できるようにします。

コード:

C では、再帰関数を使用して、8 クイーン問題を解くなどのバックトラッキング アルゴリズムを実装できます:

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

実際のケース:

8 クイーン問題は、よく知られた組み合わせ最適化問題です。8 つのクイーンを互いに攻撃しないように 8x8 のチェス盤に配置する必要があります。このコードは、再帰関数とバックトラッキング アルゴリズムを使用してこの問題を解決し、解決策をチェッカーボード形式で出力する方法を示しています。

以上がC++ 再帰関数をバックトラッキング アルゴリズムに適用しますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。