أساسيات الحاسب والبرمجة الأدلة التقنية

مشكلة التوقف Halting Problem ومسألة P مقابل NP بالكود

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

مشكلة التوقف Halting Problem ومسألة P مقابل NP بالكود

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

هذان السؤالان يقودان إلى أعمق نتيجتين في علوم الحاسب. الأولى أن هناك أسئلة لا يستطيع أي برنامج أن يجيب عنها إطلاقاً، مهما كان الجهاز سريعاً والوقت طويلاً، وأشهرها مشكلة التوقف Halting Problem. والثانية أن هناك مسائل يمكن حلها نظرياً، ولكن كل الطرق المعروفة لحلها تنفجر في الوقت مع حجم المدخل، وهذا هو سؤال P مقابل NP الذي ما زال مفتوحاً منذ أكثر من خمسين سنة. وفي هذا المقال لن نكتفي بالتعريفات، وإنما سوف نكتب البرهان على مشكلة التوقف ككود يعمل، ثم نقيس بأيدينا كيف ينفجر وقت حل مسألة SAT ومسألة البائع المتجول.

وسوف نناقش في هذا المقال ما يلي:

  • من أين جاء سؤال «ما الذي يمكن حسابه؟»، ومن هو Alan Turing في هذه القصة.
  • مشكلة التوقف، والبرهان بالقطر Diagonal Argument مكتوباً بلغة Python ومشغلاً ضد ثلاثة برامج تحاول حلها.
  • الفرق بين المسائل القابلة للحسم Decidable وغير القابلة للحسم Undecidable، وأثر ذلك على أدوات التحليل التي تستخدمها كل يوم.
  • لماذا لا ينقذنا أن ذاكرة الحاسب الحقيقي محدودة.
  • من القابلية إلى الكلفة: الصنف P والصنف NP والمسائل NP-Complete.
  • مختبر SAT: البحث الشامل مقابل خوارزمية DPLL، ولماذا التحقق من الحل سريع والبحث عنه بطيء، وأين تقع الصيغ الصعبة.
  • مختبر البائع المتجول TSP: كل الترتيبات، ثم البرمجة الديناميكية، ثم حل تقريبي سريع وكم يبعد عن الأفضل.
  • ماذا تفعل عملياً عندما تواجه مسألة من هذا النوع، والأخطاء الشائعة.

من أين جاء سؤال «ما الذي يمكن حسابه؟» Computability

في 1928 طرح الرياضي الألماني David Hilbert مع Wilhelm Ackermann سؤالاً عرف باسم «مسألة القرار» Entscheidungsproblem: هل توجد طريقة آلية، أي خطوات محددة يمكن أن ينفذها شخص دون تفكير، تقرر لأي عبارة رياضية منطقية هل هي صحيحة أم لا؟ وكان الأمل أن تكون الإجابة نعم، فتصبح الرياضيات كلها قابلة للحساب. والمشكلة أن أحداً لم يكن يملك تعريفاً دقيقاً لمعنى «طريقة آلية» حتى يثبت وجودها أو عدمها.

وفي 1936 نشر Alan Turing، وعمره 24 سنة، ورقته On Computable Numbers, with an Application to the Entscheidungsproblem، وفيها عرف «الطريقة الآلية» بآلة خيالية بسيطة جداً: شريط طويل مقسم إلى خانات، ورأس يقرأ خانة ويكتب فيها ويتحرك يميناً أو يساراً، وجدول قواعد صغير يقول للرأس ماذا يفعل في كل حالة. وهذه هي آلة تورنغ Turing Machine، والفكرة المهمة فيها أن كل ما يستطيع أي حاسب اليوم أن يحسبه، من هاتفك إلى أكبر سيرفر، تستطيع آلة تورنغ أن تحسبه، ببطء أكبر فقط. وقد مررنا على قصة Turing في مقال قصة الذكاء الاصطناعي من تورنغ إلى ChatGPT، وإذا كنت قد بنيت مفسراً صغيراً في مقال ابن مفسراً صغيراً بيدك فأنت تعرف الإحساس: برنامج يقرأ برنامجاً آخر وينفذه خطوة خطوة.

وفي نفس السنة تقريباً وصل الرياضي الأمريكي Alonzo Church إلى نفس النتيجة بطريقة مختلفة تماماً، هي حساب لامدا Lambda Calculus الذي صار لاحقاً أساس البرمجة الوظيفية Functional Programming. وتبين أن الطريقتين متكافئتان، أي أن كل ما يحسب بإحداهما يحسب بالأخرى، ومن هنا جاءت الفكرة المعروفة بأطروحة Church وTuring: كل ما نعتبره «قابلاً للحساب بطريقة آلية» هو بالضبط ما تحسبه آلة تورنغ. وهي أطروحة وليست مبرهنة، لأن «الطريقة الآلية» مفهوم بشري لا يمكن تعريفه رياضياً إلا بأحد هذين النموذجين، ولكن لم يجد أحد حتى اليوم طريقة حساب تتجاوزهما، ولا حتى الحاسب الكمومي، الذي قد يكون أسرع في مسائل معينة، ولكنه لا يحسب ما لا تحسبه آلة تورنغ.

وبهذا التعريف استطاع Turing أن يثبت أن الإجابة عن سؤال Hilbert هي «لا»، وكانت أداته في ذلك سؤالاً يبدو أبسط بكثير، وهو مشكلة التوقف.

خريطة المسائل: الدائرة الكبيرة كل المسائل، وداخلها المسائل القابلة للحسم Decidable التي يوجد برنامج يجيب عنها دائماً، وخارجها غير القابلة للحسم مثل مشكلة التوقف، وداخل القابلة للحسم الصنف NP الذي يمكن التحقق من حلوله بسرعة، وداخله الصنف P الذي يمكن حله بسرعة، وعلى حافة NP المسائل NP-Complete مثل SAT والبائع المتجول وجدولة المناوبات، والسؤال المفتوح هل P تساوي NP
خريطة المقال: سؤال القابلية للحساب أولاً، ثم سؤال الكلفة داخل ما يمكن حسابه

