البحث

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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