تعد خوارزميات البحث جزءًا لا يتجزأ من علوم الكمبيوتر والذكاء الاصطناعي. يتم استخدامها لحل مجموعة متنوعة من المشكلات، بدءًا من ممارسة الألعاب مثل الشطرنج ولعبة الداما وحتى تحديد موقع أقصر طريق على الخريطة. تقوم طريقة Depth First Search (DFS)، وهي إحدى خوارزميات البحث الأكثر شيوعًا، بالبحث في شبكة أو شجرة عن طريق السفر إلى أقصى حد ممكن على طول كل فرع قبل الدوران. ومع ذلك، فإن DFS له عيب خطير: إذا كان الرسم البياني يحتوي على دورات، فقد يصبح محاصرًا في حلقة لا نهاية لها. يعد استخدام بحث التعميق التكراري (IDS) أو البحث الأول في عمق التعميق التكراري أحد الأساليب لحل هذه المشكلة (IDDFS).
ما هو معرف الهوية؟
تجمع خوارزمية البحث المعروفة باسم IDS بين فوائد DFS وBroadth 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 بإجراء بحث تعميق تكراري على الرسم البياني باستخدام العقدة الجذرية وعقدة الهدف كمدخلات حتى يتم تحقيق الهدف أو استخدام مساحة البحث. ويتم تحقيق ذلك عن طريق استخدام وظيفة DeepLimitedSearch بشكل منتظم، والتي تطبق قيودًا على العمق على DFS. ينتهي البحث ويعيد عقدة الهدف إذا كان الهدف يقع على أي عمق. لا ينتج عن البحث أي شيء إذا تم استخدام مساحة البحث (تم فحص جميع العقد حتى حد العمق).
تقوم وظيفة DeepLimitedSearch بإجراء DFS على الرسم البياني مع حد العمق المحدد عن طريق أخذ عقدة وعقدة وجهة وحد عمق كمدخلات. يقوم البحث بإرجاع 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 عيب احتمال زيارة عقد معينة أكثر من مرة، مما قد يؤدي إلى إبطاء البحث. فوائد الاكتمال والمثالية كثيرا ما تتجاوز هذا العيب. بالإضافة إلى ذلك، من خلال استخدام استراتيجيات مثل الذاكرة أو التخزين المؤقت، يمكن تقليل الرحلات المتكررة.