반복 심화 검색(IDS) 또는 반복 심화 깊이 우선 검색(IDDFS)

컴퓨터 과학과 인공 지능의 필수 구성 요소는 검색 알고리즘입니다. 체스나 체커 같은 게임부터 지도에서 최단 경로를 찾는 것까지 다양한 문제를 해결하는 데 사용됩니다. 가장 널리 사용되는 검색 알고리즘 중 하나인 깊이 우선 검색(DFS) 방법은 방향을 바꾸기 전에 각 가지를 따라 최대한 멀리 이동하여 네트워크나 트리를 검색합니다. 그러나 DFS에는 치명적인 단점이 있습니다. 그래프에 주기가 포함되어 있으면 무한 루프에 빠질 수 있습니다. Iterative Deepening Search(IDS) 또는 Iterative Deepening Depth First Search를 활용하는 것은 이 문제(IDDFS)를 해결하는 한 가지 기술입니다.

IDS란 무엇입니까?

IDS라고 알려진 검색 알고리즘은 DFS의 이점과 BFS(Breadth First Search)를 결합합니다. 그래프는 DFS를 사용하여 탐색되지만 대상을 찾을 때까지 깊이 제한이 꾸준히 증가합니다. 즉, IDS는 원하는 결과를 얻을 때까지 계속해서 DFS를 실행하여 매번 깊이 제한을 높입니다. 반복 심화는 검색이 철저하고(즉, 솔루션이 있는 경우 이를 발견) 효율적(즉, 목표까지의 최단 경로 찾기)을 보장하는 방법입니다.

IDS의 의사코드는 간단합니다.

암호

 function iterativeDeepeningSearch(root, goal): depth = 0 while True: result = depthLimitedSearch(root, goal, depth) if result == FOUND: return goal if result == NOT_FOUND: return None depth = depth + 1 function depthLimitedSearch(node, goal, depth): if node == goal: return FOUND if depth == 0: return NOT_FOUND for child in node.children: result = depthLimitedSearch(child, goal, depth - 1) if result == FOUND: return FOUND return NOT_FOUND

IDS는 어떻게 작동하나요?

iterativeDeepeningSearch 함수는 루트 노드와 목표 노드를 입력으로 사용하여 목표를 달성하거나 검색 공간을 모두 사용할 때까지 그래프에 대해 반복 심화 검색을 수행합니다. 이는 DFS에 깊이 제한을 적용하는 deepLimitedSearch 함수를 정기적으로 사용하여 수행됩니다. 검색이 종료되고 목표가 임의의 깊이에 있으면 목표 노드를 반환합니다. 검색 공간을 모두 사용한 경우 검색 결과 없음이 반환됩니다(깊이 제한까지의 모든 노드가 조사되었습니다).

DepthLimitedSearch 함수는 노드, 대상 노드 및 깊이 제한을 입력으로 사용하여 지정된 깊이 제한을 사용하여 그래프에 대해 DFS를 수행합니다. 원하는 노드가 현재 깊이에 있으면 검색은 FOUND를 반환합니다. 깊이 제한에 도달했지만 목표 노드를 찾을 수 없는 경우 검색은 NOT FOUND를 반환합니다. 두 기준 모두 참이 아닌 경우 검색은 반복적으로 노드의 자손으로 이동합니다.

프로그램:

암호

 from collections import defaultdict class Graph: def __init__(self): self.graph = defaultdict(list) def add_edge(self, u, v): self.graph[u].append(v) def iddfs(self, start, goal, max_depth): for depth in range(max_depth+1): visited = set() if self.dls(start, goal, depth, visited): return True return False def dls(self, node, goal, depth, visited): if node == goal: return True if depth == 0: return False visited.add(node) for neighbor in self.graph[node]: if neighbor not in visited: if self.dls(neighbor, goal, depth-1, visited): return True return False # Example usage g = Graph() g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 2) g.add_edge(2, 0) g.add_edge(2, 3) g.add_edge(3, 3) start = 0 goal = 3 max_depth = 3 if g.iddfs(start, goal, max_depth): print(&apos;Path found&apos;) else: print(&apos;Path not found&apos;)

산출

 Path found

장점

IDS는 여러 면에서 다른 검색 알고리즘보다 우수합니다. 첫 번째 이점은 포괄적이므로 검색 공간에 솔루션이 있는 경우 이를 찾을 수 있다는 것입니다. 이는 깊이 제한 DFS를 수행하는 IDS가 깊이 제한을 올리기 전에 특정 깊이 제한 아래의 모든 노드를 조사하기 위한 것입니다.
IDS는 메모리 효율적이라는 점이 두 번째 장점입니다. 이는 IDS가 검색 영역의 모든 노드를 메모리에 저장하지 않음으로써 알고리즘의 메모리 요구량을 줄이기 때문입니다. IDS는 현재 깊이 제한까지만 노드를 저장하여 알고리즘의 메모리 공간을 최소화합니다.
트리 검색과 그래프 검색 모두에 활용될 수 있는 IDS의 능력은 세 번째 이점입니다. 이는 IDS가 트리나 그래프를 포함한 모든 검색 공간에서 작동하는 일반 검색 알고리즘이기 때문입니다.

단점

IDS에는 특정 노드를 두 번 이상 방문할 가능성이 있어 검색 속도가 느려질 수 있다는 단점이 있습니다. 완전성과 최적성의 이점이 이러한 단점을 능가하는 경우가 많습니다. 또한 메모리나 캐싱과 같은 전략을 사용하면 반복적인 이동을 최소화할 수 있습니다.