مشكلة التوقف Halting Problem: سؤال يبدو سهلاً

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

والحل الأول الذي يخطر على البال: شغل البرنامج وانتظر. فإذا توقف فالإجابة «نعم». والمشكلة في الحالة الأخرى، فإذا لم يتوقف بعد دقيقة، فهل هو في حلقة لا نهائية، أم أنه برنامج بطيء سوف ينتهي بعد ساعة؟ ولا يوجد وقت انتظار يكفي لكل البرامج. والحل الثاني: اقرأ الكود وابحث عن الحلقات التي لا تنتهي، مثل while True دون break. وهذا يكتشف الحالات الواضحة، ولكن شرط توقف الحلقة قد يعتمد على حساب لا يعرف أحد نتيجته. فمثلاً لا يعرف أحد حتى اليوم هل الحلقة التالية تتوقف لكل رقم موجب n، وهي ما يسمى حدسية Collatz:

while n != 1:
    n = n // 2 if n % 2 == 0 else 3 * n + 1

ولكن عدم معرفتنا بطريقة لا يعني أنها غير موجودة، وهنا يأتي برهان Turing، الذي يقول إنه لا يمكن أن يوجد برنامج واحد يجيب عن السؤال إجابة صحيحة لكل البرامج، والدليل أن أي برنامج تدعي أنه يفعل ذلك يمكن أن نبني له برنامجاً يخدعه.

البرهان بالقطر Diagonal Argument ككود يعمل

الفكرة كما يلي: لنفرض أن لديك دالة halts(p, x) تجيب دائماً وبشكل صحيح: هل يتوقف البرنامج p عندما نعطيه المدخل x؟ الآن نكتب برنامجاً «معاكساً» Contrarian يأخذ برنامجاً p ويسأل halts عن p عندما يعطى نفسه كمدخل، ثم يفعل العكس: إذا كانت الإجابة «سوف يتوقف» دخل في حلقة لا تنتهي، وإذا كانت «لن يتوقف» توقف فوراً. ثم نعطي البرنامج المعاكس نفسه. فإذا قالت halts إنه يتوقف، فهو لن يتوقف، وإذا قالت إنه لن يتوقف، فهو يتوقف. أي أن halts مخطئة في الحالتين، وهذا يناقض الفرض أنها صحيحة دائماً.

ولماذا يسمى «بالقطر»؟ تخيل جدولاً، صفوفه كل البرامج الممكنة وأعمدته كل المدخلات الممكنة، وفي كل خانة «يتوقف» أو «لا يتوقف». والبرنامج المعاكس مصمم بحيث يختلف عن كل برنامج في الجدول في خانة واحدة على الأقل، وهي الخانة التي يعطى فيها البرنامج نفسه، أي خانات القطر. فلا يمكن أن يكون البرنامج المعاكس صفاً في الجدول، ومع ذلك هو برنامج حقيقي، فالجدول الذي تحسبه halts لا يمكن أن يكون كاملاً. وهي نفس الحيلة التي استخدمها Georg Cantor قبل ذلك بعقود ليثبت أن الأعداد الحقيقية لا يمكن عدها.

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

والبرهان عادة يكتب على الورق بدالة halts مفترضة، ولكننا نستطيع أن نفعل شيئاً أكثر إقناعاً: أن نكتب عدة دوال halts حقيقية بطرق مختلفة، ثم نبني لكل منها برنامجها المعاكس، ونشغله فعلاً لنرى أنها تخطئ. وحتى نستطيع أن «نشغل البرنامج لعدد محدد من الخطوات»، كتبنا البرامج كدوال مولدة Generators في Python، كل yield فيها خطوة واحدة، والبرنامج يتوقف عندما تنتهي الدالة، كما يشرح توثيق Python. والملف halting.py كاملاً في مجلد lab مع المقال، وأهم أجزائه:

def run(prog, arg, budget):
    """Run prog(arg) for at most `budget` steps. Returns the number of steps if it halted, None otherwise."""
    g = prog(arg)
    for step in range(budget):
        try:
            next(g)
        except StopIteration:
            return step
    return None

def make_contrarian(decider):
    def contrarian(p):
        if decider(p, p):          # "you say p halts on itself?"
            while True:            # then loop forever
                yield
        yield                      # otherwise stop right away
    return contrarian

وكتبنا ثلاث دوال تحاول الإجابة عن سؤال التوقف، وكل منها تمثل طريقة حقيقية:

  • always_yes: تقول «يتوقف» دائماً. وهي ليست غبية كما تبدو، فأغلب البرامج التي يكتبها الناس تتوقف فعلاً.
  • looks_at_source: تحليل ثابت Static Analysis، تقرأ الكود بالوحدة ast وتبحث عن while True ليس فيها break أو return، فإذا وجدتها قالت «لا يتوقف». وهذه فكرة كثير من أدوات التحليل.
  • simulate: محاكاة Simulation، تشغل البرنامج حتى 100,000 خطوة، فإذا انتهى قالت «يتوقف»، وإلا قالت «لا يتوقف». ولأن البرنامج المعاكس يستدعي الدالة نفسها، فهي سوف تحاكي نفسها وهي تحاكي نفسها، لذلك أضفنا حداً للعمق، فإذا تجاوز العمق ثلاثة مستويات «خمنت» الإجابة، ونسخة simulate_guess_yes تخمن «يتوقف» بدلاً من «لا يتوقف».

وشغلنا الملف داخل Container من debian:trixie-slim مع Python 3.13.5، والمخرج سوف يكون كما يلي:

easy programs:
  always_yes           counts_to_ten -> True   spins -> True
  looks_at_source      counts_to_ten -> True   spins -> False
  simulate             counts_to_ten -> True   spins -> False

