logo

TechCodeview

Iteratívne prehlbujúce vyhľadávanie (IDS) alebo Iteratívne prehlbujúce sa hĺbkové prvé vyhľadávanie (IDDFS)

Neoddeliteľnou súčasťou informatiky a umelej inteligencie sú vyhľadávacie algoritmy. Používajú sa na riešenie rôznych problémov, od hrania hier ako šach a dáma až po nájdenie najkratšej trasy na mape. Metóda Depth First Search (DFS), jeden z najpopulárnejších vyhľadávacích algoritmov, prehľadáva sieť alebo strom tak, že prejde čo najďalej pozdĺž každej vetvy, kým sa otočí. DFS má však kritickú nevýhodu: ak graf obsahuje cykly, môže byť uväznený v nekonečnej slučke. Jednou z techník na vyriešenie tohto problému je použitie iteratívneho prehlbovania (IDS) alebo iteratívneho prehlbovania hĺbky prvého vyhľadávania (IDDFS).

čo je IDS?

Vyhľadávací algoritmus známy ako IDS kombinuje výhody DFS s Breadth First Search (BFS). Graf sa skúma pomocou DFS, ale hĺbkový limit sa neustále zvyšoval, kým sa cieľ nenájde. Inými slovami, IDS neustále spúšťa DFS, pričom zakaždým zvyšuje hĺbkový limit, kým sa nedosiahne požadovaný výsledok. Iteratívne prehlbovanie je metóda, ktorá zabezpečuje dôkladné vyhľadávanie (t. j. nájde riešenie, ak nejaké existuje) a efektívne (t. j. nájde najkratšiu cestu k cieľu).

Pseudokód pre IDS je jednoduchý:

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

Ako funguje IDS?

Funkcia iterativeDeepeningSearch vykonáva iteratívne prehlbujúce vyhľadávanie v grafe pomocou koreňového uzla a cieľového uzla ako vstupov, kým sa nedosiahne cieľ alebo sa nevyčerpá priestor na vyhľadávanie. To sa dosahuje pravidelným používaním funkcie depthLimitedSearch, ktorá aplikuje obmedzenie hĺbky na DFS. Vyhľadávanie sa ukončí a vráti cieľový uzol, ak sa cieľ nachádza v akejkoľvek hĺbke. Vyhľadávanie prinesie Žiadne, ak sa vyhľadávací priestor vyčerpá (všetky uzly až do limitu hĺbky boli preskúmané).

Funkcia depthLimitedSearch vykonáva DFS na grafe so špecifikovaným limitom hĺbky tým, že ako vstupy berie uzol, cieľový uzol a limit hĺbky. Vyhľadávanie vráti FOUND, ak sa požadovaný uzol nachádza v aktuálnej hĺbke. Vyhľadávanie vráti NOT FOUND, ak je dosiahnutý limit hĺbky, ale cieľový uzol nemožno nájsť. Ak ani jedno z kritérií nie je pravdivé, vyhľadávanie sa iteračne presunie k potomkom uzla.

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ýkon 

 Path found

Výhody

  • IDS je v mnohých smeroch lepší ako iné vyhľadávacie algoritmy. Prvou výhodou je, že je komplexný, čo zaisťuje, že riešenie sa nájde, ak sa nejaké nachádza v priestore vyhľadávania. Je to tak, že všetky uzly pod určitým hĺbkovým limitom sú vyšetrené predtým, ako sa hĺbkový limit zvýši pomocou IDS, čo robí DFS s obmedzením hĺbky.
  • IDS je pamäťovo efektívny, čo je jeho druhá výhoda. Je to preto, že IDS znižuje pamäťové potreby algoritmu tým, že neukladá do pamäte každý uzol v oblasti vyhľadávania. IDS minimalizuje pamäťovú stopu algoritmu tým, že ukladá uzly len do aktuálneho limitu hĺbky.
  • Treťou výhodou IDS je možnosť využitia na vyhľadávanie stromov aj grafov. Je to spôsobené tým, že IDS je všeobecný vyhľadávací algoritmus, ktorý funguje na akomkoľvek vyhľadávacom priestore vrátane stromu alebo grafu.

Nevýhody

  • IDS má tú nevýhodu, že potenciálne navštevuje určité uzly viac ako raz, čo môže spomaliť vyhľadávanie. Výhody úplnosti a optimality často prevyšujú túto nevýhodu. Navyše, použitím stratégií, ako je pamäť alebo ukladanie do vyrovnávacej pamäte, je možné minimalizovať opakované výlety.