Невід’ємною складовою інформатики та штучного інтелекту є пошукові алгоритми. Вони використовуються для вирішення різноманітних завдань, від гри в шахи та шашки до визначення найкоротшого маршруту на карті. Метод Depth First Search (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 на графіку з указаним обмеженням глибини, беручи як вхідні дані вузол, вузол призначення та обмеження глибини. Пошук повертає ЗНАЙДЕНО, якщо потрібний вузол знаходиться на поточній глибині. Пошук повертає 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 є загальним алгоритмом пошуку, який працює в будь-якому просторі пошуку, включаючи дерево або граф.
Недоліки
- Недоліком IDS є потенційне відвідування певних вузлів більше одного разу, що може уповільнити пошук. Переваги повноти та оптимальності часто перевищують цей недолік. Крім того, використовуючи такі стратегії, як пам’ять або кешування, повторні поїздки можна мінімізувати.