مدونة نانو تك
  • الرئيسية
  • التصنيفات
    • أبحاث علمية تقنية
    • أخبار التكنولوجيا والتقنية
    • أخبار لغات البرمجة وأطر العمل
    • أفكار مشاريع تخرج IT
    • مقالات برمجية وتقنية
    • مواضيع تقنية
  • الاخبار
  • الصور
  • الفيديوهات
  • للتواصل
مدونة نانو تك
  • الرئيسية
  • التصنيفات
    • أبحاث علمية تقنية
    • أخبار التكنولوجيا والتقنية
    • أخبار لغات البرمجة وأطر العمل
    • أفكار مشاريع تخرج IT
    • مقالات برمجية وتقنية
    • مواضيع تقنية
  • الاخبار
  • الصور
  • الفيديوهات
  • للتواصل
تطبيق_App_Food من نانوسوفت

التصنيفات

  • مواضيع تقنية 65
  • أفكار مشاريع تخرج IT 26
  • مقالات برمجية وتقنية 114
  • أخبار التكنولوجيا والتقنية 66
  • أخبار لغات البرمجة وأطر العمل 26
  • أبحاث علمية تقنية 20

الهاشتاجات

ابحاث علمية تقنية 19 افكار مشاريع تخرج تقنية 33 التقنية والتكنولوجياء 155 مشاريع تقنية 7

البومات الصور

89 صور
مارس 13, 2025
21 صور
سبتمبر 10, 2024
17 صور
مارس 16, 2023

فيديوهات

تعلم الكتابة بسرعة على الحاسوب من خلال هذا الموقع واستمتع باللعب
تعلم الكتابة بسرعة على الحاسوب من خلال هذا الموقع واستمتع باللعب
تعلم الكتابة بسرعة على الحاسوب من خلال هذا الموقع واستمتع باللعب https://zty.pe/ الموقع حلو ج...
الفيديوهات
2023/08/04
ألعاب مجانية لتعلم البرمجة الجزء الثاني
ألعاب مجانية لتعلم البرمجة الجزء الثاني
ألعاب مجانية لتعلم البرمجة الجزء الثاني
الفيديوهات
2023/08/04
ألعاب مجانية لتعلم البرمجة الجزء الاول
ألعاب مجانية لتعلم البرمجة الجزء الاول
ألعاب مجانية لتعلم البرمجة الجزء الاول free games to learn programming parrt 1
الفيديوهات
2023/08/04
مواقع مفيده لتعليم الاطفال البرمجه
مواقع مفيده لتعليم الاطفال البرمجه
مواقع مفيده لتعليم الاطفال البرمجه
الفيديوهات
2023/08/04
ماهي ال NFTs.
ماهي ال NFTs.
هى اهتصار ل Non Fungible Tokens او الرموز الغير قابلة للاستبدال وهى الرموز التي لاتماثلها أي رموز أخ...
الفيديوهات
2023/08/04
نصائح لتصبح فريلانسر ناجح
نصائح لتصبح فريلانسر ناجح
الفيديوهات
2023/08/04
تعرف معنا على اهم مهارات العمل الحر
تعرف معنا على اهم مهارات العمل الحر
الفيديوهات
2023/08/04
ماهو العمل الحر
ماهو العمل الحر
الفيديوهات
2023/08/04
أشياء يجب أن تعرفها عن العمل الحر
أشياء يجب أن تعرفها عن العمل الحر
الفيديوهات
2023/08/04
مشاكل وعيوب العمل الحر
مشاكل وعيوب العمل الحر
الفيديوهات
2023/08/04
كيف تصبح فريلانسر
كيف تصبح فريلانسر
الفيديوهات
2023/08/04

الهاشتاجات

لايوجد بيانات لعرضها

روابط ذات صله

    لايوجد بيانات لعرضها

Posted in أبحاث علمية تقنية, مواضيع تقنية on أغسطس 30, 2024

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

   ماهي خوارزميات 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



x

[closed]

[open]

S

[ ]

[S]

A

[S]

[A,B]

B

[S,A]

[B, G]

G

[S,A,B]

[G,C,D]


[S,A,B,G]

Stop











- الطريق الأقصر: 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  أي احتمالية اختيار هذا الكروموسوم

Expected count

pi

Fitness Fj f(x) = x ^ 2

X value

Initial population

String No

4 * 0.14 = 0.56

169 / 1170 = 0.14

169

13

01101

1

1.97

0.49

576

24

11000

2

0.22

0.06

64

8

01000

3

1.23

0.31

361

19

10011

4

4

1

1170



Sum

1

0.25

293



 Avg

1.97

0.49

576



Max


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

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

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

مثال:



Fitness f(x) = x^2

X value

Offspring after crossover

Crossover point


String No

144

12

01100

4

0110 | 1

1

625

25

11001

4

1100 | 0

2

729

27

11011

2

11 | 000

2

256

16

10000

2

10 | 011

4

1254





Sum

439





Avg

729





Max



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

Fitness f(x) = x ^ 2

X value

Offspring after mutation

Offspring after crossover

String No

676

26

 11100

01100

1

625

25

11001

11001

2

729

27

11011

11011

2

2354

18

10100

10000

4

5885




Sum

729




Avg





Max


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


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




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

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

أغسطس 30, 2024 in أبحاث علمية تقنية, مواضيع تقنية
Tags # ابحاث علمية تقنية

Related posts

خرائط جوجل وطريقة عملها ومميزاتها google maps منصة Force واستخداماتها واهميتها أفضل خدمات مشاركة الملفات السحابية لعام 2024 A Comparison between 10 Data Mining Tools افكار مشاريع تخرج شبكات 2024 Top Tools in Academic Mining يتحدى مجتمع JavaScript علامة JavaScript التجارية الخاصة بشركة Oracle Google Workspaceأدوات جوجل للتعاون والإنتاجية coogle word مشاريع تخرج علوم حاسوب وتقنية معلومات جاهزه

  • القائمة
  • الرئيسية
  • التصنيفات
    أبحاث علمية تقنية أخبار التكنولوجيا والتقنية أخبار لغات البرمجة وأطر العمل أفكار مشاريع تخرج IT مقالات برمجية وتقنية مواضيع تقنية
  • الاخبار
  • الصور
  • الفيديوهات
  • للتواصل

يمكنكم التواصل معنا عن طريق :

العنوان
Yemen IBB
الهاتف +967770529482
967770177866+
البريد info@nano2soft.com

كما يمكنكم زيارتنا على مواقع التواصل التالية

مدونة نانو تك © 2020 -
تطوير Nano 2 Soft
الهاتف 00967770529482
البريد info@nano2soft.com website https://nano2soft.com