logo

TechCodeview

Recherche itérative d'approfondissement (IDS) ou recherche itérative d'approfondissement en profondeur d'abord (IDDFS)

Les algorithmes de recherche font partie intégrante de l’informatique et de l’intelligence artificielle. Ils sont utilisés pour résoudre une variété de problèmes, depuis les jeux d’échecs et de dames jusqu’à la localisation de l’itinéraire le plus court sur une carte. La méthode Depth First Search (DFS), l'un des algorithmes de recherche les plus populaires, recherche un réseau ou un arbre en parcourant le plus loin possible chaque branche avant de faire demi-tour. Cependant, DFS présente un inconvénient majeur : si le graphique contient des cycles, il pourrait se retrouver piégé dans une boucle sans fin. L’utilisation de la recherche itérative d’approfondissement (IDS) ou de la première recherche itérative d’approfondissement en profondeur est une technique pour résoudre ce problème (IDDFS).

Qu’est-ce que l’IDS ?

Un algorithme de recherche appelé IDS combine les avantages de DFS avec Breadth First Search (BFS). Le graphique est exploré à l'aide de DFS, mais la limite de profondeur augmente régulièrement jusqu'à ce que la cible soit localisée. En d’autres termes, IDS exécute continuellement DFS, en augmentant à chaque fois la limite de profondeur, jusqu’à ce que le résultat souhaité soit obtenu. L'approfondissement itératif est une méthode qui garantit que la recherche est approfondie (c'est-à-dire qu'elle découvre une solution si elle existe) et efficace (c'est-à-dire qu'elle trouve le chemin le plus court vers l'objectif).

Le pseudocode pour IDS est simple :

Code 

 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

Comment fonctionne l’IDS ?

La fonction iterativeDeepeningSearch effectue une recherche itérative d'approfondissement sur le graphique en utilisant un nœud racine et un nœud objectif comme entrées jusqu'à ce que l'objectif soit atteint ou que l'espace de recherche soit épuisé. Ceci est accompli en utilisant régulièrement la fonction deepLimitedSearch, qui applique une restriction de profondeur à DFS. La recherche se termine et renvoie le nœud d'objectif si l'objectif est situé à n'importe quelle profondeur. La recherche donne Aucun si l'espace de recherche est épuisé (tous les nœuds jusqu'à la limite de profondeur ont été étudiés).

La fonction deepLimitedSearch effectue DFS sur le graphique avec la limite de profondeur spécifiée en prenant comme entrées un nœud, un nœud de destination et une limite de profondeur. La recherche renvoie FOUND si le nœud souhaité est situé à la profondeur actuelle. La recherche renvoie NOT FOUND si la limite de profondeur est atteinte mais que le nœud objectif ne peut pas être localisé. Si aucun des deux critères n'est vrai, la recherche passe de manière itérative à la progéniture du nœud.

Programme:

Code 

 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')

Sortir 

 Path found

Avantages

  • IDS est supérieur aux autres algorithmes de recherche à bien des égards. Le premier avantage est qu’il est complet, ce qui garantit qu’une solution sera trouvée si elle est présente dans l’espace de recherche. Cela permet que tous les nœuds situés sous une limite de profondeur spécifique soient étudiés avant que la limite de profondeur ne soit augmentée par IDS, qui effectue un DFS limité en profondeur.
  • IDS est économe en mémoire, ce qui constitue son deuxième avantage. En effet, IDS diminue les besoins en mémoire de l'algorithme en ne stockant pas en mémoire tous les nœuds de la zone de recherche. IDS minimise l'empreinte mémoire de l'algorithme en stockant uniquement les nœuds jusqu'à la limite de profondeur actuelle.
  • La capacité d'IDS à être utilisé à la fois pour la recherche arborescente et graphique constitue son troisième avantage. Cela est dû au fait qu’IDS est un algorithme de recherche générique qui fonctionne sur n’importe quel espace de recherche, y compris un arbre ou un graphique.

Désavantages

  • IDS présente l'inconvénient de pouvoir visiter certains nœuds plus d'une fois, ce qui peut ralentir la recherche. Les avantages de l’exhaustivité et de l’optimalité dépassent souvent cet inconvénient. De plus, en employant des stratégies telles que la mémoire ou la mise en cache, les déplacements répétés peuvent être minimisés.