the contrarian built against each decider:
  always_yes           says halts=True   reality: still running after 1,000,000 steps  -> WRONG
  looks_at_source      says halts=False  reality: halted after 1 steps                 -> WRONG
  simulate             says halts=True   reality: still running after 1,000,000 steps  -> WRONG
  simulate_guess_yes   says halts=False  reality: halted after 1 steps                 -> WRONG

ولنقرأ المخرج سطراً سطراً:

  • الجزء الأول اختبار على برنامجين سهلين: counts_to_ten يعد إلى عشرة ويتوقف، وspins يدور إلى الأبد. الدالتان looks_at_source وsimulate أجابتا إجابة صحيحة على الاثنين، وalways_yes أخطأت في spins كما هو متوقع. أي أن الدوال ليست سيئة، وهي تعمل في الحالات العادية.
  • always_yes قالت إن برنامجها المعاكس يتوقف، فدخل البرنامج في الحلقة ولم يتوقف بعد مليون خطوة.
  • looks_at_source وجدت while True دون break في كود البرنامج المعاكس، فقالت «لا يتوقف»، ولكن الحلقة لا تنفذ إلا إذا قالت الدالة «يتوقف»، فتوقف البرنامج بعد خطوة واحدة.
  • simulate قالت «يتوقف»، والسبب أن التخمين في أعمق مستوى قلب الإجابة في كل مستوى فوقه، حتى وصلت إلى المستوى الأعلى «يتوقف»، فدار البرنامج المعاكس إلى الأبد.
  • وعندما غيرنا التخمين في simulate_guess_yes انقلبت الإجابة، وأخطأت مرة أخرى بالعكس.
نتيجة مختبر مشكلة التوقف: أربع دوال تحاول الإجابة، always_yes قالت يتوقف والبرنامج المعاكس لم يتوقف بعد مليون خطوة، وlooks_at_source قالت لا يتوقف والبرنامج توقف بعد خطوة، وsimulate قالت يتوقف والبرنامج لم يتوقف، وsimulate_guess_yes قالت لا يتوقف والبرنامج توقف، والأربع مخطئة
أربع طرق مختلفة، وكل منها صحيحة في البرامج العادية، وكلها مخطئة أمام برنامجها المعاكس

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

ولكن حاسبي محدود الذاكرة Finite Memory، أليس كذلك؟

قد يعترض أحدهم اعتراضاً ذكياً: آلة تورنغ لها شريط لا نهائي، أما الجهاز الحقيقي فذاكرته محدودة، والبرنامج الذي يعمل في ذاكرة محدودة له عدد محدود من الحالات الممكنة، فإذا تكررت حالة فهو في حلقة لا تنتهي، وإذا لم تتكرر فلا بد أن يتوقف يوماً. وهذا صحيح نظرياً، فمشكلة التوقف لآلة ذاكرتها محدودة قابلة للحسم. ولكن انظر إلى العدد: برنامج صغير يستخدم كيلوبايت واحداً فقط من الذاكرة، أي 8,192 بت، له 28192 حالة ممكنة، وهو رقم من قرابة 2,466 خانة عشرية، أكبر بما لا يقارن من عدد الذرات في الكون المرئي. لذلك فإن الحل «النظري» هنا لا يختلف عملياً عن الاستحالة، والنتيجة الهندسية واحدة: لا تتوقع أن تعرف مسبقاً هل البرنامج سوف ينتهي، وضع له حداً.

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

قابل للحسم Decidable أم غير قابل للحسم Undecidable؟

المسألة القابلة للحسم Decidable هي مسألة إجابتها نعم أو لا، ويوجد برنامج يتوقف دائماً ويعطي الإجابة الصحيحة لكل مدخل، مثل «هل هذا الرقم أولي؟» أو «هل يوجد مسار بين هاتين النقطتين في هذا الرسم البياني؟». وغير القابلة للحسم Undecidable هي التي لا يوجد لها مثل هذا البرنامج، ومشكلة التوقف أولها وأشهرها.

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

وهذا يفسر السؤال في أول المقال: أدوات التحليل الثابت، من المحرر إلى المترجم إلى أدوات فحص الأمان، لا تستطيع أن تكون دقيقة دائماً، فهي تختار جهة الخطأ. فبعضها متحفظ Conservative، يحذرك من كل ما قد يكون خطأ فيعطيك تحذيرات خاطئة False Positives، كالمترجم الذي يقول إن المتغير «قد يستخدم قبل أن يعطى قيمة» وهو ليس كذلك. وبعضها متساهل، لا يحذرك إلا مما هو متأكد منه فيفوته بعض الأخطاء False Negatives. ولا يوجد خيار ثالث يجمع الدقة الكاملة في الجهتين، وهذه ليست مشكلة في جودة الأداة، وإنما حد رياضي.

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

من القابلية إلى الكلفة: التعقيد Complexity

الآن نترك المسائل المستحيلة، وننتقل إلى المسائل الممكنة، ونسأل سؤالاً مختلفاً: كم يكلف الحل؟ وقد شرحنا في مقال الخوارزميات وتعقيد Big-O كيف نصف نمو الوقت مع حجم المدخل. وهنا يهمنا فرق واحد كبير: الفرق بين النمو متعدد الحدود Polynomial، مثل n² وn³، والنمو الأسي Exponential، مثل 2ⁿ وn!. والجدول التالي يبين الفرق بأرقام محسوبة، مع افتراض جهاز ينفذ مليار خطوة في الثانية:

nn²n³2ⁿn!
101001,0001,0243,628,800
204008,0001,048,576 (ميلي ثانية)2.4 × 10¹⁸ (قرابة 77 سنة)
3090027,0001.07 × 10⁹ (ثانية)2.7 × 10³²
502,500125,0001.1 × 10¹⁵ (13 يوماً)3.0 × 10⁶⁴
10010,0001,000,0001.3 × 10³⁰ (4 × 10¹³ سنة)9.3 × 10¹⁵⁷

