الفصل الثالث

البحث

إن حقيقة أن الخوارزميات يمكن أن تنجز أنواع المهام كافة — بدايةً من ترجمة النصوص إلى قيادة السيارات — قد تعطينا صورة مضللة عن المجالات التي يغلب فيها استخدام الخوارزميات. قد تبدو الإجابة عادية. فلا يُحتمل أن تجد برنامجًا على جهاز كمبيوتر ينجز أيَّ مهمة مفيدة على الإطلاق من دون توظيف خوارزميات مختصة بالبحث في البيانات.

السبب في ذلك أن البحث بشكلٍ أو بآخر يظهر في كل السياقات تقريبًا. البرامج تستوعب البيانات، وغالبًا ستحتاج إلى البحث عن شيء في تلك البيانات؛ ومِن ثَم فلن يكون هناك مناص من استخدام خوارزمية بحث. فالبحث ليس عملية متكررة في البرامج فحسب؛ بل إنه نظرًا لكثرة حدوثها، قد يكون البحث أكثرَ العمليات استنفادًا للوقت في تطبيقٍ ما. ويمكن لخوارزمية البحث الجيدة أن تؤدي إلى تحسيناتٍ كبيرة من حيث السرعة.

البحث بشكل أو بآخر يظهر في كل السياقات تقريبًا … ويمكن لخوارزمية البحث الجيدة أن تؤدي إلى تحسيناتٍ كبيرة من حيث السرعة.

يتضمَّن البحث التنقيب عن عنصر معيَّن وسط مجموعة من العناصر. وهذا الوصف العام للمسألة يتضمَّن عدة تباينات. فثمَّة فارق كبير بين إذا ما كانت العناصر مرتَّبة بطريقةٍ مرتبطة بعملية البحث أم كان الترتيب عشوائيًّا. ثمة سيناريو مختلف يحدث عندما تُعطى لنا العناصر واحدًا تلو الآخر ويكون علينا أن نقرِّر ما إن كنا وجدنا العنصر الصحيح فور رؤيته أم لا من دون أن نستطيع إعادة التفكير في قرارنا. إذا بحثنا مرارًا في مجموعةٍ من العناصر، فمن المهم أن نعرف هل توجد عناصر أكثر شيوعًا من غيرها أم لا بحيث ينتهي بنا المقام إلى البحث عنها أكثر. سنتناول كل تلك التباينات في هذا الفصل، ولكن تذكَّر أن هناك المزيد. على سبيل المثال، لن نعرض سوى مسائل «البحث الدقيق» ولكن يوجد العديد من التطبيقات التي نحتاج فيها إلى «بحث تقريبي». لنضرب مثالًا بالتدقيق الإملائي: عندما تخطئ في كتابة كلمةٍ ما، سيضطر المدقِّق اللغوي إلى البحث عن كلمات مشابهة للكلمات التي أخفق في التعرُّف عليها.

كلما زادت أحجام البيانات، زادت أهمية القدرة على البحث بكفاءة في عدد ضخم من العناصر أكثر وأكثر. وسنرى أنه إذا كانت العناصر مرتَّبة، يمكن حينها أن يسير البحث جيدًا إلى أقصى درجة. في الفصل الأول، ذكرنا أنه يمكن العثور على عنصرٍ من بين مليار عنصر مرتَّب في غضون نحو ٣٠ عملية بحث؛ وسنرى الآن كيف يمكن القيام بذلك فعليًّا.

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

البحث عن إبرة في كومة قش

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

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

لا نتعامل عادةً مع عناصر مادية في أجهزة الكمبيوتر، بل مع تمثيلات رقمية لها. وتأتي إحدى الطرق الشائعة لتمثيل مجموعات من البيانات على جهاز كمبيوتر في شكل «قائمة». والقائمة عبارة عن بنية بيانات تحتوي على مجموعةِ عناصر بطريقةٍ تمكِّننا من العثور على عنصر بناءً على العنصر الذي يسبقه. عادة ما يمكننا اعتبار أن القائمة تحوي «عناصر مترابطة»، حيث يشير كل عنصر إلى العنصر التالي حتى النهاية بحيث لا يشير العنصر الأخير إلى شيء. والمجاز ليس بعيدًا عن الواقع؛ لأن أجهزة الكمبيوتر تستخدم مواقع الذاكرة الداخلية لتخزين العناصر. وفي «القائمة المترابطة»، يحتوي كل عنصر على مكوِّنين هما: حمولة البيانات وموقع الذاكرة للعنصر التالي في القائمة. يُطلق على الموقع في الذاكرة الذي يحمل موقع الذاكرة لمكانٍ آخرَ في الذاكرة «المؤشر». لذلك يحتوي كل عنصر في القائمة المترابطة على مؤشرٍ للعنصر التالي. يُطلق على العنصر الأول في القائمة «رأس» القائمة. ويُطلق على العناصر في القائمة اسم «العُقَد» أيضًا. ولا تشير العقدة الأخيرة إلى أي عنصر آخر؛ ومِن ثَم نقول إنها تشير إلى «قيمة فارغة»؛ أي لا شيء على الكمبيوتر.

