정보가 없는 검색 알고리즘

정보가 없는 검색은 무차별 방식으로 작동하는 범용 검색 알고리즘 클래스입니다. 무정보 탐색 알고리즘은 트리를 순회하는 방법 외에 상태나 탐색 공간에 대한 추가 정보가 없으므로 블라인드 탐색이라고도 합니다.

다음은 다양한 유형의 정보가 없는 검색 알고리즘입니다.

너비 우선 검색 깊이 우선 검색 깊이 제한 검색 반복 심화 깊이 우선 탐색 균일 비용 검색 양방향 검색

1. 너비 우선 검색:

너비 우선 검색은 트리나 그래프를 순회하는 가장 일반적인 검색 전략입니다. 이 알고리즘은 트리나 그래프에서 너비 방향으로 검색하므로 너비 우선 검색이라고 합니다.
BFS 알고리즘은 트리의 루트 노드부터 검색을 시작하고 현재 레벨의 모든 후속 노드를 확장한 후 다음 레벨의 노드로 이동합니다.
너비 우선 탐색 알고리즘은 일반 그래프 탐색 알고리즘의 한 예입니다.
FIFO 대기열 데이터 구조를 사용하여 구현된 너비 우선 검색입니다.

장점:

솔루션이 존재한다면 BFS는 솔루션을 제공할 것입니다.
특정 문제에 대한 솔루션이 두 개 이상인 경우 BFS는 최소한의 단계가 필요한 최소 솔루션을 제공합니다.

단점:

다음 레벨을 확장하려면 트리의 각 레벨을 메모리에 저장해야 하므로 많은 메모리가 필요합니다.
솔루션이 루트 노드에서 멀리 떨어져 있는 경우 BFS에는 많은 시간이 필요합니다.

예:

아래 트리 구조에서는 루트 노드 S에서 목표 노드 K까지 BFS 알고리즘을 사용하여 트리를 순회하는 것을 보여줍니다. BFS 검색 알고리즘은 레이어별로 순회하므로 점선 화살표로 표시된 경로를 따릅니다. 통과 경로는 다음과 같습니다:

 S---&gt; A---&gt;B----&gt;C---&gt;D----&gt;G---&gt;H---&gt;E----&gt;F----&gt;I----&gt;K

시간 복잡도: BFS 알고리즘의 시간 복잡도는 가장 얕은 노드까지 BFS에서 통과하는 노드 수로 얻을 수 있습니다. 여기서 d는 가장 얕은 솔루션의 깊이이고 b는 모든 상태의 노드입니다.

T(b) = 1+b²+b^삼+......+b^디=O(비^디)

공간 복잡도: BFS 알고리즘의 공간 복잡도는 프론티어 메모리 크기 O(b)로 표현됩니다.^디).

완전성: BFS는 완전합니다. 즉, 가장 얕은 목표 노드가 유한한 깊이에 있으면 BFS가 솔루션을 찾습니다.

최적성: BFS는 경로 비용이 노드 깊이의 비감소 함수인 경우 최적입니다.

2. 깊이 우선 탐색

깊이 우선 검색은 트리 또는 그래프 데이터 구조를 순회하는 재귀 알고리즘입니다.
루트 노드에서 시작하여 각 경로를 따라 가장 큰 깊이 노드까지 이동한 후 다음 경로로 이동하기 때문에 깊이 우선 탐색이라고 합니다.
DFS는 구현을 위해 스택 데이터 구조를 사용합니다.
DFS 알고리즘의 프로세스는 BFS 알고리즘과 유사합니다.

참고: 역추적은 재귀를 사용하여 가능한 모든 솔루션을 찾는 알고리즘 기술입니다.

이점:

DFS는 루트 노드에서 현재 노드까지의 경로에 있는 노드 스택만 저장하면 되므로 매우 적은 메모리가 필요합니다.
BFS 알고리즘보다 목표 노드에 도달하는 데 시간이 덜 걸립니다(올바른 경로로 통과하는 경우).

불리:

계속해서 많은 상태가 재발할 가능성이 있으며 해결책을 찾을 수 있다는 보장은 없습니다.
DFS 알고리즘은 심층 검색을 수행하며 때로는 무한 루프에 빠질 수 있습니다.

예:

아래 검색 트리에서는 깊이 우선 검색의 흐름을 보여 주며 다음과 같은 순서를 따릅니다.