لاحظ أن n³ عند مئة عنصر ما زال مليون خطوة، أي ميلي ثانية، بينما 2ⁿ عند نفس الحجم يحتاج أكثر من عمر الكون بآلاف المرات. ولهذا يعامل علماء الحاسب المسائل التي لها حل متعدد الحدود على أنها «سهلة» حتى لو كان الحل بطيئاً عملياً، ويعاملون المسائل التي لا يعرف لها إلا حل أسي على أنها «صعبة»، لأن الأجهزة الأسرع لا تنقذك: جهاز أسرع بألف مرة يضيف عشرة عناصر فقط إلى ما تستطيع حله بطريقة 2ⁿ.

مقارنة نمو الوقت: عند n تساوي 50 يحتاج n تربيع 2500 خطوة وn تكعيب 125 ألف خطوة، بينما 2 أس n يحتاج 13 يوماً بمليار خطوة في الثانية، وn مضروب يحتاج رقماً من 64 خانة، وجهاز أسرع بألف مرة يضيف عشرة عناصر فقط في الخوارزمية الأسية
في النمو الأسي لا ينقذك جهاز أسرع: ألف ضعف في السرعة تعني عشرة عناصر إضافية فقط

الصنف P والصنف NP: الحل مقابل التحقق

الصنف P هو كل مسائل نعم أو لا التي يوجد لها حل في وقت متعدد الحدود، مثل ترتيب قائمة، أو إيجاد أقصر طريق في خريطة بخوارزمية Dijkstra، أو معرفة هل الرقم أولي. والصنف NP هو كل المسائل التي إذا أعطاك أحد حلاً مقترحاً، تستطيع أن تتحقق من صحته في وقت متعدد الحدود. وهنا الفكرة كلها، وصفحة معهد Clay للرياضيات تلخصها في سؤال واحد: إذا كان من السهل التحقق من أن الحل صحيح، فهل من السهل أيضاً إيجاد الحل؟

ومثال من الحياة: جدول مناوبات لخمسين موظفاً مع قيود الإجازات والراحة بين المناوبات والمهارات المطلوبة في كل مناوبة. إذا أعطاك أحد جدولاً جاهزاً، فالتحقق منه سهل، تمر على كل قيد وتتأكد أنه محترم. أما إيجاد الجدول من الصفر فقد يحتاج تجربة عدد هائل من الاحتمالات. وكل مسألة في P هي أيضاً في NP، لأنك إذا استطعت أن تحل المسألة بسرعة فأنت تستطيع أن تتحقق من أي حل بأن تحلها وتقارن. والسؤال المفتوح هو العكس: هل كل مسألة يمكن التحقق منها بسرعة يمكن أيضاً حلها بسرعة؟ وهذا هو سؤال P = NP، وهو واحد من سبع مسائل خصص لها معهد Clay جائزة مليون دولار لكل منها، ولم يحله أحد حتى اليوم.

المسائل NP-Complete: إذا حللت واحدة حللت الكل

في 1971 نشر Stephen Cook ورقة The Complexity of Theorem-Proving Procedures، وأثبت فيها أن مسألة واحدة اسمها SAT لها خاصية غريبة: كل مسألة في NP يمكن تحويلها إليها في وقت متعدد الحدود. ومسألة SAT، واسمها الكامل مسألة قابلية الإرضاء Boolean Satisfiability، تسأل: لدينا صيغة منطقية فيها متغيرات كل منها صح أو خطأ، فهل توجد قيم للمتغيرات تجعل الصيغة كلها صحيحة؟ وبعد سنة نشر Richard Karp ورقة Reducibility among Combinatorial Problems وأثبت أن 21 مسألة مشهورة لها نفس الخاصية، منها تلوين الرسوم البيانية وحقيبة الظهر Knapsack والمسار الذي يمر بكل النقاط. وهذه المسائل تسمى NP-Complete، أي أنها أصعب مسائل NP: لو وجد أحد حلاً سريعاً لواحدة منها فقط، لصار عندنا حل سريع لكل مسائل NP، أي أن P = NP.

والتحويل Reduction هنا هو الفكرة الهندسية المهمة: أن تكتب مسألتك بلغة مسألة أخرى. فجدول المناوبات مثلاً يمكن كتابته كصيغة SAT، حيث المتغير «الموظف 7 يعمل في مناوبة الثلاثاء الليلية» صح أو خطأ، وكل قيد يصبح شرطاً منطقياً. وهذا ليس تمريناً نظرياً، فهناك برامج حل SAT Solvers يتنافس مطوروها كل سنة في مسابقة SAT، وتستخدمها أدوات تعرفها: مكتبة libsolv التي تحل اعتماديات الحزم في مديري حزم مثل zypper وdnf، ومدير الحزم في لغة Dart الذي يوثق خوارزمية الحل PubGrub الخاصة به، لأن اختيار إصدارات حزم متوافقة مع بعضها مسألة من نفس هذا النوع. وقد شرحنا مديري الحزم في مقال مديرو الحزم.

مختبر SAT: البحث الشامل Brute Force مقابل DPLL

لنرى الانفجار بأعيننا. كتبنا في sat.py مولداً لصيغ 3-SAT عشوائية، أي صيغ كل شرط فيها ثلاثة متغيرات، ثم طريقتين للحل. وثبتنا البذور العشوائية Seeds، فكل تشغيل يبني نفس الصيغ. وأهم ما في الملف:

def random_3sat(n, seed, ratio=4.26):
    rnd = random.Random(seed)
    return [tuple(v if rnd.random() < 0.5 else -v for v in rnd.sample(range(1, n + 1), 3)) for _ in range(round(n * ratio))]

def check(formula, assign):                       # assign[v] is True/False, index 1..n
    return all(any(assign[abs(l)] == (l > 0) for l in c) for c in formula)

def brute_force(formula, n):
    tried = 0
    for bits in product((False, True), repeat=n):
        tried += 1
        a = (None,) + bits
        if check(formula, a):
            return a, tried
    return None, tried

