الدرس الثالث (٢)
انظر إلى النصوص والأكواد البرمجية هنا. يعرض الكود دالة برمجية متكاملة لبرمجة الأعداد الصحيحة المختلطة لحل مشكلة البائع المتجول باستخدام مكتبة mip. في الجزء العلوي، يتم وضع الشروط الرياضية والقيود، مثل قيود الوصول والانتقال بين المواقع، حيث يضمن الكود أن يكون مجموع المتغيرات أكبر من أو يساوي واحداً عند الانتقال من موقع لآخر. انظر إلى دالة MIP_solver، فهي تبدأ بإنشاء نموذج كالتالي: solver = Model()، ثم تضيف متغيرات القرار الثنائية عبر var_type = BINARY لتحديد ما إذا كان الانتقال بين الموقعين مشمولاً في المسار أم لا. بعد ذلك، تُعرّف دالة الهدف عبر minimizing لحساب أقل مسافة ممكنة، وتُضاف قيود الوصول والمغادرة لكل موقع باستخدام xsum لضمان زيارة كل موقع مرة واحدة فقط ومغادرته مرة واحدة فقط، مع تطبيق قيود الاتصال لمنع الحلقات غير المرغوبة باستخدام متغيرات إضافية y.
يقوم الدرس على حل مشكلة البائع المتجول باستخدام خوارزمية البرمجة الرياضية وتحديداً برمجة الأعداد الصحيحة المختلطة عبر لغة بايثون. تتلخص الفكرة في نمذجة قيود الاتصال رياضياً لإيجاد أقصر مسار يزور كل موقع مرة واحدة ويعود لموقع البدء، مع مقارنة أداء هذا الأسلوب الدقيق بخوارزمية القوة المفرطة. فلو كان لديك 20 موقعاً، فإن القوة المفرطة تنتج طريقاً، وهي مساحة هائلة تستغرق وقتاً طويلاً للحساب، بينما تجد البرمجة الرياضية الحل الأمثل بكفاءة أكبر، رغم أنها تتطلب قيودا رياضية دقيقة ودوال موضوعية.
الفكرة الأساسية
تعتمد الفكرة على استخدام برمجة الأعداد الصحيحة المختلطة لحل مشكلة البائع المتجول بشكل دقيق ومثالي عبر كتابة دالة برمجية تنظم الانتقالات بين المواقع.
الشرح
تتطلب مشكلة البائع المتجول إيجاد أقصر مسار يزور كل موقع مرة واحدة ويعود إلى نقطة البدء. لحل ذلك، نستخدم مكتبات البرمجة الرياضية في لغة بايثون لبناء نموذج حل يشتمل على دالة موضوعية لتقليل المسافة، بالإضافة إلى قيود الوصول والانتقال. نحدد متغيرات القرار الثنائية للإشارة إلى الانتقال من موقع إلى آخر، ومتغيرات صحيحة إضافية لمنع تكوين حلقات فرعية لا تشمل موقع الانطلاق والتوقف. عند تطبيق خوارزمية برمجة الأعداد الصحيحة المختلطة لعدد كبير من المواقع، نلاحظ أنها تعطي الحل الأمثل بنسبة مئة بالمئة، وتتفوق على خوارزمية القوة المفرطة في السرعة مع مجموعات البيانات الكبيرة، رغم أنها تتطلب فهماً قوياً للنماذج والقيود الرياضية.
مثال محلول خطوة بخطوة
خذ مثلاً طريقاً يتكون من 4 مواقع بالترتيب . يتطلب الحل الصحيح ضبط قيم المتغيرات الثنائية لتكون إما أو , وتطبيق قيود الاتصال التي تشمل موقع الانطلاق والتوقف. يتم التعبير عن الدالة الموضوعية رياضياً عبر تجميع ناتج ضرب المسافة في متغير الانتقال لجميع المسارات، ثم إضافة قيود الوصول والمغادرة لكل موقع لضمان زيارته مرة واحدة فقط.
أخطاء شائعة
الاعتقاد بأن خوارزمية القوة المفرطة أسرع للبيانات الكبيرة بينما هي أبطأ بكثير بسبب عدد الطرق الهائل الناتج عن حساب المضروب. غياب قيود الاتصال الصحيحة التي تمنع تكون حلقات منفصلة عن نقطة البدء.
سؤالان للتدريب مع الإجابة
السؤال الأول: ما ميزات وعيوب أسلوب برمجة الأعداد الصحيحة المختلطة في حل مشكلات التحسين؟ الإجابة: الميزات هي إيجاد الحل الأمثل بنسبة مئة بالمئة للنسخ والسرعة مقارنة بالقوة المفرطة مع مجموعات البيانات الكبيرة. العيوب هي تطلبها قيودا رياضية خاصة، وتكون بطيئة جداً بالنسبة لمجموعات البيانات الكبيرة مقارنة بالأسلوب الاستدلالي. السؤال الثاني: لماذا يرتفع عدد الطرق الممكنة بشكل مذهل عندما ننتقل إلى نسخ أكبر مثل 20 موقعاً في مشكلة البائع المتجول؟ الإجابة: لأن عدد الطرق يساوي مضروب عدد المواقع مطروحاً منه واحد، فمثلاً لنسخة 20 موقعاً يكون عدد الطرق وهو عدد هائل يفوق قدرات أسلوب القوة المفرطة بكثير.