루트 노드--->왼쪽 노드 ----> 오른쪽 노드.

루트 노드 S에서 검색을 시작하고 A, B, D, E를 순회합니다. E를 순회한 후 E에는 다른 후속 노드가 없고 여전히 목표 노드를 찾을 수 없으므로 트리를 역추적합니다. 역추적 후 노드 C와 G를 순회하며 여기서 목표 노드를 찾으면 종료됩니다.

완전성: DFS 검색 알고리즘은 제한된 검색 트리 내의 모든 노드를 확장하므로 유한 상태 공간 내에서 완성됩니다.

시간 복잡도: DFS의 시간 복잡도는 알고리즘이 통과하는 노드와 동일합니다. 그것은 다음과 같이 주어진다:

티(n)= 1+ n²+ 엔^삼+........+ 엔^중=O(n^중)

여기서 m= 노드의 최대 깊이이며 이는 d(가장 얕은 솔루션 깊이)보다 훨씬 클 수 있습니다.

공간 복잡도: DFS 알고리즘은 루트 노드로부터의 단일 경로만 저장해야 하므로 DFS의 공간 복잡도는 프린지 세트의 크기와 동일합니다. 에 대한 .

최적: DFS 검색 알고리즘은 목표 노드에 도달하는 데 많은 단계가 발생하거나 높은 비용이 발생할 수 있으므로 최적이 아닙니다.

3. 깊이 제한 검색 알고리즘:

깊이 제한 검색 알고리즘은 미리 결정된 제한이 있는 깊이 우선 검색과 유사합니다. 깊이 제한 탐색은 깊이 우선 탐색의 무한 경로의 단점을 해결할 수 있습니다. 이 알고리즘에서 깊이 제한에 있는 노드는 더 이상 후속 노드가 없는 것으로 간주됩니다.

깊이 제한 검색은 두 가지 실패 조건으로 종료될 수 있습니다.

표준 실패 값: 문제에 대한 해결책이 없음을 나타냅니다.
컷오프 실패 값: 주어진 깊이 제한 내에서 문제에 대한 해결책을 정의하지 않습니다.

장점:

깊이 제한 검색은 메모리 효율적입니다.

단점:

깊이 제한 검색은 불완전하다는 단점도 있습니다.
문제에 둘 이상의 솔루션이 있는 경우 최적이 아닐 수 있습니다.

예:

완전성: 솔루션이 깊이 제한을 초과하면 DLS 검색 알고리즘이 완료됩니다.

시간 복잡도: DLS 알고리즘의 시간복잡도는 오(b^ℓ) .

공간 복잡도: DLS 알고리즘의 공간 복잡도는 O입니다. (b�ℓ) .

최적: 깊이 제한 탐색은 DFS의 특수한 경우로 볼 수 있으며, ℓ>d인 경우에도 최적이 아닙니다.

4. 균일 비용 검색 알고리즘:

균일 비용 검색은 가중치가 적용된 트리나 그래프를 탐색하는 데 사용되는 검색 알고리즘입니다. 이 알고리즘은 각 가장자리에 대해 서로 다른 비용을 사용할 수 있을 때 작동합니다. 균일 비용 탐색의 주요 목표는 누적 비용이 가장 낮은 목표 노드까지의 경로를 찾는 것입니다. 균일 비용 검색은 루트 노드를 구성하는 경로 비용에 따라 노드를 확장합니다. 최적의 비용이 요구되는 모든 그래프/트리를 해결하는 데 사용할 수 있습니다. 균일 비용 검색 알고리즘은 우선순위 큐에 의해 구현됩니다. 가장 낮은 누적 비용에 최대 우선 순위를 부여합니다. 균일 비용 탐색은 모든 간선의 경로 비용이 동일한 경우 BFS 알고리즘과 동일합니다.

장점:

균일한 비용 탐색은 모든 상태에서 비용이 가장 적은 경로가 선택되기 때문에 최적입니다.

단점:

검색에 관련된 단계 수는 고려하지 않고 경로 비용만 고려합니다. 이로 인해 이 알고리즘은 무한 루프에 빠질 수 있습니다.

예:

완전성:

솔루션이 있으면 UCS가 찾아주는 등 균등 비용 검색이 완료됩니다.

시간 복잡도:

C*를 보자 최적의 솔루션의 비용 , 그리고 이자형 목표 노드에 가까워지기 위한 각 단계입니다. 그러면 단계 수는 = C*/ε+1입니다. 여기서는 상태 0에서 시작하여 C*/ε로 끝나므로 +1을 취합니다.

