Uninformed Search Algorithms

Uninformed Search Algorithms (خوارزميات البحث العمياء)

في مجال الذكاء الاصطناعي، نواجه كثيرًا الحاجة للبحث عن حلول أو مسارات للوصول إلى أهداف معينة ضمن بيئة غير معروفة بشكل كامل. خوارزميات البحث غير الموجه (Uninformed Search Algorithms) ولها اسم آخر معبر جداً "خوارزميات البحث العمياء (blind search algorithms)" هي تقنيات تساعدنا في استكشاف هذه البيئات والبحث عن الحلول من دون أي معلومات مسبقة، مثل المسافات أو الاتجاهات التي من المفترض أن نسير فيها. بمعنى آخر، تعمل هذه الخوارزميات على تجربة جميع المسارات الممكنة حتى تصل إلى الهدف، دون أن تعتمد على إرشادات أو تقديرات مسبقة توجهها.

Uninformed Search Algorithms - شرح مبسط

تركز هذه الخوارزميات بشكل رئيسي على فحص العقد (Nodes) المتاحة بشكل تدريجي، وتستخدم في مواقف حيث لا تتوفر لدينا أي معرفة مسبقة حول مكان الحل أو الطريق الأمثل للوصول إليه. وعلى الرغم من أن هذه الخوارزميات قد تكون بطيئة أو تتطلب ذاكرة كبيرة، إلا أنها تقدم حلولاً شاملة وتضمن العثور على الحل إذا كان يوجد حل بالفعل.

في هذا المقال، سنشرح بإذن الله بشكل موجز أبرز خوارزميات البحث العمياء، وهي: البحث بالعرض أولاً (Breadth-First Search)، البحث بالتكلفة الموحدة (Uniform-Cost Search)، البحث بالعمق أولاً (Depth-First Search)، البحث بعمق محدود (Depth-Limited Search)، البحث المتكرر بالعمق (Iterative Deepening Depth-First Search)، والبحث ثنائي الاتجاه (Bidirectional Search). سيكون الشرح مبسطاً قدر الإمكان. سعدت بوجودكم وأتمنى أن تجدوا الفائدة!

1- البحث بالعرض أولاً (Breadth-First Search - BFS)

Breadth-First Search (BFS) هي واحدة من أبسط وأهم خوارزميات البحث في مجال الذكاء الاصطناعي. تعتمد على استكشاف جميع العقد (nodes) القريبة من الحالة الأولية (initial state) أولاً، قبل الانتقال إلى العقد في المستوى التالي من العمق. أي أنها تستكشف العقد على مستوى عمق واحد بالكامل قبل الانتقال إلى المستوى الذي يليه.

ميزة BFS الأساسية هي أنها تضمن إيجاد أقصر مسار من الحالة الأولية إلى الحالة الهدف (goal state)، بشرط أن تكون تكلفة الخطوة غير متزايدة مع ازدياد العمق. هذا يعني أنه إذا كانت تكلفة الانتقال من عقدة إلى أخرى ثابتة أو تزداد بشكل ثابت مع ازدياد العمق، فستكون BFS قادرة على إيجاد أقصر مسار من البداية إلى الهدف.

الخوارزمية في كبسولة 💊

الفكرة الأساسية: استكشاف العقد الأقرب من البداية أولاً، بحيث ينتقل إلى المستوى التالي بعد إنهاء المستوى الحالي.

الخصائص: يضمن إيجاد الحل الأمثل (أقصر مسار) عندما تكون تكلفة الانتقال بين العقد متساوية.

العيوب: يتطلب ذاكرة كبيرة لأن جميع العقد في كل مستوى يجب حفظها قبل الانتقال إلى المستوى التالي.

الاستخدام: مناسب لإيجاد المسارات القصيرة، خاصة في الشبكات أو الـ graphs البسيطة.

2- البحث بالتكلفة الموحدة (Uniform-Cost Search - UCS)

Uniform-Cost Search (UCS) هي خوارزمية بحث شبيهة بـ Breadth-First Search (BFS)، ولكنها تأخذ تكلفة المسار في الاعتبار. بمعنى آخر، بدلاً من استكشاف جميع العقد على عمق معين قبل الانتقال إلى المستوى التالي (كما في BFS)، تقوم UCS بترتيب العقد بناءً على التكلفة (Cost) وتختار العقدة ذات التكلفة الأقل أولاً للاستكشاف.

شرح أوضح:

