logo

TechCodeview

Iterativno dubinsko pretraživanje (IDS) ili iterativno dubinsko dubinsko prvo pretraživanje (IDDFS)

Sastavni dio informatike i umjetne inteligencije su algoritmi pretraživanja. Koriste se za rješavanje raznih problema, od igranja igara poput šaha i dame do lociranja najkraće rute na karti. Metoda pretraživanja prvo u dubinu (DFS), jedan od najpopularnijih algoritama pretraživanja, pretražuje mrežu ili stablo putujući što je moguće dalje duž svake grane prije nego što se okrene. Međutim, DFS ima kritičan nedostatak: ako graf sadrži cikluse, mogao bi postati zarobljen u beskonačnoj petlji. Korištenje iterativnog dubinskog pretraživanja (IDS) ili iterativnog dubinskog dubinskog pretraživanja jedna je od tehnika za rješavanje ovog problema (IDDFS).

Što je IDS?

Algoritam pretraživanja poznat kao IDS kombinira prednosti DFS-a s pretraživanjem prvo u širinu (BFS). Grafikon se istražuje pomoću DFS-a, ali ograničenje dubine stalno se povećavalo dok se cilj ne pronađe. Drugim riječima, IDS kontinuirano pokreće DFS, svaki put podižući granicu dubine, sve dok se ne postigne željeni rezultat. Iterativno produbljivanje je metoda koja osigurava da pretraga bude temeljita (tj. otkriva rješenje ako ono postoji) i učinkovita (tj. pronalazi najkraći put do cilja).

Pseudokod za IDS je jednostavan:

Kodirati 

 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

Kako IDS radi?

Funkcija iterativeDeepeningSearch izvodi iterativno dublje pretraživanje na grafu koristeći korijenski čvor i ciljni čvor kao ulaze sve dok se cilj ne postigne ili dok se ne potroši prostor za pretraživanje. To se postiže redovitom upotrebom funkcije depthLimitedSearch, koja primjenjuje ograničenje dubine na DFS. Pretraživanje završava i vraća ciljni čvor ako se cilj nalazi na bilo kojoj dubini. Pretraživanje daje ništa ako je prostor za pretraživanje potrošen (svi čvorovi do granice dubine su istraženi).

Funkcija depthLimitedSearch provodi DFS na grafu s navedenim ograničenjem dubine uzimajući kao ulaze čvor, odredišni čvor i ograničenje dubine. Pretraživanje vraća FOUND ako se željeni čvor nalazi na trenutnoj dubini. Pretraživanje vraća NIJE NAĐENO ako je ograničenje dubine dosegnuto, ali ciljni čvor nije moguće locirati. Ako niti jedan kriterij nije istinit, pretraga se iterativno premješta na potomke čvora.

Program:

Kodirati 

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

Izlaz 

 Path found

Prednosti

  • IDS je superioran u odnosu na druge algoritme pretraživanja na više načina. Prva prednost je to što je sveobuhvatan, što osigurava da će se pronaći rješenje ako se nalazi u prostoru za pretraživanje. To je tako da se svi čvorovi ispod određenog ograničenja dubine istražuju prije nego što IDS podigne ograničenje dubine, što radi DFS ograničen dubinom.
  • IDS je memorijski učinkovit, što je njegova druga prednost. To je zato što IDS smanjuje potrebe algoritma za memorijom ne pohranjujući svaki čvor u području pretraživanja u memoriju. IDS smanjuje memorijski otisak algoritma pohranjujući samo čvorove do trenutnog ograničenja dubine.
  • IDS-ova sposobnost da se koristi i za stablo i za pretraživanje grafikona njegova je treća prednost. To je zbog činjenice da je IDS generički algoritam pretraživanja koji radi na bilo kojem prostoru pretraživanja, uključujući stablo ili grafikon.

Nedostaci

  • IDS ima nedostatak potencijalnog posjećivanja određenih čvorova više puta, što bi moglo usporiti pretraživanje. Prednosti potpunosti i optimalnosti često premašuju ovaj nedostatak. Nadalje, korištenjem strategija poput memorije ili predmemoriranja, ponovljena putovanja mogu se svesti na minimum.