A számítástechnika és a mesterséges intelligencia szerves részét képezik a keresési algoritmusok. Számos probléma megoldására használják őket, kezdve a sakk- és dámajátékoktól a legrövidebb útvonal megtalálásáig a térképen. A Depth First Search (DFS) módszer, az egyik legnépszerűbb keresési algoritmus, úgy keres egy hálózatot vagy fát, hogy a lehető legmesszebbre halad az egyes ágak mentén, mielőtt megfordulna. A DFS-nek azonban van egy kritikus hátránya: ha a gráf ciklusokat tartalmaz, akkor egy végtelen hurok csapdájába kerülhet. A probléma megoldásának egyik módja az iteratív mélyítő keresés (IDS) vagy az iteratív elmélyítő mélységű első keresés használata.

Mi az az IDS?

Az IDS néven ismert keresési algoritmus egyesíti a DFS és a Breadth First Search (BFS) előnyeit. A grafikon feltárása DFS segítségével történik, de a mélységhatár folyamatosan nőtt, amíg a célt meg nem találjuk. Más szóval, az IDS folyamatosan futtatja a DFS-t, minden alkalommal növelve a mélységhatárt, amíg el nem éri a kívánt eredményt. Az iteratív elmélyítés egy olyan módszer, amely biztosítja, hogy a keresés alapos legyen (vagyis megtalálja a megoldást, ha létezik) és hatékony (azaz megtalálja a célhoz vezető legrövidebb utat).

Az IDS pszeudokódja egyszerű:

Kód

 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 

Hogyan működik az IDS?

Az iterativeDeepeningSearch függvény iteratív mélyítő keresést hajt végre a grafikonon egy gyökércsomópont és egy célcsomópont bemeneteként mindaddig, amíg a célt el nem érik, vagy a keresési területet el nem használják. Ez a deepLimitedSearch funkció rendszeres használatával érhető el, amely mélységkorlátozást alkalmaz a DFS-re. A keresés véget ér, és visszaadja a célcsomópontot, ha a cél bármely mélységben található. A keresés eredménye nincs, ha a keresési területet kimerítettük (a mélységi határig minden csomópontot megvizsgáltunk).

A deepLimitedSearch függvény DFS-t hajt végre a grafikonon a megadott mélységhatárral úgy, hogy bemenetként vesz egy csomópontot, egy célcsomópontot és egy mélységkorlátot. A keresés a TALÁLT értéket adja vissza, ha a kívánt csomópont az aktuális mélységben található. A keresés a NEM TALÁLHATÓ értéket adja vissza, ha elérte a mélységi határt, de a célcsomópont nem található. Ha egyik feltétel sem igaz, a keresés iteratív módon továbblép a csomópont utódjára.

Program:

Kód

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

Kimenet

 Path found 

Előnyök

• Az IDS számos szempontból felülmúlja a többi keresési algoritmust. Az első előnye, hogy átfogó, ami biztosítja, hogy megoldást találjanak, ha az ember ott van a keresőtérben. Ennek célja, hogy egy adott mélységhatár alatti összes csomópontot megvizsgáljon, mielőtt az IDS megemeli a mélységhatárt, amely mélységkorlátozott DFS-t végez.
• Az IDS memóriatakarékos, ami a második előnye. Ennek az az oka, hogy az IDS csökkenti az algoritmus memóriaigényét azáltal, hogy nem tárol minden csomópontot a keresési területen a memóriában. Az IDS minimalizálja az algoritmus memóriaterületét azáltal, hogy csak az aktuális mélységhatárig tárolja a csomópontokat.
• Az IDS azon képessége, hogy fa- és gráfkeresésre egyaránt használható, a harmadik előnye. Ez annak a ténynek köszönhető, hogy az IDS egy általános keresési algoritmus, amely bármely keresési területen működik, beleértve a fát vagy a grafikont is.

Hátrányok

• Az IDS hátránya, hogy adott csomópontokat többször is felkeres, ami lelassíthatja a keresést. A teljesség és az optimálisság előnyei gyakran meghaladják ezt a hátrányt. Ezenkívül olyan stratégiák alkalmazásával, mint a memória vagy a gyorsítótár, az ismétlődő utak minimalizálhatók.