Неразделна част от компютърните науки и изкуствения интелект са алгоритмите за търсене. Те се използват за решаване на различни проблеми, от игри като шах и дама до намиране на най-краткия маршрут на карта. Методът за първо търсене в дълбочина (DFS), един от най-популярните алгоритми за търсене, търси мрежа или дърво, като пътува възможно най-далеч по всеки клон, преди да се обърне. DFS обаче има критичен недостатък: ако графиката съдържа цикли, тя може да попадне в безкраен цикъл. Използването на итеративно задълбочено търсене (IDS) или итеративно задълбочено първо търсене в дълбочина е една техника за решаване на този проблем (IDDFS).

Какво е IDS?

Алгоритъм за търсене, известен като IDS, съчетава предимствата на DFS с първо търсене в ширина (BFS). Графиката се изследва с помощта на DFS, но ограничението на дълбочината непрекъснато се увеличава, докато целта не бъде локализирана. С други думи, IDS непрекъснато изпълнява DFS, като всеки път повишава ограничението на дълбочината, докато се получи желаният резултат. Итеративното задълбочаване е метод, който гарантира, че търсенето е задълбочено (т.е. открива решение, ако такова съществува) и ефективно (т.е. намира най-краткия път до целта).

Псевдокодът за IDS е ясен:

Код

 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 

Как работи IDS?

Функцията iterativeDeepeningSearch извършва итеративно задълбочаващо търсене на графиката, като използва основен възел и целеви възел като входове, докато целта бъде постигната или пространството за търсене се изразходва. Това се постига чрез редовно използване на функцията deepLimitedSearch, която прилага ограничение на дълбочината към DFS. Търсенето приключва и връща целевия възел, ако целта се намира на произволна дълбочина. Търсенето дава Няма, ако пространството за търсене е изчерпано (всички възли до ограничението на дълбочината са изследвани).

Функцията deepLimitedSearch провежда DFS върху графиката с указаното ограничение на дълбочината, като приема като вход възел, възел на местоназначение и ограничение на дълбочината. Търсенето връща FOUND, ако желаният възел се намира на текущата дълбочина. Търсенето връща NOT FOUND, ако ограничението на дълбочината е достигнато, но целевият възел не може да бъде локализиран. Ако нито един критерий не е верен, търсенето итеративно преминава към наследника на възела.

програма:

Код

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

Изход

 Path found 

Предимства

• IDS превъзхожда другите алгоритми за търсене по много начини. Първото предимство е, че е изчерпателен, което гарантира, че ще бъде намерено решение, ако има такова в пространството за търсене. Това е така, че всички възли под определено ограничение на дълбочината се изследват, преди ограничението на дълбочината да бъде повишено от IDS, което прави DFS с ограничена дълбочина.
• IDS е ефективен по отношение на паметта, което е второто му предимство. Това е така, защото IDS намалява нуждите от памет на алгоритъма, като не съхранява всеки възел в областта за търсене в паметта. IDS минимизира отпечатъка на паметта на алгоритъма, като съхранява само възлите до текущото ограничение на дълбочината.
• Способността на IDS да се използва както за дървовидно, така и за графично търсене е третото му предимство. Това се дължи на факта, че IDS е общ алгоритъм за търсене, който работи във всяко пространство за търсене, включително дърво или графика.

Недостатъци

• IDS има недостатъка потенциално да посещава определени възли повече от веднъж, което може да забави търсенето. Ползите от пълнотата и оптималността често надхвърлят този недостатък. В допълнение, чрез използване на стратегии като памет или кеширане, повтарящите се пътувания могат да бъдат сведени до минимум.