القائمة عبارة عن سلسلة عناصر، ولكن لا يلزم ترتيب السلسلة باستخدام معيار معيَّن. على سبيل المثال، فيما يلي قائمة تحتوي على بعض الحروف الأبجدية:

إذا لم تكن القائمة مرتَّبة، فستسير خطوات الخوارزمية للبحث عن عنصرٍ ما بها على النحو التالي:
  • (١)

    الانتقال إلى رأس القائمة.

  • (٢)

    إذا كان هذا هو العنصر الذي نبحث عنه، فعليك الإبلاغ بأنه قد تم العثور عليه وأوقف البحث.

  • (٣)

    الانتقال إلى العنصر التالي في القائمة.

  • (٤)

    إذا وصلنا إلى قيمة فارغة، يتم الإبلاغ بأنه لم يتم العثور على العنصر ويتوقف البحث. وإذا لم نصل إلى قيمة فارغة، نعود إلى الخطوة رقم ٢.

يُطلق على تلك العملية «البحث الخطي» أو «البحث التسلسلي». لا يوجد شيء خاص في ذلك؛ فهو تطبيق مباشر لفكرة فحص كل عنصر تباعًا إلى أن نعثر على العنصر الذي نريده. في الواقع أن الخوارزمية تجعل الكمبيوتر يقفز من مؤشرٍ إلى آخر حتى يصل إلى العنصر الذي نبحث عنه أو يصل إلى قيمة فارغة. وفيما يلي، نوضِّح ما يحدث عندما نبحث عن الحرف E أو X:
إذا كنَّا نبحث في عدد من العناصر، فأفضل شيء يمكن أن يحدث هو الوصول إلى العنصر الذي نبحث عنه في الحال، وهو ما سيحدث إذا كان العنصر هو رأس القائمة. أما أسوأ شيء يمكن أن يحدث، فهو أن يكون العنصر في نهاية القائمة أو ليس على القائمة على الإطلاق. عندئذٍ، سنضطر إلى تصفُّح كل عناصر . وهكذا يصبح أداء البحث التسلسلي بالقيمة .

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

يواجه الناس مشكلةً في ذلك في بعض الأحيان. إذا كنا نبحث عن ورقةٍ بين كومة كبيرة من الأوراق، فربما نشعر بالضجر من تصفُّح الأوراق الواحدة تلو الأخرى. بل ربما نفكِّر في مدى تعاسة الحظ التي سنُمنَى بها إن تبيَّن أن الورقة في نهاية كومة الورق! لذا نتوقَّف عن تصفُّح كومة الورق بالترتيب ونلقي نظرة خاطفة على نهاية الكومة. لا خطأ في إلقاء نظرة خاطفة على نهاية الكومة، ولكن الخطأ أن نعتقد أن تلك الطريقة تحسِّن من فرص الانتهاء من البحث بسرعة. إذا كانت الكومة ذات ترتيب عشوائي، فلا يوجد سببٌ لكي نعتقد أن الورقة التي نبحث عنها ليست في البداية أو النهاية أو جهة اليمين أو في المنتصف. كل المواضع محتملة على نحوٍ متساوٍ؛ لذا فالبدء من قمة الكومة وصولًا إلى قاعدتها يُعَد استراتيجية جيدة مثل أي استراتيجية أخرى تضمن تفقُّد كل عنصر مرة واحدة فقط. لكن عادة ما يكون الأسهل أن نتتبَّع ما بحثنا فيه إذا كنا نبحث بترتيب معيَّن بدلًا من التنقُّل بين العناصر بلا نظام؛ ولذا نفضِّل الالتزام بطريقة البحث التسلسلي.

كل هذا يصح ما دام لا يوجد سببٌ للتشكيك في أن العنصر الذي نبحث عنه في موضعٍ معيَّن. ولكن إذا لم يكن ذلك صحيحًا، فالأمور تتغيَّر ويمكننا الاستفادة من أي معلومات إضافية قد تكون متوافرة لدينا لتسريع عملية البحث.

تأثير ماثيو والبحث

ربما لاحظت أن بعض الأشياء في مكتبٍ غير مرتَّب تجد طريقها إلى أعلى الكومة، بينما يبدو أن عناصرَ أخرى قد انزلقت إلى قاعدتها. وعند إزالة الفوضى في النهاية، يبتهج صاحب المكتب كثيرًا لأنه اكتشف أشياءَ مدفونةً وسط كومةٍ ظنَّ أنه قد فقدها منذ وقت طويل. ربما مرَّ آخرون أيضًا بتلك التجربة. فنحن نميل إلى وضع الأشياء التي نستخدمها كثيرًا في مكانٍ قريب منَّا؛ بينما تنزلق الأشياء القليلة الاستخدام بعيدًا عن متناول أيدينا أكثر وأكثر.

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

