📍 フルナビゲーション

完全ナビゲーションは、コンピュータの高速計算性能を利用して、可能な限り任意の数をナビゲートする方法です.
「無知に解決する」とも言われるブルート・フォース.
すべての場合、ナビゲーションの精度は100%、効率は0です.
したがって、所与のNの大きさが小さい場合に使用することを推奨する.
「アルゴリズム」というより、問題を解決する方法です!

💡 5つの完全なナビゲーション方法

完全ナビゲーション・メソッドを使用して問題を解決するには、次の操作を考慮して実行します.
1.解決すべき問題の可能な数を大まかに計算する
2.あらゆる可能な方法を考える
3.アプリケーションが実際の答えを得ることができるかどうか
上記2で述べた「すべての方法」5つ
1.簡単なプレゼンテーション
2.並べ替え
3.再コール
4.ビットマスク
5. BFS, DFS

🔹 簡単なクイックフォーラム

条件文を使用してすべての単純なメソッドを検索
ex)ロックパスワードを検索する場合(0000～9999)

🔹 BFS、DFS利用

グラフィックデータ構造ですべての頂点をナビゲートする方法
ex)単純な探索問題=>BFS,DFS/障害物,追加先など他のタスクに必要な問題=>完全ナビゲーション+BFS,DFS

🔹 整列

任意の数列がある場合、数列をどのように利用して異なる順序で演算するか.
異なるN個の列を一列にする数=N!//Nは一桁程度です.
完全ナビゲーションの典型的なタイプ
ex)n個の数字で可能なすべてのシーケンスを作成するときのカウント

🔸 再帰呼び出し

再帰関数による解決方法
ex)ローカル集合問題で、作成するローカル集合S′の場合、S′={}となり、各要素にその要素が含まれている場合は、それをS′に入れ、再帰関数を呼び出し、含まれていない場合は、S′を直接再帰関数に入れる.

🔸 ビットマスク

ビット(bit)演算による部分セットの表示方法
ex)上記の再帰呼び出しと同様に,主に各要素を含む場合や含まない2つの選択からなる場合に用いられる.

かんぜんたんさく

コンビネーション・イテレーション:product、置換、コンビネーション、コンビネーションwith replacement

import itertools

# product, 곱집합
# product(p, q, … [repeat=1])
a = [1, 2, 3, 4]
aa = list(itertools.product(a, a))
print(aa) # [(1, 1), (1, 2), (1, 3), (1, 4), ... , (4, 1), (4, 2), (4, 3), (4, 4)]

b = list(itertools.product('1234', repeat=2))
print(b) # [('1', '1'), ('1', '2'), ('1', '3'), ... , ('4', '2'), ('4', '3'), ('4', '4')]

# permutations, 순열
# permutations(p[, r])
# 가능한 모든 순서를 반환, 반복되는 요소 없음
permutations_a = list(itertools.permutations(a))
print(permutations_a) # [(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2), (2, 1, 3, 4), (2, 1, 4, 3), (2, 3, 1, 4), (2, 3, 4, 1), (2, 4, 1, 3), (2, 4, 3, 1), (3, 1, 2, 4), (3, 1, 4, 2), (3, 2, 1, 4), (3, 2, 4, 1), (3, 4, 1, 2), (3, 4, 2, 1), (4, 1, 2, 3), (4, 1, 3, 2), (4, 2, 1, 3), (4, 2, 3, 1), (4, 3, 1, 2), (4, 3, 2, 1)]

permutations_a = list(itertools.permutations(a, 2))
print(permutations_a) # [(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]

permutations_a = list(itertools.permutations(a, 3))
print(permutations_a) # [(1, 2, 3), (1, 2, 4), (1, 3, 2), (1, 3, 4), (1, 4, 2), (1, 4, 3), (2, 1, 3), (2, 1, 4), (2, 3, 1), (2, 3, 4), (2, 4, 1), (2, 4, 3), (3, 1, 2), (3, 1, 4), (3, 2, 1), (3, 2, 4), (3, 4, 1), (3, 4, 2), (4, 1, 2), (4, 1, 3), (4, 2, 1), (4, 2, 3), (4, 3, 1), (4, 3, 2)]

# combinations, 조합
# combinatinos(p, r)
# 반복되는 요소가 없는 정렬된 순서
combinations_a = list(itertools.combinations(a, 2))
print(combinations_a) # [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

combinations_a = list(itertools.combinations(a, 3))
print(combinations_a) # [(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]

# combinations_with_replacement, 중복이 가능한 조합
# combinations_with_replacement(p, r)
# 조합에서 개별 요소마다 두 번 이상 반복할 수 있음
combinations_with_replacement_a = list(itertools.combinations_with_replacement(a, 2))
print(combinations_with_replacement_a) # [(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)]

combinations_with_replacement_a = list(itertools.combinations_with_replacement(a, 3))
print(combinations_with_replacement_a) # [(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 3, 3), (1, 3, 4), (1, 4, 4), (2, 2, 2), (2, 2, 3), (2, 2, 4), (2, 3, 3), (2, 3, 4), (2, 4, 4), (3, 3, 3), (3, 3, 4), (3, 4, 4), (4, 4, 4)]

完全探索はいつ使えばいいですか?

通常、完全ナビゲーションの問題は、for文とif文を使用するか、BFS/DFSを使用するかです.
また、完全なナビゲーションの問題を解決するためにソートを利用する方法もよくあります.

入力データ(N)が非常に小さい場合
ほとんどの場合,完全ナビゲーション問題のNは非常に小さい.
完全ナビゲーションで問題を解くと,時間的複雑さは基本的にO(2^N)またはO(N!)である.したがって、Nは非常に小さくなければならない.

答えの範囲が小さく、任意の答えを選択すると、問題条件を満たすかどうかを逆方向に追跡できます.
答えの範囲が非常に限られている場合、任意の固定答えを決定し、与えられた条件が答えに適しているかどうかを決定する方法(可能なすべての答えを決定する過程で完全検索を使用する)を使用することができます.

📑 リファレンス

アルゴリズム-穷挙検索
完全検索アルゴリズム
コーディングテストの準備に必要なコンセプト!<フルナビゲーション>了解