في الكود أعلاه لاحظ التالي:

  • كل شرط Clause ثلاثة أرقام، والرقم السالب يعني نفي المتغير، فالشرط (3, -7, 12) يعني «المتغير 3 صح، أو المتغير 7 خطأ، أو المتغير 12 صح».
  • عدد الشروط هو عدد المتغيرات مضروباً في 4.26، وسوف نشرح لماذا هذا الرقم بالذات بعد قليل.
  • الدالة check هي التحقق، وهي تمر على الشروط مرة واحدة، أي أن وقتها يتناسب مع حجم الصيغة، وهذا ما يجعل SAT في NP.
  • brute_force تجرب كل التوزيعات الممكنة، وعددها 2ⁿ.

والطريقة الثانية هي خوارزمية DPLL، التي تحمل أسماء Davis وPutnam وLogemann وLoveland، وهي أساس أغلب برامج حل SAT الحديثة. وفكرتها أن تختار متغيراً وتجرب له قيمة، ثم تبسط الصيغة، فإذا بقي شرط فيه متغير واحد فقيمته صارت إجبارية، وهذا ما يسمى نشر الوحدة Unit Propagation، وإذا وصلت إلى شرط فارغ فقد فشل هذا الفرع فترجع وتجرب القيمة الأخرى. والكود الكامل في الملف، وهو قرابة أربعين سطراً.

ولنأخذ مثالاً صغيراً لترى لماذا DPLL أسرع بكثير. لدينا ثلاثة شروط: (1 أو 2) و(ليس 1 أو 3) و(ليس 3). البحث الشامل يجرب ثمانية توزيعات للمتغيرات الثلاثة. أما DPLL فتبدأ بنشر الوحدة: الشرط الثالث فيه متغير واحد، فالمتغير 3 يجب أن يكون خطأ دون أي تجربة، وعندها يصبح الشرط الثاني (ليس 1) وحده، فالمتغير 1 خطأ إجبارياً، فيصبح الشرط الأول (2) وحده، فالمتغير 2 صح. وصلنا إلى الحل دون أن نخمن مرة واحدة. وفي الصيغ الحقيقية لا يكفي نشر الوحدة وحده، فتخمن الخوارزمية قيمة متغير، وتختار في نسختنا الحرف الأكثر تكراراً في الشروط المتبقية، ثم تنشر النتائج، فإذا وصلت إلى تناقض رجعت وجربت العكس. وكل تخمين صحيح يوفر نصف شجرة البحث، وكل نشر يقطع فروعاً كاملة دون تجربتها، ولهذا كان عدد الاستدعاءات في المختبر عشرات بدلاً من ملايين. ولكن في أسوأ حالة قد تضطر الخوارزمية إلى الرجوع في كل مستوى، فتعود شجرة البحث إلى حجمها الأسي.

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

  n clauses         2^n  brute tried  brute s dpll calls  dpll s
 12      51       4,096        4,096     0.04         11   0.001
 14      60      16,384       16,384     0.19         19   0.001
 16      68      65,536       65,536     0.43         13   0.001
 18      77     262,144      262,144     1.57         11   0.001
 20      85   1,048,576    1,048,576     9.45         37   0.003
 22      94   4,194,304    4,194,304    30.89         19   0.002

ولنقرأ الجدول:

  • العمود brute tried يساوي 2^n تماماً في كل سطر، أي أن البحث الشامل جرب كل التوزيعات ليتأكد أنه لا يوجد حل.
  • كل متغيرين إضافيين يضربان العمل في 4، وكان يجب أن يضربا الوقت في 4 أيضاً، ولكن الوقت قفز من 1.57 إلى 9.45 ثانية بين 18 و20 متغيراً، أي ستة أضعاف. والسبب أن الجهاز كان يشغل أعمالاً أخرى في نفس الوقت، فلا تقرأ كل رقم وحده، وانظر إلى الاتجاه.
  • عند 22 متغيراً فقط احتاج البحث الشامل 31 ثانية، ومع نفس الاتجاه سوف يحتاج 30 متغيراً قرابة ساعتين، و40 متغيراً قرابة 94 يوماً، و60 متغيراً قرابة 270 ألف سنة.
  • DPLL حسمت نفس الصيغ في أجزاء من الميلي ثانية، بعشرات الاستدعاءات فقط بدلاً من الملايين.
أعمدة وقت البحث الشامل في SAT تتضاعف أربع مرات تقريباً مع كل متغيرين من 0.04 ثانية عند 12 متغيراً إلى 31 ثانية عند 22 متغيراً، بينما DPLL تحسم نفس الصيغ في أقل من 3 ميلي ثانية، ثم جدول DPLL على صيغ أكبر حيث الوسيط 0.02 ثانية عند 50 متغيراً و0.16 عند 100 و6.9 ثانية عند 125 متغيراً وأسوأ صيغة 19 ثانية، والتحقق من الحل أقل من نصف ميلي ثانية دائماً
البحث الشامل ينفجر عند 22 متغيراً، وDPLL تؤخر الانفجار ولا تلغيه، والتحقق يبقى أقل من ميلي ثانية

فهل حلت DPLL المشكلة؟ لنعطها صيغاً أكبر، خمس صيغ لكل حجم، ونقيس الوسيط والأسوأ وزمن التحقق من الحل عندما يوجد:

   n clauses SAT/5 dpll calls (median) dpll s (median) dpll s (max) check ms
  50     213     3                  75           0.020        0.065    0.166
  75     320     4                 151           0.059        0.401    0.368
 100     426     3                 343           0.156        2.729    0.409
 125     532     4               7,457           6.944       19.117    0.414
  • العمود SAT/5 يقول كم صيغة من الخمس لها حل، وهو قرابة النصف في كل حجم.
  • الوسيط في عدد الاستدعاءات بقي صغيراً حتى 100 متغير، ثم قفز من 343 إلى 7,457 عند 125 متغيراً، وأسوأ صيغة أخذت 19 ثانية.
  • والعمود الأخير هو قلب القصة: التحقق من الحل، عندما وجد، أخذ أقل من نصف ميلي ثانية في كل الأحجام. أي أن الحل نفسه أخذ حتى 19 ثانية، والتحقق منه أقل من ميلي ثانية، وهذا بالضبط الفرق بين «الإيجاد» و«التحقق» الذي يعرف NP.