1. كيف تعمل:
تبدأ الخوارزمية من العقدة الابتدائية (initial node)، وتبحث عن العقدة التي تؤدي إلى الهدف (goal node) بأقل تكلفة. تستخدم UCS قائمة انتظار مرتبة (Priority Queue) بحيث تكون العقدة ذات التكلفة الأقل في المقدمة. وعندما تستكشف عقدة معينة، تقوم بإضافة جميع العقد المجاورة إلى قائمة الانتظار مع حساب تكلفة الوصول لكل منهم.

2. ضمان المسار الأمثل:
UCS تضمن إيجاد المسار الأمثل للوصول إلى العقدة الهدف، أي المسار الذي يحمل أقل تكلفة. هذا يحدث لأن الخوارزمية تبدأ دائمًا بأقل تكلفة أولًا، وعندما تصل إلى الهدف، تكون قد وجدت بالفعل المسار الأقل تكلفة.

3. التطبيقات:
تستخدم UCS في حالات يكون فيها للوصول لهدف ما أكثر من مسار، وكل مسار له تكلفة مختلفة. على سبيل المثال، يمكن استخدامها للعثور على المسار الأقل تكلفة للانتقال من محافظة المنوفية إلى محافظة القاهرة.

💡 ملاحظة: على عكس BFS، التي تفترض أن جميع التكلفات متساوية (كل خطوة لها نفس التكلفة)، تأخذ UCS في الحسبان اختلاف التكلفة.

الخوارزمية في كبسولة 💊

الفكرة الأساسية: يشبه BFS لكنه يعتمد على تكلفة الخطوات، بحيث يختار المسار ذو التكلفة الأقل للوصول إلى كل عقدة.

الخصائص: يضمن إيجاد المسار الأقل تكلفة؛ لذلك يُعد الأفضل عندما تختلف تكلفة الانتقال بين العقد.

العيوب: قد يكون بطيئًا ويستهلك ذاكرة كبيرة إذا كانت هناك مسارات متعددة بتكلفات مختلفة.

الاستخدام: مفيد في إيجاد المسارات ذات التكلفة الأقل، مثل اختيار الطريق الأفضل للوصول لمدينة أو مكان معين.

3- البحث بالعمق أولاً (Depth-First Search - DFS)

Depth-First Search (DFS) هي خوارزمية بحث أساسية أخرى في الذكاء الاصطناعي، وتعمل بطريقة مختلفة عن Breadth-First Search (BFS). بدلاً من استكشاف جميع العقد على نفس العمق قبل الانتقال إلى المستوى التالي، تستمر DFS في استكشاف عمق كل فرع حتى تصل إلى نهاية هذا الفرع، ثم تتراجع للخلف (backtracking) وتبدأ في استكشاف الفروع الأخرى.

شرح أوضح:

1. كيف تعمل:

تبدأ DFS من العقدة الابتدائية (initial node) وتستمر في الانتقال إلى أعمق نقطة في كل فرع قبل الانتقال إلى الفروع المجاورة. إذا وصلت إلى نهاية مسار بدون الوصول إلى الهدف، تتراجع (تعود إلى العقد السابقة) وتبدأ في استكشاف مسار آخر. تستخدم DFS هيكل بيانات stack للحفاظ على العقد التي يجب استكشافها. ويمكن استخدام الـ stack الذي نعرفه في مادة Data Structures & Algorithms مباشرةً أو يتم تحقيقه من خلال الاستدعاءات التكرارية (recursion).

2. المسار الأقصر:

DFS لا تضمن إيجاد المسار الأقصر للوصول إلى العقدة الهدف، لأنها قد تستمر في استكشاف مسارات أطول أو أقل كفاءة قبل أن تصل إلى الهدف.

3. استهلاك الذاكرة:

بالمقارنة مع BFS، تعتبر DFS غالباً أكثر كفاءة في استخدام الذاكرة، لأنها تحتفظ فقط بالعقد التي تم الوصول إليها في المسار الحالي. بينما BFS تحتاج إلى تخزين جميع العقد على كل مستوى، مما قد يستهلك ذاكرة كبيرة.

متى تستخدم DFS؟

- تعتبر DFS مناسبة عندما يكون الهدف في أعماق الـ tree أو الـ graph.

- يمكن أن تكون فعالة عندما لا يكون من الضروري إيجاد المسار الأمثل أو الأقصر، أو عندما تكون الذاكرة المتاحة محدودة.

مثال عملي:

تخيل أنك تستكشف متاهة، وبدلاً من تفقد كل المسارات القريبة أولاً، تختار الاستمرار في السير في كل طريق حتى تصل إلى نهايته، ثم تعود للخلف لاستكشاف طريق آخر. هذا يشبه تمامًا عمل DFS.

