[アルゴリズム]完全ナビゲーション

1.完全ナビゲーションアルゴリズムとは？

완전탐색は、可能な限り、すべての数字を調べて正解を探す方法で、可能なことを無知に試してみることを意味し、Brute Forceとも呼ばれています.

2.完全ナビゲーションアルゴリズムを利用する

2-1. フルナビゲーションアルゴリズムアクションプロセス

約

で解決する可能性のある問題の数

を計算します.

可能な限り

に適用される実際の答え

2-2. 完全ナビゲーションのタイプ

1）Brute Force技術

Brute Force 기법とは,反復/条件文によって単純に可能なすべての方法を探す場合を指す.たとえば、4桁のデジタルロックを開くと、最悪の場合は100000*1秒=約166分(コンピュータの演算速度:約1秒1億)です.

2）遡及（BackTracking）

백트래킹 (Backtracking)は、現在の状態において可能な候補群で探索するアルゴリズムである.分割征服の手法では,再帰関数を用いて解を探す過程で解にならないような経路があれば,これ以上行かずに戻る.

3）シーケンス（Permutation）

순열は、任意の数列が与えられたときに異なる順序で演算する方法である.異なるN個を一列に並べた場合、数はN!したがって、完全ナビゲーションを使用するためには、Nは1桁でなければならない.

from itertools import permutations

permutations(arr, n) 
# permutations 이용
# n개씩 순열 조합해서 모든 경우의 수 판정

4）ビットマスク

비트 마스크 (Bit Mask)は、バイナリ数を用いたコンピュータ演算の方式である.完全検索では、問題で発生する可能性のあるすべての状況数각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우にビットマスクを使用することができる.
たとえば、1つの要素が5つの集合のすべての部分集合であることを考慮すると、ある集合の部分集合には、集合の各要素がその部分集合に含まれているか、またはその部分集合に含まれていないかの2つのケースしか存在しません.したがって、5ビットのバイナリ数を使用して、各要素が含まれているかどうかを確認できます.

5）再帰関数

これは、재귀함수によって問題を満たす場合を製造する方法である.
前述した部分集合問題を例にとると、作成する部分集合を「S」と呼ぶ場合、「S'={}」から各要素について、その要素が含まれている場合は「S」に入れ、再帰関数を返し、含まれていない場合は「S」を直接再帰関数に入れる.
ビットマスクと同様に、主に各要素を含むか含まないかの2つの選択に使用されます.

6) DFS/BFS

DFS/BFSアルゴリズム
ちょっと難しい問題は완전탐색 + DFS/BFS題もたくさん出ています.例えば、道を探すだけの問題であればDFS/BFSのみで十分であるが、所与の道路に障害物を設置したり、目的地を追加したりするなどの他の操作が必要であれば、これらの問題を完全なナビゲーションで解決してからDFS/BFSを使用する必要がある.
👉 リファレンス
アルゴリズム-穷挙検索
完全検索アルゴリズム