[アルゴリズム]遡及

8060 ワード
algorithm テキストリンク

遡及定義

  • 遡及または退却探索と呼ぶ.
  • 制約条件が問題における探索解を満たす戦略は,特別なアルゴリズムではない.
  • 解を求めるために候補群の中で制約条件を漸進的にチェックし、その候補群が制約条件を満たすことができないと判断した場合、直ちに他の候補群に遡り、計算量を減らす方法.
  • 実際に実施した場合、全ての考慮可能な状況の数を状態空間ツリーとして表す.
  • DFS方式で各候補群を確認
  • 状態空間ツリーでナビゲートし、制約が不適切であれば解の候補となる位置に直接ジャンプ
  • Promissing:該当ルートが条件に合っているかチェックするテクニック
  • 剪定(修枝):条件に合わないまま諦めて、そのまま他のルートに転向して探索時間を節約する方法
    backtrackingは、ツリー構造に基づいてDFSを使用して深度ナビゲーションを行い、各ルートディレクトリが条件に合致しているかどうかを確認します.ツリー内の条件に合致しないノードがDFSを使用して深度ナビゲーションを行わなくなった場合、ブランチを破棄します.

    • N Queen問題例



    に答える

  • 一行に皇后は一人しか存在しない->皇后は上、下、左、右の対角線に移動できるからです.
  • ツリー構造で、一箇所でQueenが存在するかを確認し、存在しない場合はそのノードを削除し、すべての候補群を除外する.
  • DFS方式で解決.

    • コード#コード#

    #include <iostream>

using namespace std;

int queen_col[15] = {0};
int cnt = 0;

//현재 들어온 열 값이 가능한지 여부 판단
bool is_available(int current_row) {
	for (int row = 0; row < current_row; row++) {
		// 같은 열에 있어도 안되고, 대각선이 있어도 안된다.
		if ((queen_col[row] == queen_col[current_row]) || (current_row - row == abs(queen_col[current_row] - queen_col[row]))) {
			return false;
		}
	}
	return true;
}

void nqueen(int N, int current_row) {
	if (current_row == N) { //끝까지 다 놓은 경우 성공
		cnt++; //개수 +1
		return;
	}
	for (int col = 0; col < N; col++) {
		queen_col[current_row] = col; //현재 행에 후보 열을 놓아보고
		if (is_available(current_row)) {
			nqueen(N, current_row + 1); //가능하면 DFS
		}//안되면 후보 열 전체 탈락
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	nqueen(N, 0 );
	cout << cnt << '\n';

	return 0;
}
    swift構造体(Structures)とクラス(Class)の違い
    [SQL]-索引の概念