logo

TechCodeview

Iterative Deepening Search (IDS) eller Iterative Deepening Depth First Search (IDDFS)

En integrert komponent av informatikk og kunstig intelligens er søkealgoritmer. De brukes til å løse en rekke problemer, fra å spille spill som sjakk og dam til å finne den korteste ruten på et kart. Metoden Depth First Search (DFS), en av de mest populære søkealgoritmene, søker i et nettverk eller tre ved å reise så langt som mulig langs hver gren før du snur. DFS har imidlertid en kritisk ulempe: hvis grafen inneholder sykluser, kan den bli fanget i en endeløs løkke. Å bruke Iterative Deepening Search (IDS) eller Iterative Deepening Depth First Search er en teknikk for å løse dette problemet (IDDFS).

Hva er IDS?

En søkealgoritme kjent som IDS kombinerer fordelene med DFS med Breadth First Search (BFS). Grafen utforskes ved hjelp av DFS, men dybdegrensen økte jevnt og trutt til målet er lokalisert. Med andre ord kjører IDS kontinuerlig DFS, og øker dybdegrensen hver gang, til ønsket resultat er oppnådd. Iterativ utdyping er en metode som sørger for at søket er grundig (det vil si at det oppdager en løsning hvis det finnes) og effektivt (det vil si at det finner den korteste veien til målet).

Pseudokoden for IDS er enkel:

Kode 

 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

Hvordan fungerer IDS?

IterativeDeepeningSearch-funksjonen utfører iterativt utdypingssøk på grafen ved å bruke en rotnode og en målnode som input til målet er oppnådd eller søkeplassen er brukt opp. Dette oppnås ved regelmessig å bruke funksjonen depthLimitedSearch, som bruker en dybdebegrensning på DFS. Søket avsluttes og returnerer målnoden hvis målet befinner seg på en hvilken som helst dybde. Søket gir Ingen dersom søkeplassen er brukt opp (alle noder opp til dybdegrensen er undersøkt).

DepthLimitedSearch-funksjonen utfører DFS på grafen med den spesifiserte dybdegrensen ved å ta inn en node, en destinasjonsnode og en dybdegrense. Søket returnerer FOUND hvis ønsket node befinner seg på gjeldende dybde. Søket returnerer NOT FOUND hvis dybdegrensen er nådd, men målnoden ikke kan lokaliseres. Hvis ingen av kriteriene er sanne, går søket iterativt videre til nodens avkom.

Program:

Kode 

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

Produksjon 

 Path found

Fordeler

  • IDS er overlegen andre søkealgoritmer på en rekke måter. Den første fordelen er at den er omfattende, noe som sikrer at en løsning vil bli funnet hvis man er der i søkefeltet. Dette er slik at alle noder under en spesifikk dybdegrense undersøkes før dybdegrensen heves av IDS, som gjør en dybdebegrenset DFS.
  • IDS er minneeffektiv, som er den andre fordelen. Dette er fordi IDS reduserer algoritmens minnebehov ved ikke å lagre hver node i søkeområdet i minnet. IDS minimerer algoritmens minnefotavtrykk ved kun å lagre nodene opp til gjeldende dybdegrense.
  • IDSs evne til å bli utnyttet til både tre- og grafsøk er den tredje fordelen. Dette skyldes det faktum at IDS er en generisk søkealgoritme som fungerer på alle søkerom, inkludert et tre eller en graf.

Ulemper

  • IDS har ulempen ved å potensielt besøke visse noder mer enn én gang, noe som kan redusere søket. Fordelene med fullstendighet og optimalitet overstiger ofte denne ulempen. I tillegg, ved å bruke strategier som minne eller caching, kan de gjentatte turene minimeres.