النسخة الأصلية ل هذه القصة ظهرت في مجلة Quanta.
غالبًا ما يتعامل علماء الكمبيوتر مع المشكلات المجردة التي يصعب فهمها ، ولكن خوارزمية جديدة مثيرة تهم أي شخص يمتلك الكتب ورف واحد على الأقل. تتناول الخوارزمية شيئًا يسمى مشكلة فرز المكتبة (بشكل أكثر رسمية ، مشكلة “وضع العلامات”). يكمن التحدي في وضع استراتيجية لتنظيم الكتب في نوع من الترتيب المرتبة – من الناحية الفنية ، على سبيل المثال – تقلل من الوقت الذي يستغرقه كتابًا جديدًا على الرف.
تخيل ، على سبيل المثال ، أنك تبقي كتبك متجانسة معًا ، تاركًا مساحة فارغة على أقصى اليمين من الرف. ثم ، إذا قمت بإضافة كتاب من قبل إيزابيل أليندي إلى مجموعتك ، فقد تضطر إلى نقل كل كتاب على الرف لإفساح المجال لذلك. سيكون ذلك عملية تستغرق وقتًا طويلاً. وإذا حصلت على كتاب من قبل دوغلاس آدمز ، فسيتعين عليك القيام بذلك مرة أخرى. من شأن الترتيب الأفضل أن يترك مساحات غير مشغولة موزعة في جميع أنحاء الرف – ولكن كيف ، بالضبط ، يجب توزيعها؟
تم تقديم هذه المشكلة في ورقة 1981 ، وتتجاوز ببساطة تزويد أمناء المكتبات بالتوجيه التنظيمي. ذلك لأن المشكلة تنطبق أيضًا على ترتيب الملفات على محركات الأقراص الصلبة وفي قواعد البيانات ، حيث يمكن أن ترقيم العناصر المراد ترتيبها بالمليارات. نظام غير فعال يعني أوقات انتظار كبيرة ونفقات حسابية كبيرة. اخترع الباحثون بعض الأساليب الفعالة لتخزين العناصر ، لكنهم أرادوا منذ فترة طويلة تحديد أفضل طريقة ممكنة.
في العام الماضي ، في دراسة تم تقديمها في مؤتمر علوم الكمبيوتر في شيكاغو ، وصف فريق من سبعة باحثين وسيلة لتنظيم العناصر التي تأتي بالقرب من المثل الأعلى النظري. يجمع النهج الجديد بين القليل من المعرفة بمحتويات رف الكتب السابقة مع القوة العشوائية المدهشة.
وقال سيث بيتي ، عالم الكمبيوتر في جامعة ميشيغان ، لأن العديد من هياكل البيانات التي نعتمد عليها اليوم تخزن المعلومات: “إنها مشكلة مهمة للغاية” ، لأن العديد من هياكل البيانات التي نعتمد عليها اليوم تخزن المعلومات اليوم. ووصف العمل الجديد بأنه “مستوحى للغاية (و) بسهولة واحدة من أفضل ثلاث أوراق مفضلة لهذا العام.”
تضييق الحدود
فكيف يمكن للمرء أن يقيس رف الكتب المصنوع جيدًا؟ هناك طريقة شائعة هي معرفة المدة التي يستغرقها لإدخال عنصر فردي. وبطبيعة الحال ، يعتمد ذلك على عدد العناصر الموجودة في المقام الأول ، وهي قيمة تشير إليها عادة ن. في مثال إيزابيل أليندي ، عندما يتعين على جميع الكتب الانتقال لاستيعاب كتاب جديد ، فإن الوقت الذي يستغرقه يتناسب مع ن. أكبر ن، كلما استغرق الأمر. هذا يجعل هذا “الحد الأعلى” للمشكلة: لن يستغرق وقتًا أطول من وقت يتناسب مع الوقت ن لإضافة كتاب واحد إلى الرف.
أراد مؤلفو ورقة عام 1981 التي تدخلت في هذه المشكلة معرفة ما إذا كان من الممكن تصميم خوارزمية مع متوسط وقت الإدراج أقل بكثير من ن. وبالفعل ، أثبتوا أنه يمكن للمرء أن يفعل ما هو أفضل. قاموا بإنشاء خوارزمية مضمونة لتحقيق متوسط وقت الإدراج يتناسب مع (LOGH ن)2. كان لهذه الخوارزمية خصائصان: كانت “حتمية” ، مما يعني أن قراراتها لا تعتمد على أي عشوائي ، وكانت أيضًا “سلسة” ، مما يعني أن الكتب يجب أن تنتشر بالتساوي داخل الأقسام الفرعية من الرف حيث الإدراج (أو الحذف) مصنوعة. ترك المؤلفون مفتوحين مسألة ما إذا كان يمكن تحسين الحد الأعلى إلى أبعد من ذلك. لأكثر من أربعة عقود ، لم يتمكن أحد من القيام بذلك.
ومع ذلك ، فإن السنوات المتداخلة قد شاهدت تحسينات على الحد الأدنى. بينما يحدد الحد الأعلى الحد الأقصى للوقت المحتمل اللازم لإدراج كتاب ما ، فإن الحد الأدنى يعطي أسرع وقت إدخال ممكن. لإيجاد حل نهائي لمشكلة ما ، يسعى الباحثون إلى تضييق الفجوة بين الحدود العلوية والسفلية ، بشكل مثالي حتى يتزامن. عندما يحدث ذلك ، تعتبر الخوارزمية مثالية – محدودة بشكل غير محدود من أعلى وأسفل ، ولا تترك مجالًا لمزيد من التحسين.
