Саставни део рачунарства и вештачке интелигенције су алгоритми претраживања. Користе се за решавање разних проблема, од играња игара попут шаха и дама до лоцирања најкраће руте на мапи. Метода Дептх Фирст Сеарцх (ДФС), један од најпопуларнијих алгоритама за претрагу, претражује мрежу или дрво тако што путује што је даље могуће дуж сваке гране пре него што се окрене. Међутим, ДФС има критичан недостатак: ако граф садржи циклусе, могао би постати заробљен у бескрајној петљи. Коришћење итеративног продубљивања претраге (ИДС) или итеративног продубљивања претраге прве дубине је једна од техника за решавање овог проблема (ИДДФС).
Шта је ИДС?
Алгоритам претраге познат као ИДС комбинује предности ДФС-а са претрагом у ширину (БФС). Графикон се истражује помоћу ДФС-а, али граница дубине се стално повећава све док се циљ не пронађе. Другим речима, ИДС непрекидно покреће ДФС, подижући границу дубине сваки пут, све док се не добије жељени резултат. Итеративно продубљивање је метода која осигурава да претрага буде темељна (тј. открива решење ако постоји) и ефикасна (тј. проналази најкраћи пут до циља).
Псеудокод за ИДС је једноставан:
Код
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
Како ИДС функционише?
Функција итеративеДеепенингСеарцх врши итеративно продубљивање претраге на графу користећи основни чвор и циљни чвор као улазе све док се циљ не постигне или се простор за претрагу не потроши. Ово се постиже редовним коришћењем функције деепЛимитедСеарцх, која примењује ограничење дубине на ДФС. Претрага се завршава и враћа чвор циља ако се циљ налази на било којој дубини. Претрага даје Ништа ако је простор за претрагу потрошен (сви чворови до границе дубине су истражени).
Функција деепЛимитедСеарцх спроводи ДФС на графу са специфицираном границом дубине узимајући као улазе чвор, одредишни чвор и ограничење дубине. Претрага враћа ФОУНД ако се жељени чвор налази на тренутној дубини. Претрага се враћа НИЈЕ ПРОНАЂЕН ако је граница дубине достигнута, али се циљни чвор не може лоцирати. Ако ниједан критеријум није тачан, претрага итеративно прелази на потомство чвора.
Програм:
Код
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
Предности
- ИДС је супериорнији од других алгоритама за претрагу на више начина. Прва предност је то што је свеобухватан, што осигурава да ће се решење пронаћи ако постоји у простору за претрагу. Ово је тако да се сви чворови под одређеним ограничењем дубине истражују пре него што ИДС подигне ограничење дубине, који ради ДФС ограничен на дубину.
- ИДС је меморијски ефикасан, што је његова друга предност. То је зато што ИДС смањује меморијске потребе алгоритма тако што не чува сваки чвор у области претраге у меморији. ИДС минимизира меморијски отисак алгоритма тако што чува чворове само до тренутног ограничења дубине.
- Могућност ИДС-а да се користи и за претраживање стабла и графова је његова трећа предност. Ово је због чињенице да је ИДС генерички алгоритам претраживања који ради на било ком простору за претрагу, укључујући стабло или граф.
Недостаци
- ИДС има недостатак потенцијалне посете одређеним чворовима више пута, што би могло успорити претрагу. Предности комплетности и оптималности често превазилазе овај недостатак. Поред тога, коришћењем стратегија попут меморије или кеширања, поновљена путовања се могу свести на минимум.