ماهي خوارزميات BFS  و  DFS و DA    

تعتبر خوارزميات BFS (Breadth-First Search) و DFS (Depth-First Search) من أهم الخوارزميات المستخدمة في تجوّل الرسوم البيانية (Graph Traversal). هذه الخوارزميات تلعب دورًا حاسمًا في حل العديد من المشكلات في علوم الحاسوب، مثل:

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

خوارزمية البحث بالعرض أولاً (BFS)

• الفكرة الأساسية: تبدأ BFS من عقدة جذرية وتزور جميع الجيران المباشرين لهذه العقدة قبل الانتقال إلى الجيران المباشرين للعقد التي تم زيارتها.
• الاستخدام: تستخدم BFS بشكل شائع للعثور على أقصر مسار في رسم بياني غير موجه وغير مرجح.
• البيانات الهيكلية: تستخدم قائمة انتظار (Queue) لتخزين العقد التي يجب زيارتها.

خوارزمية البحث بالعمق أولاً (DFS)

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

خوارزمية Dijkstra (DA)

• الفكرة الأساسية: تعتبر خوارزمية Dijkstra امتدادًا لخوارزمية BFS، ولكنها تستخدم لتحديد أقصر مسار في رسم بياني مرجح.
• الاستخدام: تستخدم Dijkstra على نطاق واسع في العديد من التطبيقات، مثل توجيه الشبكات، وتخطيط المسارات، وتحليل البيانات.
• البيانات الهيكلية: تستخدم قائمة أولوية (Priority Queue) لتخزين العقد بناءً على المسافة التقديرية من العقدة المصدر.

         خوارزمية BFS              

• خوارزمية ال BFS: 
• تقوم فكرتها على أساس المراحل levels ولديها نقطة بداية ونقطة نهاية (الهدف)، يتم حلها بترتيب الأبجدية أو ذات العقد الأكثر
• خوارزمية البحث بالعرض أولاً (Breadth-First Search أو BFS اختصارًا) هي إحدى الخوارزميات الأساسية في علم الحاسوب، وتستخدم لاستكشاف وتنقيب الرسوم البيانية (الغراف). تعمل هذه الخوارزمية على استكشاف جميع الجيران المباشرين لعُقدة معينة قبل الانتقال إلى الجيران الأبعد.

• كيف تعمل BFS؟
• البداية من عُقدة: تبدأ الخوارزمية من عُقدة محددة في الرسم البياني.
• زيارة الجيران: يتم زيارة جميع الجيران المباشرين لهذه العُقدة وإضافتهم إلى قائمة الانتظار (عادةً ما تكون قائمة).
• الانتقال إلى العُقدة التالية: يتم إزالة العُقدة الأولى من قائمة الانتظار وزيارة جميع جيرانها غير المستكشفين وإضافتهم إلى القائمة.
• التكرار: تتكرر هذه العملية حتى يتم زيارة جميع العُقد التي يمكن الوصول إليها من العُقدة البداية.

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

مثال باستخدام طريقة ذات العقد الأكثر:

Visited Nodes:

• S
• A
• B
• C
• D
• E
• F
• G

مثال2:

وليكن الهدف H

مسار الحل: هو مجموعة النقاط المتتالية التي توصل الجذر بالهدف

- إذا مسار الحل: A B F C E G I D H

• مثال باستخدام ترتيب الابجدية:
• وليكن الهدف G

- الطريق الأقصر: S è A è B è G      

• الكود الخاص ب BFS:

        خوارزمية  DFS            

خوارزمية ال BFS: 

• تستخدم لعرض عدد المكونات المتصلة
• معرفة طبيعة الاتصال بين كل عقدة وأخرى
• إيجاد ال strongly connected components of a graph
• حل مشاكل لبعض الألعاب مثل لعلة sudoku puzzles
• الترتيب بناء على أولويات (جدولة مجموعة من المهام أي توزيع المهام بالترتيب الصحيح)
• تعمل هذه الخوارزمية على استكشاف أقصى عمق ممكن في فرع واحد قبل الانتقال إلى فرع آخر.

