خوارزميات البحث PDF

# الجامعة الوطنية الخاصة ## كلية الهندسة ### قسم هندسة الحاسوب – الاتصالات #### المقرر: مبادئ الخوارزميات وبنى المعطيات ##### المحاضرة: الثانية ###### Dr. Mohammed AL-Mohammed ## Chapter 2 ### خوارزميات البحث ### Search Algorithms ## مقدمة تُعتبر خوارزمية البحث ركنا أساسيا من أركان علم الخوارزميات...

# الجامعة الوطنية الخاصة ## كلية الهندسة ### قسم هندسة الحاسوب – الاتصالات #### المقرر: مبادئ الخوارزميات وبنى المعطيات ##### المحاضرة: الثانية ###### Dr. Mohammed AL-Mohammed ## Chapter 2 ### خوارزميات البحث ### Search Algorithms ## مقدمة تُعتبر خوارزمية البحث ركنا أساسيا من أركان علم الخوارزميات و تتخذ هذه الخوارزمية عدة أشكال، من أبسطها البحث عن عدد في مصفوفة مُحددة الحجم و يزداد الأمر تعقيدا عند الانتقال إلى البحث عن كلمة داخل نص، تماما كما ترى في محررات النصوص العادية والتي تحتوي على خاصية Find & Replace ، حيث أن أغلب المحررات الحالية تستخدم خوارزميه بحث تسمى Boyer-Moore searching التي تُعد تقريبا من أسرع الخوارزميات في مجال البحث. هناك أيضا بحث من نوع آخر، فماذا لو كانت لدينا مجموعة حروف و نريد إيجاد جميع الكلمات التي تبدأ بهذه الحروف ؟؟ عادة ما يُسمى هذا النوع من الخوارزميات ب prefix searching و لهذا النوع تطبيقات كثيرة خصوصا في محركات البحث و القواميس و المتصفحات التي تستخدم هذه الخوارزمية عند كتابتك لموقع يبدأ بحرف كنت قد زرته سابقا. ## مقدمة: ### خوارزميات البحث البحث عن المعلومات في مصدر ما وترتيبها تعتبر من أبرز و أهم العمليات التي تحتاج لها صناعة البرمجيات للأنظمة المختلفة، لهذا يعكف الباحثون في مجال علوم الحاسوب على دراسة الخوارزميات الأفضل للبحث وطرق ترتيب وفرز البيانات. سنناقش أكثر خوارزميات البحث والترتيب شهرةً واستخداما مع تراكيب البيانات المشهور استخدامها. إن خوارزميتا البحث search والترتيب sort هما من أهم الخوارزميات اللازمة في مجال علوم الحاسب لأنه لا يخلو أي عمل لـ computer system منهما. ولكن هنالك مشكلة كبيرة أن هاتان الخوارزميتان هما ركن أساسي من التعقيد الزمني للبرامج إذا استطعنا تقليل تعقيدهما الزمني = يقل زمن تنفيذ البرنامج ولو بشكل بسيط جداً. سنقوم بدراسة بعض خوارزميات البحث وكيف حسنها المبرمجون لجعلها أقل تكلفة ثم سنكتبها على شكل كود بلغة + + C (هذا لا يعني أنه لا يمكن كتابتها بطريقة أخرى كالمخططات التدفقية flow chart ثم سنقوم بعمل تتبع لها. ## مسألة البحث: بصيغة أخرى: وهي عملية تبحث عن عنصر معين في مجموعة معطيات (بيانات). هي العملية التي تبحث عن قيمة معينة تسمى مفتاح البحث key في مجموعة معطيات معينة (وفق بنية معطيات )Data structure معينة سوف نعتمد الآن بنية المعلومات المصفوفة والتي هي مجموعة من العناصر المتتالية في الذاكرة (عنوان العنصر الأول يليه عنوان العنصر الثاني ... وهكذا). حجمها ثابت حتى نهاية البرنامج، يتم التحكم بها عن طريق Index (دليل المصفوفة ) الذي نمر به على كافة قيم المصفوفة. على المصفوفة قيد وهو أن تكون جميع بياناتها من نفس النوع قد يكون لبنية معطيات أخرى نفس الخوارزمية أو قد تشابهها مع قليل من التعديل. وهذا ما يقودنا إلى Data Base وهي مجموعة من البيانات الضخمة. نربطها مع بعضها ونجمعها في جدول Data Base لها. ## خوارزميات البحث ### أولاً : البحث الخطي linear Search أسهل أنواع البحث الخطي هو البحث عن عنصر داخل مصفوفة وذلك بأن نقارن كل عنصر من المصفوفة مع العنصر المراد البحث عنه . مقارنة القيمة المطلوبة مع كافة العناصر عنصرا عنصر. عند إيجاد القيمة المطلوبة تتوقف المقارنات. **مثال:** لدينا المصفوفة التالية فرضاً ونريد أن نبحث عن عنصر معين فيها: Index 0 1 2 3 4 5 Value 3 6 1 1 1 9 8 المصفوفة هي بنية تحتوي على مجموعة من البنى ذات النمط نفسه، وحجمها ثابت. نستطيع الوصول لأي خانة من خانات المصفوفة عن طريق ال index ، مثل في المصفوفة السابقة لتكن [a[n حيث n يمثل حجم المصفوفة و هو في مثالنا 6 (يعني عدد العناصر) نستطيع الوصول إلى الرقم 11 عن طريق خانته 3 أي ]3[ = 11 دائماً حجم المصفوفة = اخر index + 1 <start_of_image> Diagrams: - An array with index 0 1 2 3 4 5 and array values 2 5 7 9 34 55 56 66 79 80 81 88 90 99. An arrow is pointing to the value 80 with the text "Wanted = 80" above it. - A table with index 0 1 2 3 4 5 and values 3 6 1 1 1 9 8. ### الخوارزمية بلغة + + C: ```c++ 1.int linearSearch (int a[],int n,int target) 2.{ 3. int i; 4.for(i=0;i<n;i++) 5.if(a[i]==target)//key comparison 6. return i; 7. return -1;//use -1 to indicate failure 8.} ``` ### كمثال للتوضيح لنفترض الجدول الآتي : 41 5 -1 18 7 62 39 0 -6 28 إذا قمنا بتطبيق خوارزمية البحث الخطي على الجدول فسنمر بالخطوات التالية : 41 5 -1 18 7 62 39 0 -6 28 41 5 -1 18 7 62 39 0 -6 28 41 5 -1 18 7 62 39 0 -6 28 41 5 -1 18 7 62 39 0 -6 28 41 5 -1 18 7 62 39 0 -6 28 41 5 -1 18 7 62 39 0 -6 28 41 5 -1 18 7 62 39 0 -6 28 41 5 -1 18 7 62 39 0 -6 28 41 5 -1 18 7 62 39 0 -6 28 ### حالات التعقيد: أفضل حالة: العنصر المراد البحث عنه يقع في الخانة الأولى وبالتالي سيكون عدد العمليات عملية واحدة فقط. أسوأ حالة: العنصر المراد البحث عنه غير موجود ضمن المصفوفة فيكون عدد العمليات يساوي عدد عناصر المصفوفة. حالة متوسطة : نفترض فيها أن هناك احتمالات متساوية لوجود الحد في أي خانة من خانات المصفوفة أي أن احتمال وجود الـ target في الخانة الأولى مثلاً يساوي احتمال وجوده في الخانة الخامسة ... إلخ فإذا كان الاحتمال الكلي = 1 فإن احتمال الحد الواحد هو $$\frac{1}{n}$$. وبجمع الاحتمالات: $$\frac{1}{n}$$ + $$\frac{1}{n}$$(2) + $$\frac{1}{n}$$(3) + ... + $$\frac{1}{n}$$(n) = $$\frac{1}{n}$$(1 + 2 + 3 + ... + n) **وبجمع بالطريقة:** $$\sum_{i=1}^{n}$$ $i$ = 1 + 2 + 3 + .... N = $$\frac{N(N+1)}{2}$$. **وتصبح حسب العلاقة** $$\frac{1}{n}$$($$\frac{n(n+1)}{2}$$)= $$\frac{n+1}{2}$$. وهو الحالة المتوسطة. Diagrams: - A linear graph with y axis labeled 'f(n)' and x as 'n', with 2 lines. The first is a straight line from the origin, passing through (n,n), labeled 'n'. The second is a curve that is going up more slowly than the straight line, labeled 'log2 n'. ### ملاحظة أفضل حالة عندما يكون زمن التنفيذ أقصر ما يمكن وبالتالي عندما 1 = n" ؟؟؟؟!! أفضل حالة هي توزع القيم لمجموعة معطيات حجمها n الذي يعطي أقل كلفة (أي أقصر زمن تنفيذ). أسوأ حالة هي توزع القيم لمجموعة معطيات حجمها n الذي يعطي أكبر تكلفة (أي أطول زمن تنفيذ). إذا فأفضل حالة تعتمد على الحد الذي يحتاج أقل وقت تنفيذ بين كل الحدود. ### ملاحظة مهمة جداً: تذكير: نمط bool هو نمط منطقي •0/1 )True/false) يعيد القيم كما ذكرنا يمكن كتابة الخوارزمية بأكثر من شكل والشكل السابق أحدها يعد الشكل السابق تحسين الخوارزمية قديمة تستخدم النمط bool. ### الخوارزمية هي: ```c++ 1.bool linersearch (int a[],int n,int key) 2.{ 3.for(int i=0;i<n;i++) 4.{ 5.if(a[i]==key) 6. Return true; 7.} 8.else 9.return false;} ``` يمكننا التعديل على الخوارزمية حسب الطلب فمن الممكن أن يطلب منا إيجاد قيمة المفتاح أو مكانه (index) أو عدد مرات تكراره في المصفوفة، وهذه تصبح طلبات برمجية من المعلومات السابقة لا علاقة لها بالخوارزميات. ## ثانيا": البحث الثنائي Binary Search . تعتمد خوارزمية البحث الثنائي على التعامل مع مجموعة من العناصر المرتبة تصاعدياً أو تنازلياً سواءً كانت أرقاماً أو نصوصاً. . و لأن العناصر مرتبة فيمكن الاعتماد على هذه الحقيقة في تجاهل مجموعة من العناصر أو اعتمادها من خلال تقسيم العناصر إلى نصفين فيتم تجاهل أحدهما و اعتماد الأخرى بناء على مقارنة هل العنصر الوسط أكبر من العنصر المراد أم أصغر أم يساويه؟ . و يتم تكرار ذلك حتى الوصول إلى النتيجة النهائية و التي تتمثل في أنَّ العنصر موجود في موقع ما محدد أو غير موجود. ### البحث الثنائي Binary Search "تعتمد الخوارزمية بشكل رئيسي على فكرة تقسيم العمل أو تقسيم المشكلة ليسهل حلها ستمر هذه الفكرة بشكل مفصل أكبر في العودية" أما إذا كانت مصفوفة طلاب (غرض )object) = يجب أن نعرف أكبر وأصغر بطريقة مختلفة مثلاً: طالب ما > طالب آخر > معدل الطالب الأكبر أفضل كما أنه ناجح في كل المواد (كل المواد > 60) سنفترض ( فرضاً ولكن يمكن أن ترتب بأي شكل من أجل البحث الثنائي أن المصفوفة مرتبة تصاعدياً من الأصغر إلى الأكبر) وفق هذا المخطط: Diagrams: - A line with 0, m, n-1 markings, with arrows pointing to "First" , "Middle" and "Last" elements. ### ملاحظة: من أجل البحث الثنائي يجب أن تكون القائمة مرتبة تصاعدياً أو تنازلياً (وفق ترتيب معين سواء أكانت أرقاماً أم أحرفاً ..... • لهذا الترتيب التصاعدي خاصتان - كل العناصر على يمين midle أكبر منه. - كل العناصر على يسار midle أصغر منه. فإذا كان لدينا مفتاح Key ما سنقارن بين Key و midle = فإذا كان مساوياً له فإننا قد نجحنا وإذا كان أصغر منه سنلغي المجموعة اليمنى وإذا كان أكبر منه - سنلغي المجموعة اليسرى. من خصائص هذه الخوارزمية أننا ومنذ الخطوة الأولى إما أن نجد العنصر في الوسط أو أن نختصر نصف المجموعة قللنا عدد العمليات بتقليل البيانات Data لنفترض أننا وجدنا أن midle > key = سنأخذ النصف اليساري فقط: Diagrams: - A line with 2 markings '0' and 'm*'. - An arrow pointing to the 'm-1' marking. ### ملاحظة: سنستمر بتقسيم المصفوفة حتى يصبح حجمها 1 = نقارن للمرة الأخيرة فإما نجاح أو فشل كلي Base case. ## الترتيب و البحث مع Array List !! • يمتلك صنف ArrayList العديد من الدوال التي سبق الحديث عنها، و من هذه .Binary Serach و Sort الدوال دالتي . تقوم دالة Sort بترتيب المصفوفة من خلال المقارنة الافتراضية (التساوي) أو من خلال مقارنة تعطيها أنت للدالة. • تقوم دالة Binary Search بالبحث ضمن المصفوفة عن عنصر ما باستخدام خوارزمية البحث الثنائي و تعيد رقم موضعه إن كان موجودا و إلا تعيد قيمة سالبة، حيث تقوم الدالة ذاتها بترتيب العناصر ترتيبا تصاعديا ثم تتطبق البحث الثنائي. Diagrams: - An array with values -9 -5 3 4 8 10 15 17 21 22 30 31 32 40 41 43 60 and with the following descriptions for each iteration: - 1st iteration: 'Lo' at index 0, 'Mid' at index 8 and 'hi' at index 16. - 2nd iteration:'Lo' at index 0, 'Mid' at index 4 and 'hi' at index 16. - 3rd iteration: 'Lo' at index 0, 'Mid' at index 8 and 'hi' at index 16. - 4th iteration: 'Lo' at index 9, 'Mid' at index 10 and 'hi' at index 11. ### الخوارزمية بلغة + + C ```c++ 1.int binarySearch(const int arr[],int arrSize,const int key) 2. { int Lo=0,mid,hi=arrSize-1; while (Lo<=hi) 3. 4. 5. { 6. mid=(Lo+hi)/2; 7. if (key<arr[mid]) 8. hi=mid-1; 9. else 10. if(arr[mid]<key) 11. Lo=mid+1; 12. else 13. return mid; 14. } 15. return -1;} ``` يتم البحث الثنائي في مصفوفة مرتبة تصاعدياً أو تنازلياً حيث نقوم بقسم المصفوفة لمجالين فإذا كان العنصر الذي نبحث عنه أصغر من القيمة المتوسط في المصفوفة فهو في المجال الأصغر من القيمة المتوسطة ونغير قيمة الـ hi لتصبح 1 - mid أي المجال الذي نبحث عنه هو [mid - 1 Lo] إذا لم نجد العنصر نقوم بالبحث في المجال الأكبر من القيمة المتوسطة أي في المجال [1 + hi,mid] ونعيد العملية حتى نصل لمجال صغير يحوي العنصر فقط وإلا فإن الـ mid هو العنصر الذي نبحث عنه. ### حالات التعقيد أفضل حالة: عندما يكون العنصر الذي نبحث عنه في منتصف المصفوفة "ذلك حسب الخوارزمية الثانية" حيث يكون عدد العمليات = 1 أسوأ حالة : لا يوجد العنصر ضمن المصفوفة أبداً فستبقى تدور حتى يصبح Lo > hi فستكون عدد العمليات كالتالي: 1. عند اختبار العنصر middle سيكون عدد العمليات $$\frac{n}{2}$$. 2. عند اختبار المجال الأقل أو الأكبر من middle سيكون عدد العمليات $$\frac{n}{2^2}$$. 3. عند اختبار نصف المجال السابق أي ربع مجال المصفوفة الكلي سيكون $$\frac{n}{2^3}$$. ... إلخ ... فأخيرا: $$\frac{n}{2^0}$$ $$\frac{n}{2^1}$$ $$\frac{n}{2^2}$$ $$\frac{n}{2^3}$$ $$\frac{n}{2^4}$$ $$\frac{n}{2^5}$$ $$\frac{n}{2^k}$$ ⇒ $$\frac{n}{2^k}$$ = 1 فيكون التعقيد لأسوأ حالة كالتالي: **حساب التعقيد** ```c++ log 2k = log n k log 2 = log n k = logn ``` فالتعقيد (logn) و"عدد الدورات" هو 1 + k ### أيهما أفضل ؟ . لا يمكن الحكم مطلقا بأنَّ إحداهما أفضل من الأخرى، بل كل واحدة منهما أفضل من الأخرى في حالات، و التوضيح كما يلي: - عندما تكون كمية البيانات التي نود البحث فيها كبيرة و مرتبـة بترتيب ما، في هذه الحالة تعتبر خوارزمية البحث الثنائي أفضل، و ذلك لأنها في هذه الحالة ستوفر علينا عناء البحث في عدد كبير من العناصر عندما يتم تجاهله بناءً على الشرط. - عندما تكون كمية البيانات صغيرة و غير مرتبة، في هذه الحالة تعتبر خوارزمية البحث الخطي أفضل، لأن عدد العناصر صغير و غیر مرتب، و بالتالي فإننا لا نستطيع استخدام البحث الثنائي مباشرة، و كذلك عدد العناصر الصغير يعني أننا سنحتاج لعدد قليل من المقارنات. Diagrams: - A linear graph with y axis labeled 'f(n)' and x as 'n', with 2 lines. The first is a straight line from the origin passing through (n,n) labeled 'n'. The second is a curve that is going up more slowly than the straight line labeled 'log2 n'.