[アルゴリズム]深度優先ナビゲーション(DFS)、バックトラック(BackTracking)

1.優先ブラウズ深度
グラフィックブラウズは、1つの頂点からすべての頂点に1回アクセスします.深度優先探索(Depth Priority Search)は、ある頂点から次のブランチに至るまで、そのブランチをすべて探索するグラフィック探索法の一種である.
主にすべてのノードにアクセスする必要がある場合にこの方法を選択します.幅優先ブラウズ(BFS)より簡単ですが、検索速度が遅い場合があります.シールド不要の場合などの処理がないため、ケースの数を減らすことはできません.Nだから!N!N!の場合、数の問題はDFSでは解決できません.また,最短経路を求める問題では,この解は最短経路ではない可能性がある.太陽になると探索が終わるからだ.
木を基準にしてみると、サブノードのサブノードについて突き当たりまで歩き、葉に出会うまで深く探索する.迷宮探索の例では、ずっと1本の道を歩き続け、続けられないうちに前の分かれ道に戻り、別の道を選ぶ.
グラフィックブラウズを使用する場合は、無限ループに陥らないように、ノードにアクセスしたかどうかを確認する必要があります.
再帰関数やスタックで実現できます.ナビゲートするノードをスタックに挿入してアクセス処理を行った後(A)、スタックの最上位ノードに未アクセスの隣接ノードがある場合はスタックに入れてアクセス処理を行う(B).アクセスされていないノードがない場合は、スタック内でpopします.(B)この処理を実行できなくなるまで繰り返す.
2.バックトレース
バックトラック(Back Tracking)は、深度優先探索(DFS)から不要なブランチを枝切り(枝切り)する方法であり、探索中に答えが得られない(希望がない)場合には、さらなる処理を行わず、親ノードに戻って他の年を探す方法である.
これはDFSを必要とせずに全てのナビゲーションを行うことを制限できる方法である.条件文などのデバイス定義で解決できない場合、DFSに該当する場合はブラウズを停止し、前四半期に戻ります.
3.例題
3-1. N-Queen(プログラマー)
👉 質問リンク
🔍 解き方
N-Queenは「8皇后問題」の一般化で、NXNチェス盤にN個の皇后を置き、一度に相手を攻撃できなければ数を求めることができます.
この問題では、以下のbacktrackingを使用することができます.

上図は列を基準として,筆者は行動基準で探索した.col_numは、n個の列について、その位置の数行目にQueenが置かれていることを示す.col_num[a] = bといえば、a列とb行に皇后がいることを意味します.これにより、特定の位置でcol_numを参照して、その位置に皇后を置くことができるかどうかを知ることができる.

### r행 c열에 퀸을 놓을 수 있는지 없는지
def is_possible(r, c, n, col_num):
    for i in range(r):
        if col_num[i] == c or (r - i) == abs(c - col_num[i]):
        	# 대각선은 col_num[i] 위치의 퀸과 나 사이의 row값 차와 col값 차가 같음을 이용했다.
            return False
    return True

### r행을 탐색하며 퀸을 놓을 자리를 찾음
def queen(r, n, col_num):
    if r == n:  
    	#r행이 n이라면 끝까지 탐색이 끝났으므로 성공한 것.
        return 1
    
    cnt = 0  # 경우의 수

    for c in range(n):  # 0열부터 n-1 열까지 순차적으로 탐색함
        if is_possible(r, c, n, col_num):
        	# 그 자리에 놓을 수 있다면 이 행의 col_num에 이 열의 번호를 기록하고 다음 행으로 넘어감
            col_num[r] = c
            cnt += queen(r+1, n, col_num)
    
    return cnt


def solution(n):
    col_num = [0] * n
    return queen(0, n, col_num)

参考資料

Heejeon Kwon，[[アルゴリズム]深度優先ナビゲーション(DFS)]GitHub blog gmlwjd 9405

頭を上げて、「DFS&BFS(C++)」を理解して実施し、「Tistoryをクリーンアップする」

ChanhuiSeok、「アルゴリズム-遡及」の定義と例の問題、「GitHub blog ChanBLOG

Sooyoung，"N-Queenアルゴリズム"，GitHub blog sooyoung 32

Kingsmo，「プログラマ-[LEVEL 3]N-Queen，」Tistoryデータエンジニア

「八皇后問題」ウィキペディア。