ما هي مشكلة ساعي البريد الصيني (Chinese Postman Problem) في الخوارزميات؟
مشكلة ساعي البريد الصيني (Chinese Postman Problem) هي مسألة في نظرية الرسوم البيانية تبحث عن أقصر مسار مغلق يمرّ على كل حافة (ضلع) في الرسم البياني مرة واحدة على الأقل، ثم يعود إلى نقطة الانطلاق. تخيّل ساعي بريد عليه أن يسلك كل شارع في حيّه ثم يرجع إلى المكتب: ما أقصر طريق يحقق ذلك بأقل مسافة مكرَّرة؟ هذا بالضبط جوهر المشكلة. وقد سُميت بهذا الاسم نسبةً إلى عالم الرياضيات الصيني قوان ميقو (Guan Meigu) الذي صاغها عام 1962، فكلمة "الصيني" تشير إلى جنسيته لا إلى أي شيء آخر.
الفكرة الأساسية: الحواف لا العُقد
أول ما يجب استيعابه أن هذه المشكلة تهتم بتغطية كل الحواف، وليس بزيارة كل العقد. هنا يقع الخلط الأكثر شيوعًا؛ إذ يظنّ كثيرون أنها تشبه "مشكلة البائع المتجول" (TSP)، لكن البائع المتجول يزور كل عقدة مرة واحدة، بينما ساعي البريد يمرّ على كل طريق (حافة). الفرق جوهري وينعكس مباشرةً على صعوبة الحل كما سنرى.
الرسم البياني هنا هو مجموعة من العقد (تمثّل التقاطعات) تربط بينها حواف (تمثّل الشوارع)، ولكل حافة وزن يعبّر عن طولها أو تكلفتها.
متى يكون الحل سهلًا؟ مسار أويلر
إذا كان الرسم البياني يحوي "دورة أويلر" (Eulerian circuit)، فالمشكلة محلولة مباشرةً: المسار الأمثل هو دورة أويلر نفسها، وتكلفته تساوي مجموع أوزان كل الحواف من دون أي تكرار. ويتحقق وجود دورة أويلر بشرطين اثنين:
- أن يكون الرسم متصلًا (يمكن الوصول من أي عقدة إلى غيرها).
- أن تكون درجة كل عقدة زوجية (عدد الحواف المتصلة بها زوجي).
عندها يكفي استخراج الدورة بخوارزمية مثل هيرهولتزر (Hierholzer) أو فلوري (Fleury)، علمًا أن هيرهولتزر أسرع وأكفأ. لاحظ أن هذه الخوارزميات تجد دورة أويلر فقط، ولا "تحلّ" المشكلة بمفردها عندما تكون بعض الدرجات فردية.
متى تصبح المشكلة أصعب؟ العُقد ذات الدرجة الفردية
في الواقع نادرًا ما تكون كل الدرجات زوجية. وأي عقدة درجتها فردية تعني أن الساعي سيُضطر إلى المرور على بعض الشوارع أكثر من مرة. وبحسب "مبرهنة المصافحة" فإن عدد العقد ذات الدرجة الفردية زوجي دائمًا (2، 4، 6...).
يقوم الحل الأمثل على تكرار أقل قدر ممكن من الحواف لتحويل كل الدرجات إلى زوجية. وخطوات الحل للرسم غير الموجَّه هي:
- حدِّد كل العقد ذات الدرجة الفردية.
- احسب أقصر مسافة بين كل زوج منها (مثلًا بخوارزمية ديكسترا أو فلويد-وارشال).
- أوجِد التزاوج التام ذا الوزن الأدنى (minimum-weight perfect matching) بين هذه العقد، أي اقرنها أزواجًا بحيث يكون مجموع مسافات الأزواج أصغر ما يمكن.
- ضاعِف (كرِّر) الحواف على المسارات المختارة، فتصبح درجة كل عقدة زوجية.
- استخرج دورة أويلر في الرسم الناتج، وهي الحل الأمثل.
التكلفة النهائية = مجموع أوزان كل الحواف + مجموع أوزان المسارات المكرَّرة.
الصعوبة الحسابية تتغيّر بحسب نوع الرسم
ليست كل صور المشكلة متساوية في الصعوبة، وهذه نقطة يغفلها كثير من الشروح:
| نوع الرسم | قابلية الحل | كيف يُحل |
|---|---|---|
| غير موجَّه | زمن كثير الحدود | عبر التزاوج (خوارزمية إدموندز/بلوسوم) |
| موجَّه | زمن كثير الحدود | عبر تدفق أدنى تكلفة |
| مختلط (حواف موجهة وغير موجهة معًا) | NP-صعبة | لا خوارزمية كفؤة معروفة |
هذا التباين مهم: النسخة غير الموجَّهة تُحلّ بكفاءة، على عكس مشكلة البائع المتجول التي تبقى صعبة (NP).
مقارنة سريعة: ساعي البريد أم البائع المتجول؟
| البُعد | ساعي البريد الصيني (CPP) | البائع المتجول (TSP) |
|---|---|---|
| ما الذي يُغطّى؟ | كل الحواف (الشوارع) | كل العقد (المدن) |
| التكرار | يُسمح بتكرار الحواف | كل عقدة مرة واحدة فقط |
| الصعوبة (رسم غير موجَّه) | سهلة نسبيًا (زمن كثير الحدود) | صعبة (NP-صعبة) |
| مثال تطبيقي | جمع النفايات، كنس الشوارع | جدولة زيارات، تصميم لوحات الدوائر |
تطبيقات عملية
- تخطيط مسارات جمع النفايات وكنس الشوارع.
- إزالة الثلوج وصيانة الطرق.
- قراءة عدادات الكهرباء والماء.
- فحص خطوط الأنابيب وشبكات الاتصالات.
- تسيير الطائرات المسيّرة لمسح منطقة بأكملها.
نصيحة عملية: قبل أن تطبّق الخوارزمية المعقّدة، تحقّق أولًا إن كانت درجات كل العقد زوجية. إن كانت كذلك فلا داعي لأي حساب إضافي، ويكون مجموع أوزان الحواف كلها هو جوابك مباشرةً. هذه الخطوة البسيطة توفّر جهدًا كبيرًا في المسائل التطبيقية.
الأسئلة الشائعة
لماذا سُميت "الصينية"؟ نسبةً إلى مبتكرها عالم الرياضيات الصيني قوان ميقو الذي طرحها عام 1962، وليس لأي خاصية جغرافية في المسألة.
ما الفرق بينها وبين مسار أويلر؟ مسار أويلر حالة خاصة مثالية تتحقق حين تكون كل الدرجات زوجية. أما مشكلة ساعي البريد فتُعمّم الفكرة لتشمل الحالة الواقعية التي لا توجد فيها دورة أويلر، فتحسب أقل تكرار لازم.
هل تنطبق على الرسوم الموجَّهة؟ نعم، وتظل قابلة للحل في زمن كثير الحدود عبر خوارزميات تدفق أدنى تكلفة، لكن الرسوم المختلطة تصبح NP-صعبة.
هل يوجد حل دائمًا؟ نعم، طالما كان الرسم البياني متصلًا. أما إن كان مفصولًا إلى أجزاء لا رابط بينها فلا يمكن لمسار واحد أن يغطّي كل الحواف.