قد يحدث ألَّا نعمل بالمعدل نفسه على كل المستندات. فقد نعود إلى بعضها مرارًا، وربما لا نلتفت إلى مستندات أخرى إلا نادرًا. وإذا استمررنا في وضع كل مستندٍ أعلى الكومة بعد العمل عليه، فسنكتشف بعد فترة أن المستندات الأكثر استخدامًا ستكون قريبة من القمة، بينما المستندات الأخرى الأقل استخدامًا اتجهت إلى القاعدة. تلك الطريقة مناسبة لنا؛ لأننا نقضي وقتًا أقلَّ في تحديد أماكن المستندات الكثيرة الاستخدام، ومِن ثَم يقل وقت العمل بوجه عام.

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

ما مدى قابلية تلك الاستراتيجية للتطبيق؟ يعتمد هذا على عدد المرات التي نلاحظ فيها مثل هذه الفروق في كثرة الاستخدام. وقد تبيَّن أن هذا يحدث كثيرًا. نعرف مقولة «الغني يزداد غنًى، والفقير يزداد فقرًا». إنها لا ترتبط بالأغنياء والفقراء فحسب. فالأمر نفسه يحدث في مجموعةٍ مذهلة من الجوانب في مختلف مجالات النشاط. وقد اتخذت الظاهرة اسمًا وهو «تأثير ماثيو» أو تأثير متَّى نسبة للآية التالية في إنجيل متَّى (٢٥: ٢٩): «لأن كلَّ مَن له يُعطى فيزدادُ، ومَن ليس له فالذي عنده يُؤخذ منه.»

تتحدَّث الآية عن السلع المادية؛ لذا لنفكر في الثروة لدقيقةٍ. لنفترض أنك تمتلك استادًا كبيرًا يسع ٨٠ ألف فرد. بإمكانك قياس متوسط أطوال الأفراد في الاستاد. قد تكون النتيجة في حدود ١٧٠ سنتيمترًا (٥ أقدام و٧ بوصات). تخيَّل أنك أخرجت فردًا بصورة عشوائية من الاستاد وأدخلت أطول شخص في العالم. هل سيختلف متوسط الطول؟ حتى إذا كان أطولُ شخص في العالم ٣ أمتار (علمًا بأن هذا الطول لم يُسجَّل حتى الآن)، فلن يتغيَّر متوسط الأطوال عن القيمة السابقة؛ فالفرق مع متوسط الأطوال السابق أقلُّ من واحد على عشرة من الملِّيمتر.

تخيَّل الآن أنك بدلًا من قياس متوسط الأطوال، تقيس متوسط الثروات. يمكن أن يكون متوسط ثروات الثمانين ألف فرد السابقين مليون دولار (نحن نفترض مجموعة ثرية). تعاود الآن إدخال شخص آخر بين أغنى أثرياء العالم. قد تبلغ ثروة ذلك الشخص ١٠٠ مليار دولار. هل تلك القيمة تُحدِث فارقًا؟ نعم، تُحدِث فارقًا، بل فارقًا كبيرًا. سيزيد المتوسط من مليون دولار إلى ٢٢٤٩٩٨٧٫٥ دولار، أو أكثر من الضعف. نعلم أن الثروة ليست موزَّعة بالتساوي على مستوى العالم، ولكن ربما لا نعلم مدى عدم التساوي في توزيعها. فالتفاوت في توزيع الثروة أكبر بكثير من القياسات الطبيعية مثل الأطوال.

يظهر الفارق نفسه في القدرات والمَلَكات في العديد من المواقع الأخرى. فهناك العديد من الممثلين لم تسمع بهم من قبل. وهناك بضعة نجوم يظهرون في العديد من الأفلام ويربحون ملايين الدولارات. كان عالِم الاجتماع روبرت كيه ميرتون هو مَن صاغ مصطلح «تأثير ماثيو» عام ١٩٦٨ حين لاحظ أن العلماء المشهورين يحظون بالتقدير لأعمالهم أكثرَ من زملائهم الأقل شهرة حتى لو كانت إسهاماتهم متماثلة. فكلما ذاع صيت العالِم حظي بشهرةٍ أوسع.