따라서 균일비용 탐색의 최악의 경우 시간 복잡도는 다음과 같습니다. 오(b^{1 + [C*/e]})/ .

공간 복잡도:

동일한 논리가 공간 복잡도에 대한 것이므로 균일 비용 검색의 최악의 공간 복잡도는 다음과 같습니다. 오(b^{1 + [C*/e]}) .

최적:

균일 비용 검색은 경로 비용이 가장 낮은 경로만 선택하므로 항상 최적입니다.

5. 반복 심화 깊이 우선 검색:

반복 심화 알고리즘은 DFS와 BFS 알고리즘의 조합입니다. 이 검색 알고리즘은 최적의 깊이 제한을 찾아내고 목표를 찾을 때까지 제한을 점진적으로 늘려 이를 수행합니다.

이 알고리즘은 특정 '깊이 제한'까지 깊이 우선 탐색을 수행하며, 목표 노드를 찾을 때까지 각 반복 후에 깊이 제한을 계속 증가시킵니다.

이 검색 알고리즘은 너비 우선 검색의 빠른 검색과 깊이 우선 검색의 메모리 효율성의 이점을 결합합니다.

반복 탐색 알고리즘은 탐색 공간이 크고 목표 노드의 깊이를 알 수 없는 경우에 유용한 비정보 탐색입니다.

장점:

빠른 검색과 메모리 효율성 측면에서 BFS와 DFS 검색 알고리즘의 장점을 결합합니다.

단점:

IDDFS의 주요 단점은 이전 단계의 모든 작업을 반복한다는 것입니다.

예:

다음 트리 구조는 반복 심화 깊이 우선 검색을 보여줍니다. IDDFS 알고리즘은 목표 노드를 찾지 못할 때까지 다양한 반복을 수행합니다. 알고리즘에 의해 수행되는 반복은 다음과 같이 제공됩니다.

1차 반복------> A
2차 반복----> A, B, C
3차 반복------>A, B, D, E, C, F, G
4번째 반복------>A, B, D, H, I, E, C, F, K, G
네 번째 반복에서는 알고리즘이 목표 노드를 찾습니다.

완전성:

이 알고리즘은 분기 인자가 유한할 때 완성됩니다.

시간 복잡도:

b가 분기 인자이고 깊이가 d라고 가정하면 최악의 시간 복잡도는 다음과 같습니다. 오(b^디) .

공간 복잡도:

IDDFS의 공간 복잡도는 다음과 같습니다. 오(bd) .

최적:

IDDFS 알고리즘은 경로 비용이 노드 깊이의 비감소 함수인 경우 최적입니다.

6. 양방향 검색 알고리즘:

양방향 검색 알고리즘은 두 가지 동시 검색을 실행합니다. 하나는 초기 상태에서 순방향 검색이라고 하고 다른 하나는 목표 노드에서 역방향 검색이라고 하며 목표 노드를 찾습니다. 양방향 검색은 하나의 단일 검색 그래프를 두 개의 작은 하위 그래프로 대체합니다. 하나는 초기 정점에서 검색을 시작하고 다른 하나는 목표 정점에서 시작합니다. 이 두 그래프가 서로 교차하면 검색이 중지됩니다.

양방향 검색은 BFS, DFS, DLS 등과 같은 검색 기술을 사용할 수 있습니다.

장점:

양방향 검색이 빠릅니다.
양방향 검색에는 더 적은 메모리가 필요합니다.

단점:

양방향 검색 트리 구현이 어렵습니다.

예:

아래 검색 트리에는 양방향 검색 알고리즘이 적용되어 있습니다. 이 알고리즘은 하나의 그래프/트리를 두 개의 하위 그래프로 나눕니다. 순방향으로 노드 1에서 횡단을 시작하고 역방향으로 목표 노드 16에서 시작합니다.

자바 기본 매개변수

알고리즘은 두 검색이 만나는 노드 9에서 종료됩니다.

완전성: 두 검색 모두에서 BFS를 사용하면 양방향 검색이 완료됩니다.

시간 복잡도: BFS를 이용한 양방향 검색의 시간복잡도는 오(b^디) .

공간 복잡도: 양방향 검색의 공간 복잡도는 오(b^디) .

최적: 양방향 검색이 최적입니다.