מרכיב אינטגרלי של מדעי המחשב והבינה המלאכותית הם אלגוריתמי חיפוש. הם משמשים לפתרון מגוון בעיות, החל ממשחקים כמו שחמט ודמקה ועד איתור המסלול הקצר ביותר במפה. שיטת Depth First Search (DFS), אחד מאלגוריתמי החיפוש הפופולריים ביותר, מחפשת רשת או עץ על ידי נסיעה רחוק ככל האפשר לאורך כל ענף לפני שמסתובבים. עם זאת, ל-DFS יש חיסרון קריטי: אם הגרף מכיל מחזורים, הוא עלול להילכד בלולאה אינסופית. שימוש בחיפוש העמקה איטרטיבי (IDS) או חיפוש העמקה איטרטיבי ראשון הוא טכניקה אחת לפתרון בעיה זו (IDDFS).

מה זה IDS?

אלגוריתם חיפוש המכונה IDS משלב את היתרונות של DFS עם Breadth First Search (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 מבצעת חיפוש העמקה איטרטיבי על הגרף באמצעות צומת שורש וצומת יעד כקלט עד להשגת המטרה או למיצוי שטח החיפוש. זה מושג על ידי שימוש קבוע בפונקציית depthLimitedSearch, המחילה הגבלת עומק על DFS. החיפוש מסתיים ומחזיר את צומת המטרה אם המטרה נמצאת בעומק כלשהו. החיפוש מניב ללא אם שטח החיפוש מנוצל (כל הצמתים עד גבול העומק נחקרו).

הפונקציה depthLimitedSearch מבצעת 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 יש את החיסרון של ביקור בצמתים מסוימים יותר מפעם אחת, מה שעשוי להאט את החיפוש. היתרונות של שלמות ואופטימליות עולים לעתים קרובות על החיסרון הזה. בנוסף, על ידי שימוש באסטרטגיות כמו זיכרון או מטמון, ניתן למזער את הנסיעות החוזרות ונשנות.