الخوارزمية في كبسولة 💊

الفكرة الأساسية: يغوص في عمق مسار واحد حتى يصل لنهايته أو يجد الهدف، ثم يعود للبحث في تفرع الآخر في حالة لم يجد الهدف.

الخصائص: يستهلك ذاكرة أقل مقارنة بـ BFS، خاصة في الـ graphs الكبيرة.

العيوب: قد يتورط في حلقات لانهائية إذا لم تتم معالجة العقد المتكررة، وقد لا يجد الحل الأمثل دائمًا.

الاستخدام: مناسب عندما تكون الذاكرة محدودة أو عندما يكون الحل في عمق معين.

4- البحث بعمق محدود (Depth-Limited Search - DLS)

Depth-Limited Search هي نسخة معدلة من خوارزمية Depth-First Search (DFS)، حيث يتم تحديد حد أقصى للعمق الذي يمكن للخوارزمية أن تستكشفه في الـ tree أو الـ graph. الهدف من هذه الخوارزمية هو تجنب الوقوع في حلقات لانهائية، خاصة عندما يكون فضاء البحث (search space) كبيرًا جدًا أو غير محدود.

كيف تعمل؟

في DLS، يتم تحديد "حد العمق" (Depth Limit) مسبقًا، ويُسمح للخوارزمية باستكشاف العقد حتى هذا العمق فقط. إذا وصلت الخوارزمية إلى العقدة التي تمثل الحد الأقصى للعمق المحدد مسبقًا ولم تصل إلى الهدف، فإنها تتوقف عن الاستكشاف في هذا الفرع وتبدأ في التراجع (backtracking) لاستكشاف الفروع الأخرى.

الاستخدامات:

- عندما يكون العمق معروفًا: DLS مفيدة في الحالات التي نعرف فيها أو نتوقع فيها عمق العقدة الهدف. في هذه الحالة، يمكننا تعيين الحد الأقصى للعمق وفقًا لمكان الهدف، مما يجعل البحث أكثر كفاءة.

- تجنب الحلقات اللانهائية: في الحالات التي يكون فيها فضاء البحث كبيرًا جدًا أو غير محدود، يمكن أن تقع DFS في حلقات لانهائية أو تستمر في استكشاف أعماق غير ضرورية. باستخدام DLS، يتم التحكم في هذا الأمر.

المزايا:

- تقليل المخاطر: بفضل الحد الأقصى للعمق، تقلل DLS من خطر الوقوع في الحلقات اللانهائية.

- كفاءة الذاكرة: بما أنها نسخة من DFS، فهي تستخدم ذاكرة أقل مقارنةً بخوارزمية Breadth-First Search (BFS).

العيوب:

- عدم العثور على الحل إذا كان أعمق من الحد المحدد: إذا كانت العقدة الهدف تقع في عمق أكبر من الحد الأقصى المحدد، فلن يتم العثور على الهدف باستخدام DLS، وقد يحتاج المستخدم إلى زيادة العمق وتجربة البحث مرة أخرى.

- غير مثالية: إذا كان هناك مسارات متعددة للوصول إلى الهدف، فقد لا تضمن DLS إيجاد المسار الأمثل (الأقصر).

مثال عملي:

تخيل أنك تبحث في مكتبة كبيرة جدًا عن كتاب معين، وتريد ألا تتجاوز البحث في رفوف المكتبة حتى عمق معين لتجنب تضييع وقت كبير. تقوم بتحديد رفوف معينة للبحث، وإذا لم تجد الكتاب في تلك الرفوف، تعود وتعيد المحاولة في أقسام أخرى أو تزيد الحد الأقصى لاحقًا.

الخوارزمية في كبسولة 💊

الفكرة الأساسية: مثل DFS، لكن بحد معين للعمق، حيث يتوقف عن البحث بالعمق بعد مستوى معين.

الخصائص: يمنع البحث بالعمق الزائد ويجنب الدخول في الحلقات اللانهائية.

العيوب: إذا كان الحل موجودًا في عمق أكبر من الحد المحدد، فقد يتم تجاوزه.

الاستخدام: مفيد عندما نحتاج لتحديد مستويات معينة في البحث ضمن نطاق معروف.

5- البحث المتكرر بالعمق (Iterative Deepening Depth-First Search - IDDFS)

IDDFS تجمع بين ميزات كل من خوارزمية Breadth-First Search (BFS) وخوارزمية Depth-First Search (DFS).

شرح أوضح:

