logo

TechCodeview

Iterativno poglabljanje (IDS) ali iterativno poglabljanje po globini (IDDFS)

Sestavni del računalništva in umetne inteligence so iskalni algoritmi. Uporabljajo se za reševanje različnih težav, od igranja iger, kot sta šah in dama, do iskanja najkrajše poti na zemljevidu. Metoda DFS (Depth First Search), eden najbolj priljubljenih iskalnih algoritmov, išče omrežje ali drevo tako, da potuje čim dlje vzdolž vsake veje, preden se obrne. Vendar ima DFS pomembno pomanjkljivost: če graf vsebuje cikle, se lahko ujame v neskončno zanko. Uporaba iterativnega poglobljenega iskanja (IDS) ali iterativnega poglobljenega iskanja po globini je ena od tehnik za rešitev te težave (IDDFS).

Kaj je IDS?

Iskalni algoritem, znan kot IDS, združuje prednosti DFS in BFS (Breadth First Search). Graf se raziskuje z uporabo DFS, vendar se meja globine vztrajno povečuje, dokler ni lociran cilj. Z drugimi besedami, IDS nenehno izvaja DFS in vsakič dviguje mejo globine, dokler ni dosežen želeni rezultat. Iterativno poglabljanje je metoda, ki poskrbi, da je iskanje temeljito (tj. odkrije rešitev, če ta obstaja) in učinkovito (tj. najde najkrajšo pot do cilja).

Psevdokoda za IDS je preprosta:

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

Kako deluje IDS?

Funkcija iterativeDeepeningSearch izvaja iterativno poglobljeno iskanje na grafu z uporabo korenskega vozlišča in ciljnega vozlišča kot vhodnih podatkov, dokler ni cilj dosežen ali je iskalni prostor porabljen. To se doseže z redno uporabo funkcije deepLimitedSearch, ki za DFS uveljavi omejitev globine. Iskanje se konča in vrne ciljno vozlišče, če se cilj nahaja na kateri koli globini. Iskanje prinese Nič, če je iskalni prostor porabljen (preiskana so bila vsa vozlišča do omejitve globine).

Funkcija depthLimitedSearch izvede DFS na grafu z določeno omejitvijo globine, tako da kot vhodne podatke vzame vozlišče, ciljno vozlišče in omejitev globine. Iskanje vrne FOUND, če se želeno vozlišče nahaja na trenutni globini. Iskanje vrne NOT FOUND, če je dosežena omejitev globine, vendar ciljnega vozlišča ni mogoče najti. Če noben kriterij ni resničen, se iskanje iterativno premakne na potomce vozlišča.

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

Izhod 

 Path found

Prednosti

  • IDS je na več načinov boljši od drugih iskalnih algoritmov. Prva prednost je, da je celovit, kar zagotavlja, da bo rešitev najdena, če je v iskalnem prostoru. To je tako, da so vsa vozlišča pod določeno omejitvijo globine raziskana, preden IDS dvigne omejitev globine, ki izvaja DFS z omejeno globino.
  • IDS je pomnilniško učinkovit, kar je njegova druga prednost. To je zato, ker IDS zmanjša pomnilniške potrebe algoritma, tako da ne shrani vsakega vozlišča v območju iskanja v pomnilnik. IDS zmanjša pomnilniški odtis algoritma tako, da shrani samo vozlišča do trenutne omejitve globine.
  • Njegova tretja prednost je zmožnost IDS, da se uporablja tako za iskanje po drevesih kot za iskanje po grafih. To je posledica dejstva, da je IDS generični iskalni algoritem, ki deluje na katerem koli iskalnem prostoru, vključno z drevesom ali grafom.

Slabosti

  • IDS ima pomanjkljivost, da lahko določena vozlišča obišče večkrat, kar lahko upočasni iskanje. Prednosti popolnosti in optimalnosti pogosto presegajo to pomanjkljivost. Poleg tega je mogoče z uporabo strategij, kot sta pomnilnik ali predpomnilnik, zmanjšati ponavljajoče se izlete.