تتَّبِع الكلمات في اللغة النمطَ نفسه؛ إذ يكون البعض منها أشهر وأكثر شيوعًا بكثير من غيره. وتضم قائمة المجالات التي تتَّسم بمثل هذه التفاوتات الصارخة حجم المدن (فالمدن الكبرى أكبر من المدن ذات الحجم العادي عدة أضعاف)، وعدد مواقع الويب وروابطها وشعبيتها (بعض المواقع لا تحظى إلا بالزوَّار العابرين بينما يحظى بعضها الآخر بملايين الزوار). كان انتشار مثل هذه التوزيعات غير المتكافئة — حيث يحصل عدد قليل من الأفراد على كم غير متناسب من الموارد — مجالًا ثريًّا للبحث والتحقيق على مدى السنوات القليلة الماضية. فالباحثون يعكفون على دراسة الأسباب والقوانين التي تقف خلف نشأة مثل تلك الظاهرة.1
من الممكن أن تُظهِر العناصر التي نبحث عنها مثل هذه الفروق على صعيد الشيوع والانتشار. لذا فالخوارزمية التي ستستفيد من تفاوت الشيوع بين العناصر قيد البحث تشبه إلى حدٍّ كبير وضْع كل مستند نجده أعلى الكومة:
  • (١)

    البحث عن عنصر باستخدام طريقة البحث التسلسلي.

  • (٢)

    إذا عُثر على العنصر، يُشار إلى العثور عليه ويوضع في مقدمة القائمة — على رأسها — ويتوقَّف البحث.

  • (٣)

    لو لم يُعثر على العنصر، يُشار إلى عدم وجوده، ويتوقف البحث.

في الشكل التالي، سيؤدي العثور على الحرف E إلى جلبه إلى المقدمة:
ثمة انتقاد محتمل قد يوجَّه إلى خوارزمية «النقل إلى المقدمة» كونها ستجعل العنصر قيد البحث في المقدمة حتى لو كان البحث عنه نادرًا. وهذا صحيح، لكن إذا لم يكن العنصر كثير الاستخدام، فسينتقل تدريجيًّا إلى نهاية القائمة كلما بحثنا عن عناصر أخرى؛ لأن هذه العناصر ستنتقل بدورها إلى المقدمة. لكن يمكننا الانتباه إلى الموقف عن طريق اتباع استراتيجية أقل تطرفًا. فبدلًا من نقل كل عنصر نعثر عليه إلى المقدمة فجأة، يمكننا تحريكه موضعًا واحدًا إلى الأمام. وهذه الطريقة تسمَّى «طريقة تبديل الموضع»:
  • (١)

    ابحث عن عنصر باستخدام بحث تسلسلي.

  • (٢)

    إذا عُثر على العنصر، فأشِر إلى أنه قد عُثر عليه وأبدِله مع العنصر الذي قبله (إذا لم يكن هو العنصر الأول) وتوقَّف عن البحث.

  • (٣)

    إذا لم يُعثر على العنصر، فأشِر إلى عدم وجوده وأوقف البحث.

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

تُعَد طريقتا النقل إلى المقدمة وتبديل الموضع مثالين على «البحث الذاتي التنظيم»، الذي جاءت تسميته تلك من كون قائمة العناصر تُرتَّب مع تواتر عمليات البحث، وسوف تعكس مدى شيوع العناصر قيد البحث. وبناءً على مدى شيوع العنصر وسط العناصر الأخرى، قد يكون التوفير في الوقت كبيرًا. فبينما يمكن توقُّع أداء البحث التسلسلي بالقيمة ، يمكن أن يكون أداء البحث ذاتي التنظيم بطريقة النقل إلى المقدمة بالقيمة . إذا كان لدينا ما يقرب من مليون عنصر، تكون هذه القيمة هي الفرق بين مليون و٥٠٠٠٠ تقريبًا. قد تؤتي طريقة تبديل الموضع نتائجَ أفضل، لكنها تتطلب مزيدًا من الوقت لتحقيقها. والسبب في ذلك أن الطريقتين كلتيهما تتطلبان «فترة إحماء» تعلِن خلالها العناصرُ الشائعة عن نفسِها وتشقُّ طريقها نحو المقدمة. في طريقة النقل إلى المقدمة تقصُر فترة الإحماء، أما في طريقة تبديل الموضع فيستغرق الإحماء فترةً أطول، ولكننا نحصل على نتائجَ أفضل.2

كيبلر والسيارات والسكرتيرات

بعدما فقد عالِم الفلك الشهير يوهانس كيبلر (١٥٧١-١٦٣٠) زوجتَه بسبب الكوليرا عام ١٦١١، بدأ التخطيط للزواج مرةً أخرى. ونظرًا لكونه رجلًا منهجيًّا، لم يترك شيئًا للصدفة. وفي خطابٍ طويل أرسله إلى البارون ستراهليندورف، وصف العملية التي اتَّبعها. خطَّط كيبلر لإجراء مقابلات مع ١١ عروسًا محتملة قبل أن يتخذ قراره. وانجذب بشدة إلى المرشَّحة الخامسة، ولكنه انصرف عنها بسبب أصدقائه الذين اعترضوا على مكانتها الاجتماعية المتواضعة. ونصحوه بأن يعيد النظر في المرشَّحة الرابعة بدلًا منها. ولكنها رفضته. في النهاية، وبعد دراسة ١١ مرشَّحة، تزوَّج كيبلر المرشَّحة الخامسة، وهي سوزانا روتينجر البالغة من العمر ٢٤ عامًا.