كيف تعمل:

1. تكرار البحث: تقوم الخوارزمية بتطبيق Depth-First Search (DFS) بشكل متكرر مع زيادة حد العمق (depth limit) في كل مرة.

2. البداية بحدود صغيرة: تبدأ بحد عمق صغير (مثل 0)، ثم تقوم بإجراء DFS حتى تصل إلى هذا الحد أي 0. إذا لم تجد الهدف، تزيد الحد وتكرر العملية وهكذا.

3. استكشاف تدريجي: تستمر هذه العملية حتى يتم العثور على العقدة الهدف. كلما زاد العمق المسموح به، يتم استكشاف المزيد من الفروع.

المزايا:

- ضمان إيجاد المسار الأقصر: بفضل طريقة زيادة العمق التدريجية، تضمن IDDFS العثور على أقصر مسار للوصول إلى الهدف، مثل BFS.

- استخدام أقل للذاكرة: نظرًا لاعتمادها على DFS، تستخدم IDDFS الذاكرة بشكل أكثر كفاءة مقارنةً بـ BFS، حيث لا تحتفظ بسجلات جميع العقد في كل مستوى.

الخصائص:

- التكرار: تعيد استكشاف بعض العقد عدة مرات، مما قد يؤدي إلى استهلاك وقت إضافي، ولكن هذا يمكن التغاضي عنه نظرًا لمميزاتها.

- الكفاءة: تستخدم في حالة المساحات البحثية الكبيرة وعندما تكون الذاكرة محدودة، حيث يمكن أن تكون BFS غير فعالة.

متى تستخدم IDDFS؟

- عندما يكون الحل في عمق معين: تكون هذه الخوارزمية مناسبة عندما يكون لديك فكرة تقريبية عن عمق الهدف.

- عندما تحتاج إلى ذاكرة محدودة: إذا كان استخدام الذاكرة يمثل مشكلة، فكما ذكرت سابقاً الـ IDDFS هو خيار مناسب، حيث يوازن بين ضمان إيجاد الحل والاحتفاظ بالذاكرة.

مثال عملي:

تخيل أنك في حديقة كبيرة مليئة بالأشجار، وتبحث عن كنز مخفي فيها. لديك معلومات تفيد بأن الكنز موجود في وسط الحديقة، ولكنك لا تعرف المسار الصحيح. فهنا أنت ستأخذ طريق وتكمله للنهاية إلى أن تصل إلى نقطة معينة في الحديقة (عمق معين)، وخلال هذه الطريق تمر على كل أجزاء الحديقة (أي تستكشف المسارات المتاحة في كل عمق بشكل منهجي). إذا لم تجد الكنز خلال هذا الطريق ترجع وتأتي بالطريق من البداية مع زيادة النقطة التي تقف عندها في الحديقة. تستمر هكذا إلى أن تصل إلى الكنز.

الخوارزمية في كبسولة 💊

الفكرة الأساسية: يبدأ بعمق محدود ويزيد العمق تدريجيًا حتى يجد الهدف، مما يجعله مزيجًا بين DFS و BFS.
الخصائص: يجمع بين مزايا BFS في إيجاد الحل الأمثل ومزايا DFS في توفير الذاكرة.
العيوب: يكرر زيارة نفس العقد في كل عمق جديد، مما قد يزيد الوقت اللازم للوصول للحل.
الاستخدام: مثالي عندما نحتاج الحل الأمثل ونرغب في تجنب استهلاك قدر كبير من الذاكرة.

6- البحث ثنائي الاتجاه (Bidirectional Search)

الـ Bidirectional Search تستخدم لإيجاد أقصر مسار بين حالة ابتدائية (initial state) وحالة هدف (goal state). تعمل هذه الخوارزمية من خلال تنفيذ عمليتي بحث منفصلتين في آنٍ واحد: واحدة تبدأ من الحالة الابتدائية وتمتد للأمام، والأخرى تبدأ من الحالة الهدف وتمتد للخلف. يتوقف البحث عندما تلتقي العمليتان في نقطة وسطى. هذه الطريقة تكون مفيدة بشكل خاص في مساحات البحث الكبيرة، حيث قد تكون تقنيات البحث التقليدية مثل Depth-First Search (DFS) أو Breadth-First Search (BFS) غير فعالة أو بطيئة.

شرح أوضح:

كيف تعمل:

تعمل الخوارزمية بدمج بحثين متزامنين كما ذكرنا؛ لتقليل الوقت الإجمالي للبحث، خطوات عملها بالتفصيل:

