[algo]遡及(BackTracking)とは?

バックトラック

aka. リトラクトスキャン
コンストレイントが問題を満たすときに解を検索するポリシー
すべての解くベクトルを作成してナビゲートするBrooke Forceは、時間と空間の複雑さを増し、必要な時間内に問題を解くことができません.
1つの解を探すために、候補群で制約条件を逐次チェックし、その候補群が制約条件を満たすことができないと判断した場合、すぐに戻り(候補をチェックしないマーク)、直接別の候補群に移動し、最終的に最適な解を見つける方法
「ステータススペースツリー」(State Space Tree)により、実際の実装で考慮できるすべての候補数を表す
DFS方式で各候補を決定する
ステートスペースツリーでナビゲートし、コンストレイントが一致しない場合は、解の候補として使用できる場所に直接移動します.

じょうたいくうかんじゅ
Promissing:ルートディレクトリが条件を満たしているかどうかを確認するテクノロジー
Prunning(枝切り):条件に合致しない場合は放棄し、直接別のルートに戻り、ナビゲーション時間を節約する方法
すなわち、ツリー構造に基づくDFSで深度ナビゲーションを行うと、各ルートディレクトリが条件を満たしているかどうかがチェックされ、このツリー(ツリー)で条件を満たしていないノードがDFSを使用して深度ナビゲーションを行わずにブランチが破棄される(Prunning)

典型的な遡及問題

N-Queen

https://velog.io/@letsbrave/backjun-963-N-Queen

import sys

n = int(sys.stdin.readline())
mlist=[0]*n

def check(mlist, row): # Promising : 해당 행에 원소 배치해도 되는지 검사
    for i in range(row):
        if mlist[i] == mlist[row] or abs(mlist[row]-mlist[i]) == row - i:
            return False # 방문할 수 없는 경우이므로 False 주기
    return True

def search(mlist, row):
    count = 0
    if n == row:
        return 1
    
    for col in range(n):
        mlist[row] = col
        if check(mlist, row): # 퀸들이 이동할 수 없을 경우엔 다음 컬렴 (백트래킹)
            count += search(mlist, row+1)
    
    return count

print(search(mlist, 0))

ソース

https://devlog-wjdrbs96.tistory.com/105
https://it00.tistory.com/26