Penggunaan fungsi rekursif C++ dalam algoritma penjejakan belakang?

Fungsi rekursif menyelesaikan masalah dengan mencari pepohon keputusan secara mendalam dahulu dalam algoritma penjejakan ke belakang: fungsi itu memanggil dirinya sendiri, meneroka cabang pepohon keputusan. Sebagai tindak balas kepada masalah itu, fungsi akan terus meneroka struktur pokok secara mendalam dan mundur selepas membuat keputusan yang salah. Kes praktikal: Dalam masalah lapan ratu, fungsi secara rekursif meletakkan ratu dan berundur untuk membuat asal ratu yang diletakkan dengan salah, dan akhirnya menemui penyelesaian yang memenuhi keperluan.

C++ Aplikasi fungsi rekursif dalam algoritma penjejakan belakang

Algoritma penjejakan belakang ialah algoritma berdasarkan carian mendalam-pertama, yang menyelesaikan masalah dengan meneroka pepohon keputusan secara mendalam dan menjejak ke belakang selepas membuat keputusan yang salah. Fungsi rekursif memainkan peranan penting dalam algoritma penjejakan ke belakang, membenarkan fungsi memanggil dirinya sendiri untuk meneroka cabang pokok keputusan.

Kod:

Dalam C++, kita boleh menggunakan fungsi rekursif untuk melaksanakan algoritma penjejakan ke belakang, seperti menyelesaikan masalah lapan ratu:

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

Kes praktikal:

Masalah pengoptimuman yang terkenal ialah gabungan lapan ratu. masalah. Anda perlu meletakkan 8 ratu pada papan catur 8x8 supaya mereka tidak menyerang satu sama lain. Kod ini menunjukkan cara menggunakan fungsi rekursif dan algoritma penjejakan ke belakang untuk menyelesaikan masalah ini dan mengeluarkan penyelesaian dalam format papan dam.

Atas ialah kandungan terperinci Penggunaan fungsi rekursif C++ dalam algoritma penjejakan belakang?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!