تلك القصة القصيرة مثالٌ مطول لعملية بحث؛ فقد كان كيبلر يبحث عن اختيار مثالي بين مجموعة من المرشَّحات المحتملات. لكن كانت هناك مشكلة في عملية البحث ربما لم ينتبه لها عندما بدأ، وهي أنه ربما لا يتمكَّن من العودة إلى اختيار محتمَل بعدما رفضه.

يمكننا إعادة صياغة المسألة بمصطلحات أحدث، من خلال البحث عن أفضل طريقة لتحديد سيارة لشرائها. قرَّرنا من قبل أن نزور عددًا محدَّدًا من معارض تجارة السيارات. ولكن الاعتزاز بالنفس لن يسمح لنا بالعودة إلى معرض سيارات بعد مغادرته. إذا رفضنا سيارة، فإن حفْظ ماء الوجه أمرٌ بالغ الأهمية، ولذا لا يمكننا العودة ونقول إننا قد غيَّرنا رأينا. أو ربما يدخل شخصٌ آخر ويشتري السيارة بعدما نغادر. وأيًّا كان الأمر، علينا أن نتخذ قرارًا نهائيًّا عند كل معرض، سواء بشراء السيارة أو عدم شرائها، عدم العودة إليه.

يُعَد هذا مثالًا على «مسألة التوقُّف الأمثل». علينا أن نتخذ إجراءً وفي الوقت نفسه نحاول تعظيمَ عائدٍ ما أو تقليل تكلفةٍ ما. في هذا المثال، نريد أن نقرِّر شراء السيارة، حين يكون هذا القرار سيفضي إلى شراء أفضل سيارة يمكن شراؤها. إذا قرَّرنا في مرحلةٍ مبكرة للغاية، فربما نستقر على سيارةٍ أسوأ من السيارات التي لم نرَها بعد. وإذا قرَّرنا في مرحلةٍ متأخرة للغاية، قد نغتم حين نكتشف أننا قد رأينا أفضلَ سيارة ولكننا فقدناها. إذن متى يكون الوقت الأمثل للتوقُّف واتخاذ القرار؟

وُصِفت المشكلةُ نفسها بمزيد من الحدة تحت اسم «مسألة السكرتيرة». أنت تريد اختيار سكرتيرة من بين مجموعةٍ من المرشَّحات. يمكنك إجراء مقابلة مع المرشَّحات واحدة بواحدة. لكن يجب أن تتخذ قرارًا بالتوظيف من عدمه في نهاية كل مقابلة. وإذا رفضت مرشَّحة، لا يمكنك أن تغيِّر رأيك لاحقًا وتقدِّم لها عرضًا (قد تكون المرشَّحة جيدة للغاية ومِن ثَم ينتزعها شخص آخرُ للعمل لديه). كيف ستختار المرشَّحة؟

الإجابة بسيطة إلى حد الذهول. تجري المقابلة مع ٣٧ بالمائة من المرشَّحات وترفضهن جميعًا، ولكن مع الاحتفاظ بسجلٍ للأفضل من بينهن كمعيار استرشادي. يظهر العدد ٣٧ — الذي يبدو سحريًّا — لأن ٣٧٪ تساوي تقريبًا ، حيث تعبِّر عن عدد أويلر، الذي يساوي تقريبًا ٢٫٧١٨٢ (تعرَّفنا على عدد أويلر في الفصل الأول). ثم تجري المقابلات مع بقية المرشَّحات. تتوقَّف عند أول مرشحة تكون أفضل من المعيار الذي معك. هذه ستكون اختيارك. وبالصيغة الخوارزمية، إذا كان لديك من المرشَّحات:
  • (١)
    احسب ، لإيجاد نسبة اﻟ ٣٧٪ من العدد من المرشَّحات.
  • (٢)
    ادرس أول من المرشَّحات وارفضهن. ستستخدم أفضل واحدة منهن كمعيار استرشادي لك.
  • (٣)

    واصل مع بقية المرشَّحات. اختر أول مرشَّحة تجدها أفضل من المعيار الذي معك، وتوقَّف.