1. الإعداد المبدئي (Initial Setup): يتم تهيئة عمليتي بحث، بحيث تبدأ الأولى من الحالة الابتدائية وتمتد للأمام، بينما تبدأ الثانية من الحالة الهدف وتمتد للخلف.

2. Alternate Search: الخوارزمية تتنقل بين البحثين، بحيث تقوم كل مرة بتوسيع عقدة جديدة في الـ Forward Search (البحث الأمامي) أو في الـ Backward Search (البحث الخلفي) بالتناوب. الهدف هو تقليل عدد العقد التي يجب استكشافها، لأن كل عملية توسع تقرب كلا البحثين من الالتقاء.

3. Expansion of the Node: عندما نقول "توسيع" عقدة، نقصد هنا توليد العقد المرتبطة مباشرةً بالعقدة الحالية. هناك نوعان من التوسع:

- في Forward Search : يتم النظر إلى الـ Successors (الخلفاء) لكل عقدة حالية، أي العقد التي يمكن الوصول إليها إذا تقدمنا خطوة للأمام.

- في Backward Search : يتم النظر إلى الـ Predecessors (الأسلاف)، أي العقد التي يمكن أن نأتي منها عند التحرك خطوة للخلف.

4. Meeting Point: بعد كل توسع، تتحقق الخوارزمية لمعرفة ما إذا كانت العقدة الموسعة قد تم استكشافها في البحث الآخر أيضًا (أي إذا كانت موجودة في frontier البحث الآخر أي حدود البحث الآخر). عندما تتطابق عقدة بين الـ Forward Search والـ Backward Search، فإن هذه العقدة تصبح نقطة التقاء.

باستخدام الـ Meeting Point، نستطيع تكوين الـ Optimal Path (المسار الأمثل) عن طريق ربط المسار من Initial State إلى Meeting Point (في البحث الأمامي) مع المسار من Goal State إلى Meeting Point (في البحث الخلفي).

المزايا:

هذا التناوب بين الـ Forward Search و الـ Backward Search يساعد في تقليل عدد العقد التي يجب استكشافها، مما يجعل Bidirectional Search أكثر كفاءة في المساحات الكبيرة مقارنةً بالبحث التقليدي.

💡 ملاحظة: نقطة الالتقاء (Meeting Point) لا تحتاج بالضرورة أن تكون عقدة واحدة؛ فقد تكون مجموعة من العقد، ويتم اختيار النقطة الأفضل أو الأقرب لتحقيق المسار الأمثل.

الخوارزمية في كبسولة 💊

الفكرة الأساسية: يتم البدء بالبحث من نقطة البداية ومن الهدف في نفس الوقت، ويتم اللقاء عند نقطة مشتركة.

الخصائص: أسرع من البحث في اتجاه واحد، لأنه يقلل من عدد العقد التي يجب زيارتها.

العيوب: يتطلب إدارة مسارين منفصلين وقد يصعب تطبيقه إذا كانت الشبكة غير واضحة أو معقدة.

الاستخدام: مفيد لإيجاد مسار بين نقطتين معروفتي الموقع، مثل إيجاد طريق بين مدينتين.

أنظر إلى هذه الصورة مهمة جداً لتعرف خصائص كل خوارزمية ذكرت بالأعلى بشكل أكثر دقة 👇👇

Properties of Uninformed Search Algorithms

💡 ملاحظة: قد تختلف قيم الـ Space Complexity والـ Time Complexity بالنسبة للخوارزميات إختلافات طفيفة جداً باختلاف المصادر.

الخاتمة

وإلى هنا يصديقي، أرجو أن تكون قد أستوعبت خوارزميات Uninformed Search Algorithms بأنواعها المختلفة جيداً، وأن يكون الموضوع واضح كفايةً بالنسبة لك. أرجو لي ولك التوفيق. إذا انتفعت مني بشئ ولو بسيط؛ فلا تنسني من صالح دعائك.

إذا وجدتم الفائدة، تابعوا مقالاتي وانضموا لقناة التلجرام (نتحدث في مواضيع أخرى في المجال كما سينزل عليها كل جديد في الموقع). لا تترددوا في مشاركة آرائكم أو استفساراتكم حول مقال اليوم في قسم التعليقات أدناه. أقدر تفاعلكم جداً، فآراؤكم تساعدني على تحسين المحتوى وتقديم ما يلبي احتياجاتكم.

كان معكم علي وحيد.

"اللهم إن كان من توفيق فمنك وحدك وإن كان من خطأ أو نسيان فمني ومن الشيطان."

المصادر

آخر الأخبار