كيف تعمل ال BFS: 

• البداية من عُقدة: تبدأ الخوارزمية من عُقدة محددة في الرسم البياني.
• اختيار فرع: يتم اختيار أحد الجيران المباشرين لهذه العُقدة والانتقال إليه.
• الاستكشاف في العمق: تستمر الخوارزمية في الانتقال إلى الجيران المباشرين للعُقدة الحالية حتى تصل إلى عُقدة لا يوجد لها جيران غير مستكشفين (ورقة).
• التراجع: عند الوصول إلى ورقة، تعود الخوارزمية إلى العُقدة السابقة وتختار جارًا آخر لم يتم زيارته بعد.
• التكرار: تتكرر هذه العملية حتى يتم زيارة جميع العُقد التي يمكن الوصول إليها من العُقدة البداية.

- يتم تطبيقه على: الجراف الموجه والغير موجه

- في خوارزميات البحث نحاول المرور على كل العناصر

 - نمسك vertex معين مثلا نبدأ في vertex A

- في حال اخترنا A انا مخير اذهب الى C او E او D ومثلا نلتزم بالترتيب الابجدي ونذهب من ال C الى E وبعدها نذهب الى F في هذه الحالة واجهنا طريق مسدود في هذه الحالة نقوم بعمل تراجع backtrack الى vertex التي قبلها ، هل يوجد مسار استطيع الذهاب اليه من خلال E ؟ لا نقوم بعمل تراجع الى العقدة التي أتيت منها سابقا وهي ال C ، نذهب من ال C الى G واجهنا مسار مسدود نعمل تراجع ل C هنا لا يوجد مسار جديد اذهب اليه أقوم بعمل تراجع الى العقدة A

- يظل يمشي بمسار معين ولن يخرج من هذا المسار الا إذا كان المسار مسدود أو مغلق ( أي يظل يمشي بالعمق الى أن يغلق المسار وبعدها أعمل تراجع وابحث حلول أخرى )

- نبحث عن مسار اخر ç D اصبحنا في مسار مسدود نعمل تراجع ل A وفي هذه الحالة قمنا بسلك جميع ال

Vertices أي قمنا بعمل لهم visited

مثال:

• نعرف مكدس وحجمه يكون بعدد ال vertices

• نختار أي نقطة ونبدأ نعمل لها push لهذا المكدس
• نعمل زيارة للمسار المحدد واظل اسير فيه الى ان يغلق المسار او ما يسمى dead end أقوم بعمل تراجع
• اكرر الخطوة 3 طالما لا يوجد لدي عقدة جديدة تم زيارتها من ال top
• إذا وصلت الى dead end وليس لدي vertex اعمل له visit أقوم بعمل له تراجع وامسح ال vertex من المكدس pop
• اكرر الخطوة 3، 4، 5 طالما المكدس غير فارغ
• عندما يصبح المكدس فارغ اخرج من النتيجة النهائية التي spanning tree مع مسح جميع الحواف edges التي لا احتاجها الى ان احصل على المسار الذي اريده
  
• 
  الحل:
• نبدأ من عند العقدة A ونعمل لها إضافة داخل المكدس push
• نعتمد ترتيب الحروف الهجائية ونذهب الى الحرف الذي يليه وهو ال B ونعمل لها push لداخل المكدس ونذهب الى C ونضيفه الى المكدس ، نذهب الى E ونضيفه الى المكدس، لدي خيارين الان اما F او D باقي ال vertices تم زيارتها لا أقوم بزيارتها مرة أخرى، نذهب الى D ونعمل له إضافة الى المكدس والان نعمل له تراجع لان الطريق مغلق وينمسح ال D من المكدس ونعود الى E ، نذهب الى F لان بقية المسارات الأخرى مغلقة ونضيف ال F الى المكدس ونذهب الى G ونضيفه الى المكدس ، الان اصبحنا في مسار مغلق نقوم بعمل تراجع ويتم مسح ال G من المكدس والان رجعنا ل F وهو مساراته كذلك مغلقة نعمل له أيضا تراجع ونحذفه من المكدس ويصبح تم زيارته كليا، والان وقفنا عند ال E نعمل له تراجع ونحذفه من المكدس، الان اصبحنا في ال C المسارات كذلك مغلقة نعمل له تراجع ونحذفه من المكدس وهكذا الى ان نصل الى A ونحذفه من المكدس وبذلك يصبح المكدس فارغ، وبالنهاية نبحث عن الحواف التي لم أزورها وأقوم بحذفها وهذا الشكل النهائي

