O componentă integrantă a informaticii și a inteligenței artificiale sunt algoritmii de căutare. Sunt folosite pentru a rezolva o varietate de probleme, de la jocuri precum șah și dame până la localizarea celui mai scurt traseu pe o hartă. Metoda Depth First Search (DFS), unul dintre cei mai populari algoritmi de căutare, caută o rețea sau un arbore călătorind cât mai departe posibil de-a lungul fiecărei ramuri înainte de a se întoarce. Cu toate acestea, DFS are un dezavantaj critic: dacă graficul conține cicluri, ar putea fi prins într-o buclă fără sfârșit. Utilizarea Căutării Iterative Deepening (IDS) sau Iterative Deepening Depth First Search este o tehnică pentru a rezolva această problemă (IDDFS).

Ce este IDS?

Un algoritm de căutare cunoscut sub numele de IDS combină beneficiile DFS cu Breadth First Search (BFS). Graficul este explorat folosind DFS, dar limita de adâncime a crescut constant până când ținta este localizată. Cu alte cuvinte, IDS rulează continuu DFS, ridicând limita de adâncime de fiecare dată, până când se obține rezultatul dorit. Aprofundarea iterativă este o metodă care se asigură că căutarea este amănunțită (adică descoperă o soluție dacă există) și eficientă (adică găsește cea mai scurtă cale către obiectiv).

Pseudocodul pentru IDS este simplu:

Cod

 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 

Cum funcționează IDS?

Funcția iterativeDeepeningSearch efectuează căutarea iterativă de aprofundare pe grafic folosind un nod rădăcină și un nod obiectiv ca intrări până când obiectivul este atins sau spațiul de căutare este epuizat. Acest lucru se realizează prin utilizarea regulată a funcției depthLimitedSearch, care aplică o restricție de adâncime pentru DFS. Căutarea se termină și returnează nodul scopului dacă obiectivul este situat la orice adâncime. Căutarea produce Niciunul dacă spațiul de căutare este epuizat (au fost investigate toate nodurile până la limita de adâncime).

Funcția depthLimitedSearch conduce DFS pe grafic cu limita de adâncime specificată, luând ca intrări un nod, un nod destinație și o limită de adâncime. Căutarea returnează FOUND dacă nodul dorit este situat la adâncimea curentă. Căutarea returnează NOT FOUND dacă limita de adâncime este atinsă, dar nodul obiectiv nu poate fi localizat. Dacă niciunul dintre criterii nu este adevărat, căutarea trece în mod iterativ la descendenții nodului.

Program:

Cod

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

Ieșire

 Path found 

Avantaje

• IDS este superior altor algoritmi de căutare în mai multe moduri. Primul beneficiu este că este cuprinzător, ceea ce asigură că va fi găsită o soluție dacă există una în spațiul de căutare. Acest lucru este astfel încât toate nodurile aflate sub o anumită limită de adâncime sunt investigate înainte ca limita de adâncime să fie ridicată de IDS, care face un DFS limitat la adâncime.
• IDS este eficient din punct de vedere al memoriei, care este al doilea beneficiu al său. Acest lucru se datorează faptului că IDS scade nevoile de memorie ale algoritmului prin faptul că nu stochează fiecare nod din zona de căutare în memorie. IDS minimizează amprenta de memorie a algoritmului prin stocarea nodurilor doar până la limita actuală de adâncime.
• Capacitatea IDS de a fi utilizat atât pentru căutarea în arbore, cât și pentru căutarea grafică este al treilea beneficiu al acestuia. Acest lucru se datorează faptului că IDS este un algoritm de căutare generic care funcționează pe orice spațiu de căutare, inclusiv un arbore sau un grafic.

Dezavantaje

• IDS are dezavantajul că poate vizita anumite noduri de mai multe ori, ceea ce ar putea încetini căutarea. Beneficiile completității și optimității depășesc frecvent acest dezavantaj. În plus, prin folosirea unor strategii precum memoria sau stocarea în cache, călătoriile repetate pot fi minimizate.