وهنا المشكلة الحقيقية التي واجهناها: في أول محاولة أضفنا أحجام 150 و200 متغيراً، وتركنا التشغيل يعمل، وبعد أربع وعشرين دقيقة لم ينته، ولم يطبع حتى السطر الأول. والسبب الثاني كان بسيطاً: Python تجمع المخرج في ذاكرة مؤقتة Buffer عندما يذهب إلى ملف بدلاً من الشاشة، فلم نر حتى النتائج التي اكتملت، والحل هو الخيار python3 -u الذي يطبع كل سطر فوراً، وهو مكتوب الآن في run.sh. أما السبب الأول فهو موضوع هذا المقال: خوارزمية أذكى بكثير من البحث الشامل، ومع ذلك فإن 200 متغير عند هذه النسبة كانت أكثر مما تحتمله نسختنا البسيطة. والبرامج الحديثة لحل SAT تحل صيغاً فيها ملايين المتغيرات من مسائل حقيقية، لأنها تضيف تعلم الشروط من الفشل وإعادة التشغيل الذكية، ولكنها تبقى أسية في أسوأ حالة.

ماذا يحدث إذا غيرنا عدد الشروط؟ انتقال الطور Phase Transition

لماذا 4.26 شرطاً لكل متغير؟ لنجرب التغيير بأنفسنا: نثبت عدد المتغيرات عند 100، ونغير النسبة بين 2 و6، والمخرج كما يلي:

n=100
ratio clauses SAT/5 dpll calls (median) dpll s (median) dpll s (max)
  2.0     200     5                  51           0.005        0.007
  3.0     300     5                  41           0.007        0.007
 4.26     426     3                 343           0.244        3.622
  5.0     500     0               2,011           1.951        3.764
  6.0     600     0                 499           0.541        1.289
منحنى انتقال الطور لمئة متغير: عند نسبة 2 و3 شروط لكل متغير كل الصيغ لها حل وDPLL تنتهي في 5 إلى 7 ميلي ثانية، وعند 4.26 ثلاث صيغ من خمس لها حل والوسيط 0.24 ثانية، وعند 5 لا حل لأي صيغة والوسيط 1.95 ثانية، وعند 6 لا حل والوسيط 0.54 ثانية، فالصيغ الأصعب في المنطقة التي ينتقل فيها الجواب من نعم إلى لا
القليل من الشروط يعني حلاً سهلاً، والكثير منها يعني تناقضاً يظهر بسرعة، والصعب في المنتصف
  • عند نسبة 2 و3 كانت كل الصيغ الخمس لها حل، وانتهت DPLL في أقل من 10 ميلي ثانية، لأن القيود قليلة وأي اختيار معقول ينجح.
  • عند 4.26 صارت ثلاث صيغ فقط لها حل، وقفز الوقت.
  • عند 5 لم يعد لأي صيغة حل، وكان الوقت في أعلاه، لأن الخوارزمية يجب أن تثبت أنه لا يوجد حل، والقيود ما زالت غير كافية لتظهر التناقض بسرعة.
  • عند 6 نزل الوقت مرة أخرى، لأن القيود الكثيرة تتناقض بسرعة.

وهذا ما يسمى انتقال الطور Phase Transition في SAT: الصيغ الأصعب تقع في المنطقة التي ينتقل فيها احتمال وجود حل من «غالباً نعم» إلى «غالباً لا». ولهذا تصنف مجموعة SATLIB المعروفة صيغها العشوائية الصعبة على أنها من «منطقة انتقال الطور»، وأكبرها فيه 250 متغيراً و1,065 شرطاً، أي 4.26 لكل متغير. والدرس العملي أن صعوبة المسألة لا تعتمد على حجمها فقط، وإنما على شكلها، فجدول مناوبات بقيود قليلة أو قيود كثيرة متناقضة قد يحل في ثوان، وجدول على حافة الإمكان قد لا يحل أبداً.

مختبر البائع المتجول Travelling Salesman Problem

الآن نعود إلى مندوب التوصيل في أول المقال. مسألة البائع المتجول TSP تسأل: لدينا مدن والمسافات بينها، فما أقصر جولة تمر بكل مدينة مرة واحدة وترجع إلى البداية؟ وصيغتها كسؤال نعم أو لا، «هل توجد جولة أقصر من طول معين؟»، هي NP-Complete. وكتبنا في tsp.py ثلاث طرق، على نقاط عشوائية ثابتة البذرة في مربع طول ضلعه 100:

  • البحث الشامل: نثبت المدينة الأولى ونجرب كل ترتيبات الباقي، وعددها (n-1)!.
  • البرمجة الديناميكية Dynamic Programming بطريقة Held وKarp من 1962: نحفظ لكل مجموعة من المدن ولكل مدينة أخيرة أقصر مسار، فيصبح الوقت n² · 2ⁿ بدلاً من n!، وهو ما زال أسياً ولكنه أفضل بكثير.
  • حل تقريبي Heuristic: نبدأ بأقرب مدينة لم نزرها Nearest Neighbour، ثم نحسن الجولة بقلب أي جزء منها يقصرها، وهي طريقة 2-opt، حتى لا يبقى تحسين. وهذا لا يضمن الأفضل، ولكنه سريع جداً.

والمخرج للبحث الشامل كما يلي:

n=8   tours=       5,040  brute=     0.01 s  best=280.85
n=9   tours=      40,320  brute=     0.11 s  best=284.93
n=10  tours=     362,880  brute=     0.75 s  best=305.93
n=11  tours=   3,628,800  brute=    17.39 s  best=357.78
n=12  tours=  39,916,800  brute=   103.78 s  best=279.79