لن تجد الخوارزمية المرشَّح الأفضل على الدوام؛ ففي النهاية، قد يكون المرشَّح الأفضل عمومًا هو المرشَّح المعياري الذي حدَّدته ضمن أول ٣٧ بالمائة، وسبق أن رفضته. ويمكن إثبات أنها ستجد لك المرشَّح الأفضل في ٣٧ بالمائة (مرة أخرى ) من جميع الحالات؛ إضافة إلى ذلك، لا توجد طريقة أخرى من شأنها أن تنجح في العثور على المرشَّح الأفضل في مزيد من الحالات. بعبارة أخرى، الخوارزمية هي أفضل الطرق التي يمكن تتبُّعها؛ وعلى الرغم من أنها قد لا تعطيك أفضل مرشَّح في ٦٣٪ من الحالات، فلا توجد استراتيجية أخرى تعطيك نتيجةً أفضل من تلك النتيجة.

بالعودة إلى السيارات، لنفترض أنك قرَّرت الذهاب إلى ١٠ معارض لتجارة السيارات. ينبغي أن نذهب إلى أول أربعة معارض وندوِّن ملحوظةً بأفضل عرض مقدَّم منها، دون شراء. بعد ذلك نبدأ في زيارة المعارض الستة المتبقية، وسنشتري من أول معْرض يقدِّم لنا عرضًا أفضلَ من العرض الذي دوَّناه (وسنتجاوز البقية حينئذٍ). ربما نكتشف أن المَعارض الستة جميعًا تقدِّم عروضًا أسوأ من الأربعة الأولى التي ذهبنا إليها من دون أن نشتري. ولكن لا توجد استراتيجيةٌ أفضلُ يمكن أن تعطينا احتمالاتٍ أفضل للحصول على أفضل صفقة.

لقد افترضنا أننا نريد العثور على أفضلِ مرشَّح محتمَل ولن نقبل بأقلَّ من ذلك. ولكن ماذا لو استطعنا القبول بشيءٍ أقلَّ في الحقيقة؟ هذا يعني أنه على الرغم من أننا نريد حقًّا أفضلَ سكرتيرة أو سيارة، فربما نقنع باختيارٍ آخرَ، وربما نسعد به وإن لم يكن قدْر سعادتنا لو اخترنا الأفضل. إذا وضعنا إطارًا للمسألة بهذا الشكل، فإن أفضلَ طريقة نحدِّد بها اختيارنا هي استخدام الخوارزميةِ نفسها السالفةِ الذكر، ولكن مع اختبار الجذر التربيعي لعدد المرشَّحين — — وإسقاطه. إذا فعلنا ذلك، فسوف تزيد احتمالية انتقاء الخيار الأفضل مع زيادة عدد المرشَّحين؛ فكلما زادت قيمة ، ارتفعت احتمالية انتقاء الخيار الأفضل إلى ١ (أي ١٠٠ بالمائة).3

البحث الثنائي

تناولنا طرقَ البحث المختلفة وطابقناها مع مختلف السيناريوهات. والقاسم المشترك في كل هذه الطرق أن العناصر التي نتناولها تأتينا دون ترتيب محدَّد؛ وفي أفضل الحالات، نرتِّبها نحن تدريجيًّا حسب تكرار استخدامها في عمليةِ بحث ذاتية التنظيم. ولكن يتغيَّر الموقف تمامًا إذا كانت العناصر مرتَّبة منذ البداية.

لنفترض أن لدينا كومة من المستندات، كل مستند معرَّف برقم. المستندات في الكومة مرتَّبة حسب الرقم التعريفي من الأصغر إلى الأكبر (لا يلزم أن تكون الأرقام متوالية). إذا كان لدينا كومة كتلك ونبحث عن مستندٍ ذي رقم تعريفي محدَّد، فمن الحماقة أن نبدأ بأول مستند ونستمر إلى نهاية الكومة حتى نعثر على المستند الذي نبحث عنه. هناك استراتيجيةٌ أفضل بكثير وهي الانتقال مباشرة إلى منتصف الكومة. ثم نطابق الرقم التعريفي الوارد على المستند في المنتصف برقم المستند الذي نبحث عنه. هناك ثلاث نتائج محتملة:
  • (١)

    إذا حالفنا الحظ، قد نقع على المستند الذي نريده بالضبط. وهنا تنتهي عملية البحث.

  • (٢)

    أن يكون الرقم التعريفي للمستند الذي نبحث عنه أكبر من الرقم التعريفي للمستند الذي بين أيدينا. وفي تلك الحالة نعلم يقينًا أنه يمكننا تجاهل المستند الذي بين أيدينا «وكذلك المستندات التي قبله». وحسب ترتيب المستندات، ستكون الأرقام التعريفية لها جميعًا أصغر. وهذا يعني أننا لم نصل إلى هدفنا بعدُ.

  • (٣)

    أن يحدث العكس: أن يكون الرقم التعريفي للمستند الذي نبحث عنه أصغر من الرقم التعريفي للمستند الذي بين أيدينا. وعندئذٍ يمكننا تجاهل المستند الذي بين أيدينا مطمئنين، «وكذلك كل المستندات التي تأتي بعده». وعندئذٍ نكون قد تجاوزنا هدفنا.

