En integrerad del av datavetenskap och artificiell intelligens är sökalgoritmer. De används för att lösa en mängd olika problem, från att spela spel som schack och dam till att hitta den kortaste vägen på en karta. Metoden Depth First Search (DFS), en av de mest populära sökalgoritmerna, söker i ett nätverk eller träd genom att resa så långt som möjligt längs varje gren innan du vänder dig om. DFS har dock en kritisk nackdel: om grafen innehåller cykler kan den fastna i en oändlig loop. Att använda Iterative Deepening Search (IDS) eller Iterative Deepening Depth First Search är en teknik för att lösa detta problem (IDDFS).

Vad är IDS?

En sökalgoritm känd som IDS kombinerar fördelarna med DFS med Breadth First Search (BFS). Grafen utforskas med DFS, men djupgränsen ökade stadigt tills målet är lokaliserat. Med andra ord, IDS kör kontinuerligt DFS, och höjer djupgränsen varje gång, tills önskat resultat erhålls. Iterativ fördjupning är en metod som ser till att sökningen är grundlig (dvs den upptäcker en lösning om en finns) och effektiv (dvs den hittar den kortaste vägen till målet).

Pseudokoden för IDS är enkel:

Koda

 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 

Hur fungerar IDS?

Funktionen iterativeDeepeningSearch utför iterativ fördjupningssökning på grafen med en rotnod och en målnod som indata tills målet uppnås eller sökutrymmet är förbrukat. Detta uppnås genom att regelbundet använda funktionen depthLimitedSearch, som tillämpar en djupbegränsning på DFS. Sökningen avslutas och returnerar målnoden om målet finns på något djup. Sökningen ger Inget om sökutrymmet är förbrukat (alla noder upp till djupgränsen har undersökts).

Funktionen depthLimitedSearch utför DFS på grafen med den angivna djupgränsen genom att ta en nod, en destinationsnod och en djupgräns som indata. Sökningen returnerar FOUND om den önskade noden är belägen på det aktuella djupet. Sökningen returnerar NOT FOUND om djupgränsen nås men målnoden inte kan lokaliseras. Om ingetdera kriteriet är sant, går sökningen iterativt vidare till nodens avkomma.

Program:

Koda

 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 

Fördelar

• IDS är överlägset andra sökalgoritmer på ett antal sätt. Den första fördelen är att den är heltäckande, vilket säkerställer att en lösning kommer att hittas om en finns där i sökutrymmet. Detta för att alla noder under en specifik djupgräns undersöks innan djupgränsen höjs av IDS, som gör en djupbegränsad DFS.
• IDS är minneseffektivt, vilket är dess andra fördel. Detta beror på att IDS minskar algoritmens minnesbehov genom att inte lagra varje nod i sökområdet i minnet. IDS minimerar algoritmens minnesavtryck genom att endast lagra noderna upp till den aktuella djupgränsen.
• IDS förmåga att användas för både träd- och grafsökning är dess tredje fördel. Detta beror på det faktum att IDS är en generisk sökalgoritm som fungerar på alla sökutrymmen, inklusive ett träd eller en graf.

Nackdelar

• IDS har nackdelen att potentiellt besöka vissa noder mer än en gång, vilket kan sakta ner sökningen. Fördelarna med fullständighet och optimalitet överstiger ofta denna nackdel. Dessutom, genom att använda strategier som minne eller cachning, kan de upprepade turerna minimeras.