역추적 알고리즘에 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개의 여왕 문제는 잘 알려진 조합입니다. 최적화 문제 8x8 체스판에 8개의 퀸을 배치하여 서로 공격하지 않도록 해야 합니다. 이 코드는 재귀 함수와 역추적 알고리즘을 사용하여 이 문제를 해결하고 솔루션을 체커보드 형식으로 출력하는 방법을 보여줍니다.

위 내용은 역추적 알고리즘에 C++ 재귀 함수를 적용합니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!