في مَعْرض البحث عن الحالة الهدف، توجد طريقتان أساسيتان للبحث:
الطريقة الأولى: البحث غير المستنير ( Uninformed Search )، في ما يُعرَف بطرائق البحث العمياء (Blind Search)
الطريقة الثانية: البحث المستنير أو البحث الاستدلالي (Informed or Heuristic Search)
سنتعرَف في هذا الدرس الفرق بين هاتين الطريقتين، وكيف يُمكن توظيف ك منهما في حَل المشكلات باستخدام تقنيات الذكاء الاصطناعي
أوَّلًا: طرائق البحث العمياء(Blinded Search Strategies)
تُعرف طرائق البحث العمياء بأنَها استراتيجيات بحث لا تعتمد على معلومات إضافية عن موقع الحَل داخل فضاء البحث، بل تقوم على استكشاف جميع الاحتمالات المُحتمَلة (المُمكنة) بشكل مُنظَّم حتّى الوصول إلى الحَلِّ المطلوب.
من الأمثلة على هذا النوع من الاستراتيجيات:
- البحث في العمق أوَّلًا (Depth-First Search)
- البحث في العرض أوَّلًا ( Breadth-First Search)
- البحث العشوائي (Random Search)
- البحث ذو التكلفة المُوحَّدة ( Uniform Cost Search)
سنتعرَّف في هذا الدرس طريقة البحث في العمق أوَّلًا وطريقة البحث في العرض أولا على نحوٍ مُفصَّل، ونتعلَّم كيف يُمكِن تطبيق هاتين الطريقتين على مسائل مُتنوِّعة.
1 - خوارزمية البحث في العمق أوَّلًا: (Depth-First Search)
تعتمد خوارزمية البحث في العمق أوَّلًا على بدء البحث من جذر شجرة البحث، ثمَّ التعمُّق - ما أمكن- في كل فرع من الفروع قبل الانتقال إلى الفرع الآخر.
آليَّة عمل خوارزمية البحث في العمق أوَّلًا :
- بَدْء بحث الخوارزمية من جذر شجرة البحث.
- انتقال الخوارزمية لاستكشاف العُقْدة أقصى اليسار في المستوى الثاني، وتفحُّص إذا كانت هي الحالة الهدف أم لا.
- في حال لم تكن هذه العُقْدة هي الحالة الهدف، فإنَّ الخوارزمية تُتابِع التعمُّق إلى المستوى الثالث، حيث تستكشف أبناء العُقْدة السابقة بَدْءًا بالعُقْدة الموجودة أقصى اليسار.
- استمرار الخوارزمية في التعمُّق داخل الشجرة - قَدْر الإمكان- حتّى تصل إلى الحالة الهدف، فتتوقَّف عندئذٍ.
- عند وصول الخوارزمية إلى عُقْدة ميتة (أيْ عُقْدة ليس لها أبناء، ولا تُمثِّل الحالة الهدف(، فإنَّها تعود إلى العُقْدة الأب لهذه العُقْدة الميتة، ثم تنتقل لاستكشاف العُقْدة التالية التي تقع إلى اليمين، والتي لم يتم استكشافها بعد
لتوضيح آليَّةَ عمل خوارزمية البحث في العمق أوَّلًا ، أنظر الشكل( 2- 1) الذي يُبيِّن الحالات المُحتمَلة (المُمكِنة) للعبة لغز( الأرقام الثمانية 8-Puzzle ):
- تُسمّى الحالة الابتدائية ( A)، وهي نقطة البداية.
- من الحالة الابتدائية ( A)، انبثقت ثلاث حالات، هي:
- الحالة (B) التي نتجت من تحريك المُربَّع الذي يحمل الرقم (1) إلى الأسفل.
- الحالة (C)التي نتجت من تحريك المُربَّع الذي يحمل الرقم ( 4) إلى اليسار.
- الحالة( D) التي نتجت من تحريك المُربَّع الذي يحمل الرقم( 7) إلى الأعلى.
- عند الانتقال إلى المستوى الثالث من شجرة البحث، يتمُّ التعامل مع الحالة ( C)، حيث تنبثق عنها ثلاث حالات جديدة، هي:
- الحالة ( E) التي نتجت من تحريك الرقم(5) إلى الأعلى.
- الحالة( F) التي نتجت من تحريك الرقم(6) إلى اليسار.
- الحالة ( G) التي نتجت من تحريك الرقم (2) إلى الأسفل.
- في المستوى الرابع، يوجد أبناء للعُقْدة ( E)، تُمثِّلهم حالتان اثنتان، هما:
- الحالة( H)التي نتجت من تحريك الرقم (7) إلى اليمين.
- الحالة ( I)التي نتجت من تحريك الرقم(8) إلى اليسار.
مثال على آليََّة على خوارزمية البحث في العمق أوَّلًا:
اعتمادًا على الشكل ( 2- 2)، وافتراض( أ ) الحالة الهدف التي يُراد الوصول إليها من شجرة البحث السابقة هي الحالة ( I)، فإن خطوات البحث ستكون كما يأتي:
1. بَدْء بحث الخوارزمية من العُقْدة الابتدائية (الجذر)( A)، ثم مقارنتها بالحالة الهدف. وفي حال تبين أنَّها ليست الحالة الهدف، فإنَّه يتم الانتقال إلى العُقْدة التي تقع في أقصى اليسار، وهي العُقْدة ( B)، ثم يتم مقارنتها بالحالة الهدف.
2. البحث في أبناء العُقْدة ( B) إذا كانت عُقْدة ميتة (أيْ ليس لها أبناء)، ثم العودة إلى العُقْدة الجذر، وهي النقطة (A).
3. عند الوصول إلى العُقْدة( C) والعُقْدة( D)، يتم البحث في أقصى يسار العُقْدة ( C)، ثم تُقارَن بالحالة الهدف.
4. البحث في أبناء العُقْدة ( C)، وهم:( E, F, G )، بَدْءًا بأقصى اليسار.
5. استكشاف العُقْدة ( E)، ثم مقارنتها بالحالة الهدف.
6. البحث في أبناء العُقْدة (E).
7. استكشاف العُقْدة ( H) في أقصى اليسار، ثم مقارنتها بالحالة الهدف.
8. العُقْدة( H) عُقْدة ميتة؛ لذا تتم العودة إلى الأب العُقْدة( E) في محاولة لاستكشاف بقية الأبناء.
9. استكشاف العُقْدة ( I)، فيتبين أنَّها الحالة الهدف، عندئذٍ تتوقَّف عميلة البحث.
بعد توقُّف عميلة البحث، يُكتََب مسار البحث، بكتابة العُقَد التي تمَّ المرور بها من دون تكرار. وفي هذه الحالة، سيكون مسار البحث هو:
(A – B – C- E- H- I).
وفي حال طُلِب حساب تكلفة مسار الحَلِّ، بافتراض أن تكلفة كل حركة واحدة هي( 1)، فإنَّ إجمالي تكلفة هذا الحَلِّ سيكون( 7).
إجابة محتملة : = تكلفة الحل 31
إجابة محتملة: مسار البحث بحسب خوارزمية البحث في العمق أولا:( 10-9-8-7-6-5-4-3-2-1)
تكلفة الحل = 10
2. خوارزمية البحث في العرض أوَّلًا :(Breadth-First Search)
تعتمد خوارزمية البحث في العرض أوّلًا على استكشاف جميع العُقَد في كل مستوى من مستويات شجرة البحث، ثمَّ مقارنتها بالحالة الهدف قبل الانتقال إلى المستوى التالي.
استنادًا إلى الشكل ( 2- 1)، يُمكِن تطبيق خوارزمية البحث في العرض أوّلًا على النحو الآتي:
1. بَدْء الخوارزمية العمل من الحالة الابتدائية (A)، ثم مقارنة هذه الحالة بالحالة الهدف.
2. في حال لم تكن الحالة الابتدائية هي الحالة الهدف، يتم الانتقال إلى جميع العُقَد في المستوى الثاني من شجرة البحث، بَدْءًا بأقصى اليسار، حيث تُفحَص العُقْدة ( B) أوّلًا ، فيتبين أنَّها ليست الحالة الهدف، ليتم الانتقال إلى العُقْدة ( C) لتعرُّف إنْ كانت هي الحالة الهدف أم لا، ثم يتم الانتقال إلى العُقْدة ( D). وبذلك يكون قد تم الانتهاء من استكشاف جميع عُقَد المستوى الثاني.
3. في حال لم يوجد الحَلُّ في المستوى الثاني، فإنَّ الخوارزمية تنتقل إلى العمل في المستوى الثالث من شجرة البحث، حيث تُستكشَف فيه جميع العُقَد مُرتّبةً من اليسار إلى اليمين، بَدْءًا بالعُقْدة ( E)، ومرورًا بالعُقْدة ( F)، وانتهاءً بالعُقْدة( G)، فيتبين أنَّ جميع هذه العُقَد لا تُمثِّل
الحالة الهدف.
4. الانتقال إلى المستوى الرابع من شجرة البحث، والبَدْء باستكشاف العُقْدة ( H) وصولًا إلى العُقْدة ( I) التي يتبين أنَّها تُمثِّل الحالة الهدف، فتتوقَّف عميلة البحث. أنظر الشكل( 2- 4).
إذن، مسار البحث باستخدام خوارزمية البحث في العرض أوّلًا هو:
.A → B → C → D → E → F → G → H → I
تكلفة الحل = 46
إجابة محتملة :
1. A – B – D- I – J- E- K – L – M – C- F- S
2. A – B – C- D- E- F- G- H- I – J- K – L – M – S
3. تكلفة الحلِِّ لخوارزميََّة البحث في العمق أوَّلًا = 12
تكلفة الحلِِّ لخوارزميََّة البحث في العرض أوَّلًا =14
4. أ ) لا، لا يُمكن؛ لأنَّ البحث يبدأ دائمًا من عُقدة جذريَّة، وفي حال تغيُّر العُقدة الجذريَّة فإنَّ المسألة كاملة تتغيَّر.
4. ب) نعم، ستتغيَّر المسارات؛ لأنَّ خوارزمية البحث في العمق أوَّلًا تعتمد على المسار أقصى اليسار، وأما خوارزمية البحث في العرض أوَّلًا فتستخدم مستوى مستوى، ويتغير ترتيب المسار.
إجابة محتملة للحل:
ثانيًا: طرائق البحث المستنيرة(الاستدلالية)(Informed (Heuristic) Search Strategies)
تُعَدُّ طرائق البحث المستنيرة (الاستدلالية) واحدة من تقنيات البحث الذكي التي تُستخدَم فيها معرفة خاصة بالمشكلة تتجاوز تعريف المشكلة نفسها. تُستخدَم في الخوارزميات التي تتبع هذه الطرائق دالَّة تقدير تُسمّى ( Heuristic Function )، وتهدف إلى توجيه عميلة البحث بسرعة وفعّّالية نحو الحلول المُحتمَلة (المُمكِنة)، في ما يُعرَف بالبحث الأفضل أَوَّلًا . تُستخدَم هذه الخوارزميات في حال كانت المشكلة مُعقَّدة، أو كان حيِّز العمل كبير الحجم.
يُستخدَم في معظم هذه الخوارزميات دالَّةَ يُرمَز إليها بالرمز h (n):n ، حيث:
(n)h: التكلفة المُقدَّرة لأرخص مسار من الحالة (n) إلى الحالة المُُستهدََفة. وفي حال كانت العُقْدة (n) هي الحالة الهدف، فإنَّ: h(n)= 0
استخدامات خوارزميات البحث المستنير (الاستدلالي):
يُستخدَم هذا النوع من خوارزميات البحث في ما يأتي:
1. الذكاء الاصطناعي: تُستخدَم خوارزميات البحث المستنير (الاستدلالي) في الروبوتات والألعاب.
2. تحليل البيانات: تُستخدَم خوارزميات البحث المستنير(الاستدلالي) عند الحاجة إلى تحليل البيانات لاستخراج الأنماط.
3. البحث في الرسوم البيانية (Graphs)
أنواع البحث (بالأفضلية) (Heuristic Search Techniques):
يوجد العديد من خوارزميات البحث بالأفضلية، ولكل منها مزايا وعيوب، وهذه أبرزها:
1. خوارزمية البحث الجشع (Greedy Best-First Search: GBFS):
تختار هذه الخوارزمية في كل خطوة العُقْدة ذات أقل قيمة لدالَّة التقدير( Heuristic Function ) من دون اعتبار للطريق الكلي.
مثال:
إذا أراد وليد الانتقال من مدينة عمّان إلى مدينة العقبة، مرورًا ببعض المدن الأردنية للاستراحة، فإنَّه سيختار في كل مَرَّة أقرب مدينة إلى المدينة التي يوجد فيها، وهكذا حتّى يصل إلى مدينة العقبة.
- هل تُفْضي خوارزمية البحث الجشع إلى المسار الأفضل دائمًا؟ لا، لأنَّها لا تأخذ في الاعتبار المسار الكامل أو التكلفة الإجماليَّة، وقد تقع في شَرَك المسارات الخاطئة، ومن الممكن أيضًا أنْ تقود إلى عُقدة ميتة لا يمكنها أنْ تقود إلى أيِّ حلٍّ
2. خوارزمية البحث بالشبكة العصبية (Neural Network-Based Heuristic Search):
تستخدم هذه الخوارزمية الشبكات العصبية ( Neural Networks ) لتحديد أفضل الحركات أو القرارات؛ إذ يتمُّ تدريب الشبكة على مجموعات ضخمة من البيانات للتنبُّؤ بأفضل دالَّة تقدير. يمتاز هذا النوع من خوارزميات البحث بالقدرة على حَل مشكلات مُعقَّدة بدِقَّة عالية، بحيث تتحسَّن فعّاليتها بمرور الوقت في ظلِّ زيادة التدريب والبيانات. تُستخدَم خوارزمية البحث بالشبكة العصبية في ألعاب الذكاء الاصطناعي، وأنظمة التوصية، والتحليل التنبُّؤي.
3. خوارزمية البحث باستخدام المستعمرات النملية (Ant Colony Optimization: ACO):
تعتمد هذه الخوارزمية في عملها على محاكاة سلوك النمل في مستعمرات النمل عند بحثه عن الطعام؛ إذ يترك النمل الباحث عن الطعام أثرًا كيميائيا(فيرمونات) يدلُّ بقية النمل على أفضل المسارات التي يُمكِن اتِّباعها للوصول إلى الغذاء. يُستخدَم هذا النوع من خوارزميات
البحث عند الحاجة إلى إيجاد مسارات قصيرة ومُتعدِّدة كما في شبكات النقل والمواصلات.
4. خوارزمية البحث الشامل بالأفضلية ( A* Search ):
يجمع هذا النوع من البحث بين البحث الجشع والبحث باستخدام تكلفة الطريق الفعلية ( Actual Cost)؛ للتقليل من إجمالي تكلفة الحَلِّ المُقدَّرة. ومن ثَم تُعَدُّ هذه الخوارزمية واحدة من أكثر الخوارزميات استخدامًا وكفاءة في إيجاد الحلول المُثلى. يُستخدَم هذا النوع من خوارزميات البحث في أنظمة المِلاحة ( GPS )، وألعاب حَلِّ الألغاز، وأنظمة الجدولة (مثل جدولة المواعيد الطبي)، وإدارة الرحلات الجوية، والبحث في البيانات الضخمة.
5. خوارزمية البحث التكراري بالأفضلية ( Iterative Deepening A*: IDA):
يُعَدُّ هذا النوع من خوارزميات البحث نسخة مُحسَّنة من خوارزمية البحث الشامل بالأفضلية (A* Search )؛ إذ تعمل خوارزمية البحث التكراري بالأفضلية على تحديد حَدٍّ مُعين للبحث يتغير تدريجي؛ ما يؤدّي إلى استهلاك ذاكرة أقل مقارنةً بخوارزمية البحث الشامل بالأفضلية (A* Search ) الأصيلة.
| الإجابة : |
البحث الشامل بالأفضلية (A* Search) | خوارزميََّة البحث التكرار يِِّ بالأفضلية(Iterative Deepening A*:IDA) |
| آليَّة العمل | تجمع بين البحث الجشع والبحث باستخدام تكلفة الطريق الفعليََّة. | نسخة محسَّنة من خوارزميَّة البحث الشامل بالأفضليَّة، حيث تعمل على تحديد حد معيَّن للبحث يتغيَّر تدريجي. |
| التكلفة | تستهلك ذاكرة أكثر. | تستهلك ذاكرة أقل. |
| الاستخدامات | أنظمة الملاحة GPS ، وألعاب حلِّ الألغاز، وأنظمة الجدولة،وإدارة الرحلات الجويَّة، والبحث في البيانات الضخمة. | تُستخدم في التطبيقات ذات الموارد المحدودة، مثل الأجهزة المدمجة، والألعاب المعقَّدة. |
المسؤولية الرقمية: ألجأ دائمًا إلى الحلول التي تعمل على تقليل استهلاك الذاكرة، وتستغرق وقتًا أقل في التنفيذ. كذلك أبني خوارزمية خاصة أُنظمِّ بها وقتي، وأستخدمها في تخطيط حياتي جيدا للوصول إلى أهدافي، وأبتعد عن هدر الوقت.
الإبداع الرقمي: أستخدم الأفكار الإبداعية في تمثيل المسائل الحياتية، واختيار خوارزميات البحث المناسبة لكلٍّ منها.
