Um componente integral da ciência da computação e da inteligência artificial são os algoritmos de busca. Eles são usados ​​para resolver uma variedade de problemas, desde jogos como xadrez e damas até localizar o caminho mais curto em um mapa. O método Depth First Search (DFS), um dos algoritmos de pesquisa mais populares, pesquisa uma rede ou árvore viajando o mais longe possível ao longo de cada ramo antes de virar. No entanto, o DFS tem uma desvantagem crítica: se o gráfico contiver ciclos, ele poderá ficar preso em um loop infinito. Utilizar Iterative Deepening Search (IDS) ou Iterative Deepening Depth First Search é uma técnica para resolver esse problema (IDDFS).

O que é IDS?

Um algoritmo de pesquisa conhecido como IDS combina os benefícios do DFS com a Breadth First Search (BFS). O gráfico é explorado usando DFS, mas o limite de profundidade aumenta continuamente até que o alvo seja localizado. Em outras palavras, o IDS executa continuamente o DFS, aumentando o limite de profundidade a cada vez, até que o resultado desejado seja obtido. O aprofundamento iterativo é um método que garante que a pesquisa seja completa (ou seja, descobre uma solução, se existir) e eficiente (ou seja, encontra o caminho mais curto para o objetivo).

O pseudocódigo para IDS é simples:

Código

 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 

Como funciona o IDS?

A função iterativeDeepeningSearch executa uma pesquisa iterativa de aprofundamento no gráfico usando um nó raiz e um nó objetivo como entradas até que o objetivo seja alcançado ou o espaço de pesquisa seja esgotado. Isso é feito usando regularmente a função deepLimitedSearch, que aplica uma restrição de profundidade ao DFS. A busca termina e retorna o nó objetivo se o objetivo estiver localizado em qualquer profundidade. A pesquisa produz Nenhum se o espaço de pesquisa estiver esgotado (todos os nós até o limite de profundidade foram investigados).

A função deepLimitedSearch conduz DFS no gráfico com o limite de profundidade especificado, tomando como entradas um nó, um nó de destino e um limite de profundidade. A pesquisa retorna FOUND se o nó desejado estiver localizado na profundidade atual. A pesquisa retorna NOT FOUND se o limite de profundidade for atingido, mas o nó objetivo não puder ser localizado. Se nenhum dos critérios for verdadeiro, a busca passa iterativamente para o descendente do nó.

Programa:

Código

 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('Path found') else: print('Path not found') 

Saída

 Path found 

Vantagens

• O IDS é superior a outros algoritmos de pesquisa de várias maneiras. O primeiro benefício é que ele é abrangente, o que garante que uma solução será encontrada se houver alguma no espaço de busca. Isto ocorre para que todos os nós abaixo de um limite de profundidade específico sejam investigados antes que o limite de profundidade seja aumentado pelo IDS, que faz um DFS com profundidade limitada.
• O IDS é eficiente em termos de memória, o que é seu segundo benefício. Isso ocorre porque o IDS diminui as necessidades de memória do algoritmo ao não armazenar na memória todos os nós da área de pesquisa. O IDS minimiza o consumo de memória do algoritmo armazenando apenas os nós até o limite de profundidade atual.
• A capacidade do IDS de ser utilizado para pesquisas em árvores e gráficos é seu terceiro benefício. Isso se deve ao fato de o IDS ser um algoritmo de busca genérico que funciona em qualquer espaço de busca, incluindo uma árvore ou um grafo.

Desvantagens

• O IDS tem a desvantagem de potencialmente visitar determinados nós mais de uma vez, o que pode retardar a busca. Os benefícios da completude e da optimização excedem frequentemente esta desvantagem. Além disso, ao empregar estratégias como memória ou cache, as viagens repetidas podem ser minimizadas.