كل مدينة إضافية ضربت عدد الجولات في عددها، فمن 11 إلى 12 مدينة صار العدد 11 ضعفاً، وأخذت 12 مدينة 104 ثوان، أي قرابة 2.6 ميكروثانية لكل جولة. وبنفس السرعة سوف تحتاج 13 مدينة قرابة 21 دقيقة، و15 مدينة قرابة يومين ونصف، و20 مدينة قرابة عشرة آلاف سنة. ولاحظ أن الجولة الأفضل لاثنتي عشرة مدينة كانت أقصر من جولة عشر مدن، والسبب أن كل حجم له نقاط عشوائية مختلفة. ثم المخرج للبرمجة الديناميكية والحل التقريبي معاً:

n=10  held-karp=    0.01 s  best=305.93  |  heuristic=    0.3 ms  len=305.93  gap= 0.00%
n=12  held-karp=    0.06 s  best=279.79  |  heuristic=    0.1 ms  len=279.79  gap= 0.00%
n=14  held-karp=    0.26 s  best=301.32  |  heuristic=    0.1 ms  len=302.59  gap= 0.42%
n=16  held-karp=    1.27 s  best=326.56  |  heuristic=    0.2 ms  len=326.56  gap=-0.00%
n=18  held-karp=    7.54 s  best=327.99  |  heuristic=    0.2 ms  len=327.99  gap= 0.00%
  • Held-Karp وجدت نفس الجولة الأفضل التي وجدها البحث الشامل لعشر واثنتي عشرة مدينة، في 0.06 ثانية بدلاً من 104 ثوان.
  • ولكنها أيضاً تنفجر: كل مدينتين إضافيتين تضربان الوقت في خمسة تقريباً، فـ 18 مدينة أخذت 7.5 ثانية، وبنفس الاتجاه سوف تحتاج 30 مدينة قرابة يوم كامل، مع ذاكرة تحفظ ملايين المسارات الجزئية.
  • الحل التقريبي أخذ أقل من ميلي ثانية، ووجد الجولة الأفضل نفسها في أربع حالات من خمس، وفي الحالة الخامسة كانت جولته أطول بـ 0.42% فقط. أما -0.00% فهو فرق صغير جداً بين طريقتين لجمع نفس الأرقام العشرية، أي أن الجولتين متساويتان، وقد شرحنا سبب هذه الفروق في مقال الأرقام العشرية Floating Point من الداخل.

ثم أعطينا الحل التقريبي أحجاماً لا يمكن حلها بدقة بأي من الطريقتين:

n=100   heuristic=   0.01 s  len=839.20
n=200   heuristic=   0.05 s  len=1192.16
n=400   heuristic=   0.17 s  len=1609.88
n=800   heuristic=   1.64 s  len=2257.93
ثلاث طرق للبائع المتجول: البحث الشامل 0.75 ثانية لعشر مدن و104 ثوان لاثنتي عشرة مدينة، وHeld-Karp 0.06 ثانية لاثنتي عشرة مدينة و7.5 ثانية لثماني عشرة، والحل التقريبي أقل من ميلي ثانية حتى ثماني عشرة مدينة بفرق أقصاه 0.42% عن الأفضل، و1.6 ثانية لثمانمئة مدينة
الدقة الكاملة تتوقف عند عشرات المدن، والحل التقريبي يصل إلى المئات في ثانية بفرق صغير عن الأفضل

ثمانمئة مدينة في 1.6 ثانية. ونحن لا نعرف كم تبعد هذه الجولات عن الأفضل، لأننا لا نستطيع حساب الأفضل، ولكن ما رأيناه في الأحجام الصغيرة يعطينا ثقة معقولة. وهذا هو الطريق الذي تسلكه شركات التوصيل والطيران في الواقع: حلول تقريبية جيدة بسرعة، بدلاً من الحل الأفضل الذي لا يصل أبداً. وفي الجهة الأخرى، تبين مجموعة أبحاث TSP في جامعة Waterloo أن الحل الدقيق لمسائل كبيرة جداً ممكن بأدوات متخصصة، فقد حل فريق منهم مسألة pla85900 التي فيها 85,900 مدينة حلاً مثبتاً أنه الأفضل في 2005 و2006 باستخدام برنامج Concorde. وهذا لا يناقض ما سبق، فالمسألة صعبة في أسوأ حالة، أما المسائل الحقيقية فلها بنية تستغلها الأدوات الذكية.

لماذا يهمك سؤال P مقابل NP؟

لو أثبت أحد يوماً أن P = NP بطريقة عملية، فسوف يتغير الكثير: جدولة المصانع، والتوزيع، وتصميم الدوائر الإلكترونية، والبحث عن البراهين الرياضية. ولكن أيضاً جزء كبير من التشفير Encryption الذي نعتمد عليه، لأن التشفير يعتمد على مسائل يسهل التحقق من حلها ويصعب إيجاده، مثل إيجاد عوامل رقم كبير، التي شرحناها في مقال الرياضيات خلف RSA. ولاحظ الدقة هنا: تحليل الرقم إلى عوامل مسألة في NP، ولكن لم يثبت أحد أنها NP-Complete، فقد تكون أسهل من SAT دون أن نعرف، وأمان RSA يعتمد على صعوبتها هي تحديداً، لا على سؤال P مقابل NP وحده.

وأغلب الباحثين يعتقدون أن P ≠ NP، أي أن هناك مسائل يسهل التحقق منها ويستحيل حلها بسرعة، ولكن هذا اعتقاد وليس برهاناً. وبالنسبة لك كمهندس، فالنتيجة العملية واحدة في الحالتين حتى يحل السؤال: عندما تعرف أن مسألتك NP-Complete فلا تبحث عن خوارزمية سريعة دقيقة لكل الحالات، فقد بحث عنها آلاف الأشخاص قبلك خمسين سنة، وإنما اختر من الطرق العملية في القسم التالي.

ماذا تفعل عملياً؟ جدول القرار Decision Table