في أيٍّ من النتيجتين الأخيرتين، يصبح المتبقي لدينا كومة تعادل نصف الكومة الأصلية على أقصى تقدير. إذا بدأنا بعددٍ فردي من المستندات، ولنقل العدد ، فإن ناتج قسمة العدد من المستندات إلى نصفين يعطينا جزأين، كل جزء يحتوي على العدد من العناصر (بغض النظر عن الجزء الكسري في عملية القسمة):
أما إذا كان لدينا عدد زوجي من العناصر، فسيعطينا ناتج القسمة جزأين؛ أحدهما يضم من العناصر، والآخر يضم من العناصر:

ما زلنا لم نعثر على ما نبحث عنه بعد، ولكننا في موقفٍ أفضلَ من ذي قبل بكثير؛ فقد صار لدينا عدد أقل بكثير من العناصر للبحث فيها. وهذا ما نفعله. نتحقق من المستند الأوسط في «العناصر المتبقية» ونكرِّر الإجراء.

في الشكل في الصفحة التالية، يمكنك أن ترى كيف تتطوَّر العملية بالنسبة إلى ١٦ عنصرًا نبحث فيها عن العنصر رقم ١٣٥. نحدِّد الحدود التي نبحث بداخلها والعنصر الأوسط باللون الرمادي.

في البداية، يكون نطاق البحث هو مجموعة العناصر كلها. ننتقل إلى العنصر الأوسط، الذي نجد أنه العنصر ٣٨٤. هذا العنصر أكبر من ١٣٥، ومِن ثَم نتجاهله، وكذلك كل العناصر الواقعة إلى يمينه. نأخذ العنصر الأوسط في العناصر المتبقية وهو العنصر ٧٢. هذا العنصر أصغر من ١٣٥، لذا نتجاهله وكذلك كل العناصر الواقعة على يساره. وبذلك يكون نطاق البحث قد تقلَّص إلى ثلاثة عناصر فقط. نأخذ العنصر الأوسط ونجد أنه العنصر المطلوب. لم يستغرق الأمر سوى ثلاث عمليات تحقُّق لإنهاء بحثنا، ولم نحتَج إلى التحقُّق حتى من ١٣ عنصرًا من بين ١٦ عنصرًا.

figure

تصلح تلك الطريقة أيضًا إذا كنا نبحث عن شيءٍ غير موجود. يمكنك إدراك ذلك في الشكل التالي، حيث إننا نبحث في العناصر نفسها عن عنصر باسم ٥٢٠.

في هذه المرة، ٥٢٠ أكبر من ٣٨٤، ومِن ثَم نقيِّد البحث في النصف الأيمن من تلك العناصر. وهناك نجد أن العنصر الأوسط في النصف العلوي هو ٦١٣، وهو أكبر من ٥٢٠. عندئذٍ نقيِّد البحث في ثلاثة عناصر فقط، أوسطهم هو ٥٠٧. هذا العنصر أصغر من ٥٢٠. لذا نتجاهله ليتبقى لدينا عنصر واحد للتحقُّق منه ونكتشف أنه ليس العنصر الذي نريده. ومِن ثَم يمكننا إنهاء عملية البحث ونقول إن العنصر غير موجود. لم تستغرق العملية أكثر من ٤ عمليات تحقُّق.

يُطلَق على الطريقة التي وصفناها للتو «البحث الثنائي»؛ لأن في كل مرة نقسِّم نطاق القيم التي نبحث فيها إلى نصفين. ونطلِق على نطاق القيم الذي نُجري فيه عملية البحث «مساحة البحث». باستخدام ذلك المفهوم، يمكننا تحويل البحث الثنائي إلى خوارزمية تتكوَّن من الخطوات التالية:
  • (١)

    إذا كانت مساحة البحث فارغة، فهذا يعني أنه لا يوجد مكانٌ للبحث فيه، ومِن ثَم نقول إن البحث قد فشل ونتوقَّف. أما إذا لم تكن كذلك، نبحث عن العنصر الأوسط في مساحة البحث.

  • (٢)

    إذا كان العنصر الأوسط أقلَّ من العنصر قيد البحث، نقلِّص مساحة البحث من العنصر الأوسط بترتيب تصاعدي ونعود إلى الخطوة ١.

  • (٣)

    ولكن إذا كان العنصر الأوسط أكبر من العنصر قيد البحث، نقصُر مساحة البحث على العنصر الأوسط ونعود إلى الخطوة ١.

  • (٤)

    وإذا كان العنصر الأوسط مساويًا للعنصر قيد البحث، نقول إن البحث قد نجح ونتوقَّف.