DFS-Spanning tress

• يطلق على الحواف المحذوفة Back edges
• ممكن رسم الحواف بشكل منقط لحفظ المكان الذي كانوا فيه ويشير على ان هذه الحواف تم الاستغناء عنها

مثال اخر:

• وليكن الهدف H

- مسار الحل باستخدام هذه الخوارزمية: A B C D E F G H

الكود الخاص ب DFS:

      خوارزمية ال GA:         

1. الكروموسوم: مجموعة من الجينات
2. هذا الشكل عبارة عن كروموسوم
3. وكل بت هو جيني ويتم تمثيله كثنائي binary
4. population: مجموعة من الكروموسومات
5. كل string له كروموسوم ومجموعة من الكروموسوم له population
6.  Fitness function: يعمل تقييم لل population

خطوات ال GA: 

• نعمل Initial population
• نحسب ال Fitness
• نختار الإباء Selection
•  Crossover
• Mutation
• نرجع نحسب ال Fitness
• هل حقق عندي التابع المطلوب؟ إذا تحقق يعني أن ال Individuals هم الأنسب، إذا لم يتحقق نعيد من الخطوة 3

 
Genetic operators: 

• Selection operator
• Crossover
• Mutation

- selection: هي عملية اختيار افراد عن طريقهم يتولد النسل (اختيار اباء لتوليد النسل)

- الإباء يتم تقييمهم عن طريق ال fitness

مثال: 

• Where x in interval [0,31] Maximize the function f(x) = x ^ 2
• نعمل  Initial population بشكل عشوائي
• 01101
• 11000
• 01000
• 10011

نحسب ال Fitness:

• Decode into an integer
• 01101 è 13
• 11000 è 24
• 01000 è 8 
• 10011 è 19

• Evaluate fitness, f(x) = x ^ 2
• 13 è 169
• 24 è 576
• 8 è 64   
• 19 è 361
• 
  

نختار الإباء selection:

• Select parent (2 individuals) based on their fitness in p:
• pi = fi / sum of strings Fj
• يتم تحديد الإباء بناء على هذا القانون
• fi: fitness for string I in population (fitness for chromosome)
• pi: prob. of string I being selected  أي احتمالية اختيار هذا الكروموسوم

• اعلى fitness هو string رقم 2
• اقل fitness هو string رقم 3
• يعني هذا ان ال 2 هي افضل fitness لأنها أعلى قيمة ونختارها كأب (Parent) لتوليد النسل الجديد
• 
  

crossover: يكون لدي 2 اباء نختارهم وبعدها نريد من هؤلاء الأبين يولدوا نسل

• نختار نقطة بشكل عشوائي one point crossover ونستبدل ما بعد النقطة بين ال 2 اباء 

مثال:

mutation: نختارالطفرة أي نختار أي بت بشكل عشوائي ونستبدله بقيمة ، الأعلى قيمة لانعمل لها mutation

• نلاحظ انه حصل تحسين لل fitness في كل مرة ، نوقف الحل هنا لأننا قمنا بعمل تحسين لل fitness function

الكود الخاص ب GA:

تم اعداد  هذا البحث بواسطة المهندسة /  سلمى العفيف   

لطلب البحث جاهز على ملف وورد يرجى مراسلتنا واتساب من خلال الضغط اضغط هنا للمراسلة واتساب