حالتكالطريقةمثال من المختبر
الحجم صغير جداً ومضمون أن يبقى صغيراًالبحث الشامل، فهو أبسط وأصححتى 10 مدن في أقل من ثانية
الحجم متوسط وتحتاج الأفضلبرمجة ديناميكية أو تفرع وتقليم Branch and BoundHeld-Karp حتى 18 مدينة في 7.5 ثانية
قيود كثيرة من نوع نعم أو لاحولها إلى SAT أو برمجة خطية بأعداد صحيحة واستخدم برنامج حل جاهزاًDPLL البسيطة حسمت 100 متغير في أقل من أربع ثوان
الحجم كبير ويكفيك حل جيدحل تقريبي Heuristic مع تحسين محلي800 مدينة في 1.6 ثانية
لا تعرف هل البرنامج سوف ينتهيمهلة Timeout وميزانية خطوات، واقبل الإجابة «لا أعرف»الدالة simulate
تحتاج أداة تحليل للكوداقبل أنها سوف تخطئ في جهة، واختر الجهة الأقل ضرراًمبرهنة Rice

أخطاء شائعة Common Mistakes

  • اختبار الخوارزمية الأسية على مدخل صغير ثم نشرها: عشر مدن في ثانية لا تعني عشرين مدينة في ثانيتين، وإنما في عشرة آلاف سنة.
  • البحث عن حل دقيق وسريع لمسألة NP-Complete قبل أن تعرف أنها كذلك: ابحث أولاً هل مسألتك معروفة، فقد تجد اسمها في قائمة Karp أو في كتب الخوارزميات.
  • كتابة برنامج حل خاص بدلاً من استخدام برنامج حل جاهز: نسختنا من DPLL أربعون سطراً وتوقفت عند 200 متغير، والبرامج المتخصصة سنوات من العمل.
  • الحكم على صعوبة المسألة من حجمها وحده: رأيت أن 100 متغير عند نسبة 3 حلت في 7 ميلي ثانية، وعند نسبة 5 في ثانيتين.
  • انتظار أداة تحليل لا تخطئ: مبرهنة Rice تقول إنها غير موجودة، فاقرأ التحذيرات بعقل.
  • تشغيل التجارب الطويلة دون مخرج فوري: python3 -u أو تفريغ المخرج دورياً، حتى ترى النتائج التي اكتملت قبل أن توقف التشغيل.
  • غياب المهلة في أي عملية قد لا تنتهي: من استدعاء الشبكة إلى حلقة البحث في برنامجك.

قائمة تحقق Checklist عندما تواجه مسألة بحث

  • ما حجم المدخل اليوم، وما حجمه بعد سنة؟
  • هل الحل البسيط أسي؟ احسب وقته عند الحجم القادم قبل أن تكتبه.
  • هل مسألتك معروفة باسم مثل SAT أو TSP أو Knapsack أو تلوين الرسوم؟
  • هل تحتاج الحل الأفضل فعلاً، أم يكفيك حل جيد مع حد معروف للفرق؟
  • هل يوجد برنامج حل جاهز، مثل SAT Solver أو برنامج برمجة خطية، يمكنك تحويل مسألتك إليه؟
  • هل وضعت مهلة وميزانية لكل بحث، وهل تعرف ماذا يفعل النظام عندما تنتهي؟
  • هل يمكنك التحقق من الحل الناتج بسرعة قبل أن تستخدمه؟

حذف المختبر Cleanup

كل التجارب عملت في Containers مؤقتة بالخيار --rm، فيكفي حذف الـ Image:

docker rmi scp6-cpx

الخلاصة

  • مشكلة التوقف غير قابلة للحسم: لا يوجد برنامج يقرر لكل برنامج هل سوف يتوقف، والبرهان بالقطر يبني لكل محاولة برنامجاً يعاكسها، كما رأيت مع الدوال الأربع في المختبر.
  • مبرهنة Rice توسع النتيجة إلى كل خاصية سلوكية للبرامج، ولهذا تخطئ أدوات التحليل دائماً في جهة ما، ولهذا نستخدم المهلة.
  • الصنف P مسائل يمكن حلها بسرعة، والصنف NP مسائل يمكن التحقق من حلها بسرعة، والمسائل NP-Complete هي أصعبها، وسؤال P = NP مفتوح.
  • في المختبر احتاج البحث الشامل في SAT إلى 31 ثانية لاثنين وعشرين متغيراً، وDPLL أخرت الانفجار إلى قرابة 125 متغيراً، والتحقق من الحل بقي أقل من نصف ميلي ثانية.
  • أصعب صيغ SAT العشوائية في منطقة انتقال الطور، حيث يتغير الجواب من نعم إلى لا.
  • في البائع المتجول توقف البحث الشامل عند 12 مدينة وHeld-Karp عند 18، بينما وجد الحل التقريبي جولات بفرق أقصاه 0.42% عن الأفضل، ووصل إلى 800 مدينة في 1.6 ثانية.

ولتكمل هذه المرحلة اقرأ ابن مفسراً صغيراً بيدك لترى كيف يقرأ برنامج برنامجاً آخر، والخوارزميات وتعقيد Big-O إذا أردت مراجعة النمو والتعقيد، والرياضيات خلف RSA لترى كيف يبنى الأمان على مسائل صعبة، وفضاء النواة واستدعاءات النظام والعمليات وجدولة المعالج من نفس المرحلة.

سجل التحديثات

  • أكتوبر 2026: كتابة المقال وتشغيل كل التجارب على Python 3.13.5 في Container من debian:trixie-slim بمعالج واحد.
نشرة عرب رووت | ArabRoot

معرفة تستحق مكاناً في بريدك.

مقالات مختارة وأدوات مفيدة وأفكار لمشروعك القادم، في رسالة واحدة كل أسبوع.

يمكنك إلغاء الاشتراك متى شئت. الخصوصية

تم استلام طلبك. افتح بريدك واضغط رابط التأكيد لإتمام الاشتراك.