Neatsiejama kompiuterių mokslo ir dirbtinio intelekto sudedamoji dalis yra paieškos algoritmai. Jie naudojami sprendžiant įvairias problemas – nuo ​​žaidimų, tokių kaip šachmatai ir šaškės, iki trumpiausio maršruto nustatymo žemėlapyje. Pirmosios gilumos paieškos (DFS) metodas, vienas populiariausių paieškos algoritmų, ieško tinkle ar medyje, kiek įmanoma nukeliaudamas išilgai kiekvienos šakos prieš apsisukdamas. Tačiau DFS turi esminį trūkumą: jei diagramoje yra ciklų, jis gali būti įstrigęs begalinėje kilpoje. Iteratyviosios gilinimo paieškos (IDS) arba kartotinės gilinimosi pirmosios paieškos naudojimas yra vienas iš būdų šiai problemai išspręsti (IDDFS).

Kas yra IDS?

Paieškos algoritmas, žinomas kaip IDS, sujungia DFS privalumus ir pirmąją paiešką (BFS). Grafikas tiriamas naudojant DFS, tačiau gylio riba nuolat didėjo, kol bus nustatytas tikslas. Kitaip tariant, IDS nuolat vykdo DFS, kiekvieną kartą didindama gylio ribą, kol bus gautas norimas rezultatas. Iteratyvus gilinimas – tai metodas, užtikrinantis, kad paieška būtų nuodugni (t. y. atrandama sprendimą, jei toks yra) ir veiksmingas (t. y. randamas trumpiausias kelias į tikslą).

IDS pseudokodas yra paprastas:

Kodas

 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 

Kaip veikia IDS?

IterativeDeepeningSearch funkcija atlieka kartotinę gilinimo paiešką grafike naudodama šakninį ir tikslo mazgą kaip įvestį, kol bus pasiektas tikslas arba išnaudota paieškos erdvė. Tai pasiekiama reguliariai naudojant deepLimitedSearch funkciją, kuri taiko gylio apribojimą DFS. Paieška baigiama ir grąžinamas tikslo mazgas, jei tikslas yra bet kuriame gylyje. Paieška duoda Nėra, jei paieškos vieta yra išnaudota (ištirti visi mazgai iki gylio ribos).

Funkcija deeplyLimitedSearch atlieka DFS grafike su nurodyta gylio riba, kaip įvestį paimdama mazgą, paskirties mazgą ir gylio ribą. Jei norimas mazgas yra esamame gylyje, paieška grąžina FOUND. Jei pasiekiama gylio riba, bet nepavyksta rasti tikslo mazgo, paieška rodo NOT FOUND. Jei nė vienas iš kriterijų nėra teisingas, paieška iteratyviai pereina prie mazgo palikuonių.

Programa:

Kodas

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

Išvestis

 Path found 

Privalumai

• IDS daugeliu atžvilgių pranašesnis už kitus paieškos algoritmus. Pirmas privalumas yra tai, kad jis yra išsamus, o tai užtikrina, kad sprendimas bus rastas, jei toks yra paieškos erdvėje. Taip yra todėl, kad visi mazgai, esantys pagal tam tikrą gylio ribą, būtų ištirti prieš pakeliant gylio ribą IDS, kuris atlieka gylio ribojamą DFS.
• IDS taupo atmintį, o tai yra antrasis privalumas. Taip yra todėl, kad IDS sumažina algoritmo atminties poreikį, nes atmintyje neišsaugo visų paieškos srities mazgų. IDS sumažina algoritmo atminties plotą, nes išsaugo tik mazgus iki dabartinės gylio ribos.
• Trečias privalumas yra IDS galimybė naudoti tiek medžio, tiek grafiko paieškai. Taip yra dėl to, kad IDS yra bendras paieškos algoritmas, veikiantis bet kurioje paieškos erdvėje, įskaitant medį ar grafiką.

Trūkumai

• IDS trūkumas yra tas, kad tam tikruose mazguose galima apsilankyti daugiau nei vieną kartą, o tai gali sulėtinti paiešką. Išsamumo ir optimalumo privalumai dažnai viršija šį trūkumą. Be to, naudojant tokias strategijas kaip atmintis arba talpyklos kaupimas, pasikartojančias keliones galima sumažinti iki minimumo.