logo

TechCodeview

Iterativní prohlubování vyhledávání (IDS) nebo Iterativní prohlubování hloubkové první vyhledávání (IDDFS)

Nedílnou součástí informatiky a umělé inteligence jsou vyhledávací algoritmy. Používají se k řešení různých problémů, od hraní her, jako jsou šachy a dáma, až po vyhledání nejkratší trasy na mapě. Metoda Depth First Search (DFS), jeden z nejpopulárnějších vyhledávacích algoritmů, prohledává síť nebo strom tak, že urazí co nejdále podél každé větve, než se otočí. DFS má však kritickou nevýhodu: pokud graf obsahuje cykly, mohl by uvíznout v nekonečné smyčce. Využití Iterativního prohlubování vyhledávání (IDS) nebo Iterativního prohlubování hloubkového prvního vyhledávání je jednou z technik řešení tohoto problému (IDDFS).

Co je IDS?

Vyhledávací algoritmus známý jako IDS kombinuje výhody DFS s BFS (Breadth First Search). Graf je prozkoumán pomocí DFS, ale hloubkový limit se neustále zvyšoval, dokud nebyl cíl lokalizován. Jinými slovy, IDS neustále spouští DFS a pokaždé zvyšuje limit hloubky, dokud není dosaženo požadovaného výsledku. Iterativní prohlubování je metoda, která zajišťuje, že hledání je důkladné (tj. najde řešení, pokud nějaké existuje) a efektivní (tj. najde nejkratší cestu k cíli).

Pseudokód pro IDS je přímočarý:

Kód 

 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

Jak IDS funguje?

Funkce iterativeDeepeningSearch provádí iterativní prohlubování prohledávání grafu pomocí kořenového uzlu a cílového uzlu jako vstupů, dokud není dosaženo cíle nebo není vyčerpán vyhledávací prostor. Toho je dosaženo pravidelným používáním funkce depthLimitedSearch, která aplikuje omezení hloubky na DFS. Hledání skončí a vrátí cílový uzel, pokud se cíl nachází v jakékoli hloubce. Pokud je prohledávací prostor vyčerpán, hledání dává Žádné (byly prozkoumány všechny uzly až do limitu hloubky).

Funkce depthLimitedSearch provádí DFS na grafu se zadaným limitem hloubky tím, že jako vstupy bere uzel, cílový uzel a limit hloubky. Hledání vrátí FOUND, pokud se požadovaný uzel nachází v aktuální hloubce. Hledání vrátí NOT FOUND, pokud je dosaženo limitu hloubky, ale cílový uzel nelze najít. Pokud ani jedno z kritérií není pravdivé, hledání se iterativně přesune k potomkům uzlu.

Program:

Kód 

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

Výstup 

 Path found

Výhody

  • IDS je v mnoha ohledech lepší než jiné vyhledávací algoritmy. První výhodou je, že je komplexní, což zajišťuje, že bude nalezeno řešení, pokud se nějaké nachází v prostoru hledání. Je to tak, že všechny uzly pod určitým hloubkovým limitem jsou vyšetřovány předtím, než je hloubkový limit zvýšen pomocí IDS, což provádí DFS s omezenou hloubkou.
  • IDS je paměťově efektivní, což je jeho druhá výhoda. Je to proto, že IDS snižuje paměťové potřeby algoritmu tím, že neukládá do paměti každý uzel ve vyhledávací oblasti. IDS minimalizuje paměťovou stopu algoritmu tím, že ukládá uzly pouze do aktuálního limitu hloubky.
  • Schopnost IDS být využita pro stromové i grafové vyhledávání je jeho třetí výhodou. To je způsobeno skutečností, že IDS je obecný vyhledávací algoritmus, který funguje na jakémkoli vyhledávacím prostoru, včetně stromu nebo grafu.

Nevýhody

  • IDS má nevýhodu potenciálně navštěvovat určité uzly více než jednou, což může zpomalit vyhledávání. Výhody úplnosti a optimality často převyšují tuto nevýhodu. Použitím strategií, jako je paměť nebo ukládání do mezipaměti, lze navíc minimalizovat opakované cesty.