En integreret komponent af datalogi og kunstig intelligens er søgealgoritmer. De bruges til at løse en række problemer, fra at spille spil som skak og dam til at finde den korteste rute på et kort. DFS-metoden (Depth First Search), en af ​​de mest populære søgealgoritmer, søger i et netværk eller træ ved at rejse så langt som muligt langs hver gren, før man vender om. DFS har dog en kritisk ulempe: Hvis grafen indeholder cyklusser, kan den blive fanget i en endeløs løkke. Brug af Iterative Deepening Search (IDS) eller Iterative Deepening Deepth First Search er en teknik til at løse dette problem (IDDFS).

Hvad er IDS?

En søgealgoritme kendt som IDS kombinerer fordelene ved DFS med Breadth First Search (BFS). Grafen udforskes ved hjælp af DFS, men dybdegrænsen øges støt, indtil målet er lokaliseret. Med andre ord kører IDS konstant DFS, og hæver dybdegrænsen hver gang, indtil det ønskede resultat opnås. Iterativ uddybning er en metode, der sikrer, at søgningen er grundig (dvs. den finder en løsning, hvis en findes) og effektiv (dvs. den finder den korteste vej til målet).

Pseudokoden for IDS er ligetil:

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 virker IDS?

Funktionen iterativeDeepeningSearch udfører iterativ uddybningssøgning på grafen ved hjælp af en rodknude og en målknude som input, indtil målet er nået, eller søgepladsen er brugt op. Dette opnås ved regelmæssigt at bruge funktionen depthLimitedSearch, som anvender en dybdebegrænsning på DFS. Søgningen afsluttes og returnerer målknudepunktet, hvis målet er placeret i nogen dybde. Søgningen giver Ingen, hvis søgepladsen er brugt op (alle knudepunkter op til dybdegrænsen er undersøgt).

DepthLimitedSearch-funktionen udfører DFS på grafen med den specificerede dybdegrænse ved at tage en node, en destinationsknude og en dybdegrænse som input. Søgningen returnerer FOUND, hvis den ønskede node er placeret i den aktuelle dybde. Søgningen returnerer IKKE FUNDET, hvis dybdegrænsen er nået, men målknuden ikke kan lokaliseres. Hvis ingen af ​​kriterierne er sande, går søgningen iterativt videre til nodens afkom.

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

Produktion

 Path found 

Fordele

• IDS er overlegen i forhold til andre søgealgoritmer på en række måder. Den første fordel er, at den er omfattende, hvilket sikrer, at der bliver fundet en løsning, hvis man er der i søgerummet. Dette er for at alle noder under en specifik dybdegrænse bliver undersøgt inden dybdegrænsen hæves af IDS, som laver en dybdebegrænset DFS.
• IDS er hukommelseseffektiv, hvilket er dens anden fordel. Dette skyldes, at IDS reducerer algoritmens hukommelsesbehov ved ikke at gemme hver node i søgeområdet i hukommelsen. IDS minimerer algoritmens hukommelsesfodaftryk ved kun at gemme noderne op til den aktuelle dybdegrænse.
• IDS's evne til at blive brugt til både træ- og grafsøgning er dens tredje fordel. Dette skyldes det faktum, at IDS er en generisk søgealgoritme, der fungerer på ethvert søgeområde, inklusive et træ eller en graf.

Ulemper

• IDS har den ulempe, at den potentielt besøger visse noder mere end én gang, hvilket kan bremse søgningen. Fordelene ved fuldstændighed og optimalitet overstiger ofte denne ulempe. Derudover kan de gentagne ture minimeres ved at anvende strategier som hukommelse eller caching.