figure
بهذه الطريقة، نُقسِّم العناصر التي علينا البحث عنها على اثنين. ويُطلق على هذه الطريقة فرِّق تَسُد. تؤدي تلك الطريقة إلى تكرار عملية القسمة، ما يعطينا لوغاريتمًا كما رأينا في الفصل الأول. وتكرار القسمة على اثنين يعطينا لوغاريتمًا أساسه العدد اثنان. وفي أسوأ الحالات، سيستمر البحث الثنائي في قسمة العناصر مرارًا وتكرارًا حتى تستحيل عملية القسمة كما رأينا في مثال عملية البحث الفاشلة التي لم يُعثر فيها على العنصر. بالنسبة إلى العدد من العناصر، لا يمكن أن تتكرَّر عملية القسمة أكثر من من المرات؛ وعليه فإن قيمة تعقيد البحث الثنائي تساوي .
نسبة التحسُّن مقارنة ببحثٍ تسلسلي — حتى في بحث ذاتي التنظيم — نسبة رائعة. فلن يستغرق الأمر أكثر من ٢٠ استكشافًا للبحث في مليون عنصر. لننظر من زاوية أخرى، باستخدام مائة احتمال، نتمكَّن من البحث عن أي عنصر وإيجاده من بين ٢١٠٠ ١٫٢٧ × ١٠٣٠، وهذا العدد أكبر من «نونليون».
إن فاعلية البحث الثنائي مذهلة. وربما لا يضاهي فاعليتها إلا شهرتها السيئة. فهي خوارزمية قائمة على الحدْس. ولكن هذه الطريقة البسيطة أثبتت مرارًا أنها معقَّدة وخادعة بما لا يجعلها تعمل بصورةٍ صحيحة في برنامجٍ من برامج الكمبيوتر. ولأسباب لا تتعلَّق بخوارزمية البحث الثنائي في حد ذاتها، بل بالطريقة التي نحوِّل بها الخوارزميات إلى تعليماتٍ برمجية حقيقية في لغة البرمجة، وقَع مبرمجون فريسةً لأخطاءٍ برمجية خبيثة تسللت إلى عمليات التنفيذ. والحديث ليس عن المبتدئين في المجال؛ فحتى المبرمجون العالميون فشلوا في تنفيذها بالطريقة الصحيحة.4
للتعرُّف على المكامن المحتملة لتلك الأخطاء، فكِّر كيف نجد العنصر الأوسط بين العناصر التي نريد البحث فيها في الخطوة الأولى من الخوارزمية. إليك فكرة بسيطة: العنصر الأوسط في العنصرين و هو ويُقرَّب إلى عدد صحيح إذا لم يكن الناتج عددًا طبيعيًّا. هذا صحيح ونابع من الرياضيات الابتدائية البسيطة، ولذا ينطبق في أي مجال.
باستثناء أجهزة الكمبيوتر. تمتلك أجهزة الكمبيوتر موارد محدودةً من بينها الذاكرة. ولذلك لا يمكن تمثيل كل الأعداد التي نريدها على جهاز الكمبيوتر. ببساطة، ستكون بعض الأرقام كبيرةً للغاية. فإذا كان الكمبيوتر له حدٌّ أعلى لحجم الأعداد التي يمكن أن يتعامل معها، فإن العنصرين و ينبغي أن يكونا أقلَّ من هذا الحد. بالطبع أقل من ذلك الحد. ولكن كي نحسب ، ينبغي أن نحسب أولًا ثم نقسم الناتج على اثنين، «وذلك المجموع قد يكون أكبر من الحد الأعلى»! وهذا يسمَّى «الفيض»؛ أي تجاوز نطاق القيم المسموح به. ولذلك تقع في خطأ برمجي لم تظن أنك قد تقع فيه. ولن تكون النتيجة هي القيمةَ الوسطى، بل شيئًا مختلفًا تمامًا.

لا تيأس إذا وجدت نفسك بائسًا تتأمَّل سطرًا من الشيفرة البرمجية لا يفعل ما تعتقد أنه يجب أن يفعله. لست وحيدًا في ذلك. فهو يحدث للجميع؛ بل يحدث للصفوة.

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

نحن هنا معنيون بالخوارزميات وليس بالبرمجة، ولكن اسمحوا للمؤلِّف أن يشارك بنصيحةٍ لمن يكتبون أو يريدون كتابة برامج الكمبيوتر. لا تيأس إذا وجدت نفسك بائسًا تتأمَّل سطرًا من الشيفرة البرمجية لا يفعل ما تعتقد أنه يجب أن يفعله. لا تفزع إذا أدركتَ في اليوم التالي أن الخطأ كان بالفعل أمام عينيك طوال الوقت. كيف لم ترَه؟ لست وحيدًا في ذلك. فهذا يحدث للجميع؛ بل يحدث للصفوة.

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

جميع الحقوق محفوظة لمؤسسة هنداوي © ٢٠٢٢