Datorzinātnes un mākslīgā intelekta neatņemama sastāvdaļa ir meklēšanas algoritmi. Tos izmanto dažādu problēmu risināšanai, sākot no tādu spēļu kā šaha un dambretes spēlēšanas līdz īsākā maršruta atrašanai kartē. Pirmā dziļuma meklēšanas (DFS) metode, kas ir viens no populārākajiem meklēšanas algoritmiem, meklē tīklu vai koku, pārvietojoties pēc iespējas tālāk pa katru zaru, pirms apgriežas. Tomēr DFS ir būtisks trūkums: ja grafikā ir cikli, tas var tikt iesprostots bezgalīgā cilpā. Iteratīvās padziļinātās meklēšanas (IDS) vai iteratīvās padziļināšanas pirmās meklēšanas izmantošana ir viens no šīs problēmas risināšanas paņēmieniem (IDDFS).

Kas ir IDS?

Meklēšanas algoritms, kas pazīstams kā IDS, apvieno DFS priekšrocības ar pirmo meklēšanu (BFS). Grafiks tiek izpētīts, izmantojot DFS, bet dziļuma ierobežojums nepārtraukti palielinājās, līdz tiek atrasts mērķis. Citiem vārdiem sakot, IDS nepārtraukti palaiž DFS, katru reizi paaugstinot dziļuma ierobežojumu, līdz tiek iegūts vēlamais rezultāts. Iteratīvā padziļināšana ir metode, kas nodrošina, ka meklēšana ir rūpīga (t.i., tā atklāj risinājumu, ja tāds pastāv) un efektīva (t.i., tā atrod īsāko ceļu uz mērķi).

IDS pseidokods ir vienkāršs:

Kods

 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 

Kā darbojas IDS?

IterativeDeepeningSearch funkcija veic iteratīvu padziļinātu meklēšanu grafikā, izmantojot saknes mezglu un mērķa mezglu kā ievadi, līdz tiek sasniegts mērķis vai tiek izmantota meklēšanas vieta. Tas tiek panākts, regulāri izmantojot funkciju deepLimitedSearch, kas DFS piemēro dziļuma ierobežojumu. Meklēšana beidzas un atgriež mērķa mezglu, ja mērķis atrodas jebkurā dziļumā. Meklēšana dod Nevienu, ja meklēšanas vieta ir izmantota (ir izpētīti visi mezgli līdz dziļuma robežai).

Funkcija dziļumsLimitedSearch veic DFS grafikā ar norādīto dziļuma ierobežojumu, kā ievadi izmantojot mezglu, galamērķa mezglu un dziļuma ierobežojumu. Meklēšana atgriež FOUND, ja vajadzīgais mezgls atrodas pašreizējā dziļumā. Meklēšana atgriež NOT FOUND, ja ir sasniegta dziļuma robeža, bet mērķa mezglu nevar atrast. Ja neviens no kritērijiem nav patiess, meklēšana iteratīvi pāriet uz mezgla pēcnācējiem.

Programma:

Kods

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

Izvade

 Path found 

Priekšrocības

• IDS vairākos veidos ir pārāks par citiem meklēšanas algoritmiem. Pirmais ieguvums ir tas, ka tas ir visaptverošs, kas nodrošina, ka risinājums tiks atrasts, ja tāds atradīsies meklēšanas telpā. Tas tiek darīts, lai visi mezgli zem noteikta dziļuma robežas tiktu izpētīti, pirms dziļuma ierobežojumu paaugstina IDS, kas veic dziļuma ierobežotu DFS.
• IDS efektīvi izmanto atmiņu, kas ir tā otrā priekšrocība. Tas ir tāpēc, ka IDS samazina algoritma atmiņas vajadzības, nesaglabājot atmiņā katru meklēšanas apgabala mezglu. IDS samazina algoritma atmiņas nospiedumu, saglabājot mezglus tikai līdz pašreizējam dziļuma ierobežojumam.
• IDS spēja izmantot gan koku, gan grafiku meklēšanai ir tās trešā priekšrocība. Tas ir saistīts ar faktu, ka IDS ir vispārīgs meklēšanas algoritms, kas darbojas jebkurā meklēšanas vietā, tostarp kokā vai diagrammā.

Trūkumi

• IDS trūkums ir iespēja apmeklēt noteiktus mezglus vairāk nekā vienu reizi, kas var palēnināt meklēšanu. Pilnības un optimāluma priekšrocības bieži pārsniedz šo trūkumu. Turklāt, izmantojot tādas stratēģijas kā atmiņa vai kešatmiņa, atkārtotos braucienus var samazināt līdz minimumam.