Integralną częścią informatyki i sztucznej inteligencji są algorytmy wyszukiwania. Służą do rozwiązywania różnych problemów, od grania w gry takie jak szachy i warcaby po znajdowanie najkrótszej trasy na mapie. Metoda Depth First Search (DFS), jeden z najpopularniejszych algorytmów wyszukiwania, przeszukuje sieć lub drzewo, przemieszczając się jak najdalej wzdłuż każdej gałęzi, zanim się zawróci. Jednakże DFS ma krytyczną wadę: jeśli wykres zawiera cykle, może zostać uwięziony w nieskończonej pętli. Wykorzystywanie iteracyjnego pogłębiania wyszukiwania (IDS) lub iteracyjnego pogłębiania pierwszego wyszukiwania jest jedną z technik rozwiązania tego problemu (IDDFS).

Co to jest IDS?

Algorytm wyszukiwania znany jako IDS łączy zalety DFS z wyszukiwaniem wszerz (BFS). Wykres jest badany za pomocą DFS, ale limit głębokości stale wzrasta, aż do zlokalizowania celu. Innymi słowy, IDS stale uruchamia DFS, za każdym razem podnosząc limit głębokości, aż do uzyskania pożądanego rezultatu. Pogłębianie iteracyjne to metoda, która zapewnia, że ​​wyszukiwanie jest dokładne (tj. odkrywa rozwiązanie, jeśli takie istnieje) i efektywne (tj. znajduje najkrótszą drogę do celu).

Pseudokod dla IDS jest prosty:

Kod

 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 

Jak działa IDS?

Funkcja iterativeDeepeningSearch wykonuje iteracyjne wyszukiwanie pogłębiające na wykresie, wykorzystując węzeł główny i węzeł docelowy jako dane wejściowe, aż do osiągnięcia celu lub wykorzystania przestrzeni poszukiwań. Osiąga się to poprzez regularne używanie funkcji głębokośćLimitedSearch, która stosuje ograniczenie głębokości do systemu DFS. Wyszukiwanie kończy się i zwraca węzeł celu, jeśli cel znajduje się na dowolnej głębokości. Wyszukiwanie daje Brak, jeśli przestrzeń poszukiwań jest zajęta (zbadano wszystkie węzły aż do limitu głębokości).

Funkcja głębokośćLimitedSearch przeprowadza DFS na wykresie z określonym limitem głębokości, przyjmując jako dane wejściowe węzeł, węzeł docelowy i limit głębokości. Wyszukiwanie zwraca FOUND, jeśli żądany węzeł znajduje się na bieżącej głębokości. Wyszukiwanie zwraca wartość NOT FOUND, jeśli osiągnięto limit głębokości, ale nie można zlokalizować węzła docelowego. Jeśli żadne z kryteriów nie jest prawdziwe, wyszukiwanie iteracyjnie przechodzi do elementów potomnych węzła.

Program:

Kod

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

Wyjście

 Path found 

Zalety

• IDS pod wieloma względami przewyższa inne algorytmy wyszukiwania. Pierwszą korzyścią jest to, że jest kompleksowy, co gwarantuje, że rozwiązanie zostanie znalezione, jeśli znajdzie się ono w przestrzeni poszukiwań. Dzieje się tak, że wszystkie węzły poniżej określonego limitu głębokości są sprawdzane, zanim limit głębokości zostanie podniesiony przez IDS, który wykonuje DFS o ograniczonej głębokości.
• IDS oszczędza pamięć i to jest jego druga zaleta. Dzieje się tak, ponieważ IDS zmniejsza zapotrzebowanie algorytmu na pamięć, nie przechowując w pamięci każdego węzła w obszarze wyszukiwania. IDS minimalizuje zużycie pamięci algorytmu, przechowując tylko węzły do ​​aktualnego limitu głębokości.
• Trzecią zaletą IDS jest możliwość wykorzystania go zarówno do wyszukiwania drzew, jak i wykresów. Wynika to z faktu, że IDS jest ogólnym algorytmem wyszukiwania, który działa na dowolnej przestrzeni poszukiwań, w tym na drzewie lub wykresie.

Niedogodności

• IDS ma tę wadę, że może odwiedzać określone węzły więcej niż raz, co może spowolnić wyszukiwanie. Korzyści z kompletności i optymalności często przewyższają tę wadę. Ponadto, stosując strategie takie jak pamięć lub buforowanie, można zminimalizować powtarzające się podróże.