مشكلة ساعي البريد الصيني

في نظرية المخططات والتحسين التوافقي ، تُعرف مسألة مسار غوان ، أو مسألة ساعي البريد الصيني ، أو جولة ساعي البريد، أو مسألة فحص المسار، بأنها إيجاد أقصر مسار مغلق أو دائرة تمر بكل حافة من حواف مخطط غير موجه (متصل) مرة واحدة على الأقل. عندما يحتوي المخطط على دائرة أويلرية (مسار مغلق يغطي كل حافة مرة واحدة)، فإن هذه الدائرة تُعد حلاً أمثل. وإلا، فإن مسألة التحسين هي إيجاد أقل عدد من حواف المخطط التي يجب تكرارها (أو مجموعة الحواف ذات أقل وزن إجمالي ممكن) بحيث يحتوي المخطط المتعدد الناتج على دائرة أويلرية. ^{[ 1 ]} يمكن حل هذه المسألة في وقت متعدد الحدود ، ^{[ 2 ]} على عكس مسألة البائع المتجول التي تُعد من المسائل الصعبة حسابيًا (NP-hard) . ^{[ 3 ]} وتختلف هذه المسألة عن مسألة البائع المتجول في أن البائع المتجول لا يمكنه تكرار زيارة العقد، وليس عليه زيارة كل حافة.

درس عالم الرياضيات الصيني ميغو غوان هذه المسألة لأول مرة عام 1960، وتُرجمت ورقته البحثية الصينية إلى الإنجليزية عام 1962. ^{[ 4 ]} وقد سُميت المسألة في الأصل "مسألة ساعي البريد الصيني" تكريمًا له؛ وتُنسب مصادر مختلفة تسميتها إما إلى آلان ج. غولدمان أو جاك إدموندز ، وكلاهما كانا يعملان في المكتب الوطني الأمريكي للمعايير في ذلك الوقت. ^{[ 5 ] [ 6 ]}

تأخذ التعميمات كمدخلات أي مجموعة T من الرؤوس ذات عدد زوجي، ويجب أن تُنتج كمخرجات مجموعة حواف ذات وزن أدنى في الرسم البياني، بحيث تكون رؤوسها ذات الدرجة الفردية هي نفسها رؤوس المجموعة T. تُسمى هذه المخرجات " وصلة T" . هذه المسألة، مسألة وصلة T ، قابلة للحل أيضًا في وقت متعدد الحدود باستخدام نفس الأسلوب المُستخدم لحل مسألة ساعي البريد.

يمكن حل مشكلة فحص المسار غير الموجه في وقت متعدد الحدود باستخدام خوارزمية تعتمد على مفهوم الربط T. لنفترض أن T هي مجموعة رؤوس في رسم بياني. تُسمى مجموعة الحواف J ربط T إذا كانت مجموعة الرؤوس التي لها عدد فردي من الحواف المتصلة بـ J هي بالضبط المجموعة T. يوجد ربط T عندما يحتوي كل مكون متصل من الرسم البياني على عدد زوجي من الرؤوس في T. تكمن مشكلة الربط T في إيجاد ربط T بأقل عدد ممكن من الحواف أو بأقل وزن إجمالي ممكن.

لأي T ، فإن أصغر وصلة T (إن وجدت) تتكون بالضرورة من${\displaystyle {\tfrac {1}{2}}|T|}$المسارات التي تربط رؤوس T في أزواج. ستكون هذه المسارات بحيث يكون طولها الإجمالي أو وزنها الإجمالي أصغر ما يمكن. في الحل الأمثل، لا يشترك أي مسارين من هذه المسارات في أي حافة، ولكن قد يشتركان في بعض الرؤوس. يمكن الحصول على وصلة T- الدنيا من خلال إنشاء رسم بياني كامل على رؤوس T ، بحواف تمثل أقصر المسارات في الرسم البياني المُدخل، ثم إيجاد تطابق مثالي ذي وزن أدنى في هذا الرسم البياني الكامل. تمثل حواف هذا التطابق مسارات في الرسم البياني الأصلي، ويشكل اتحادها وصلة T- المطلوبة . يمكن إنجاز كل من إنشاء الرسم البياني الكامل، ثم إيجاد التطابق فيه، في O( n³ ⁾ من الخطوات الحسابية.

في مسألة فحص المسار، يجب اختيار T كمجموعة جميع الرؤوس ذات الدرجة الفردية. وبحسب افتراضات المسألة، فإن الرسم البياني بأكمله متصل (وإلا لما وُجد مسار)، وبحسب مبرهنة المصافحة، فإنه يحتوي على عدد زوجي من الرؤوس الفردية، لذا فإن وصلة T موجودة دائمًا. يؤدي مضاعفة حواف وصلة T إلى تحويل الرسم البياني المعطى إلى رسم بياني متعدد أويلري (رسم بياني متصل تكون فيه درجة كل رأس زوجية)، ومن ثمّ يترتب على ذلك وجود مسار أويلري ، وهو مسار يمر بكل حافة من حواف الرسم البياني المتعدد مرة واحدة فقط. سيكون هذا المسار هو الحل الأمثل لمسألة فحص المسار. ^{[ 7 ] [ 2 ]}

في الرسم البياني الموجه، تنطبق نفس الأفكار العامة، ولكن يجب استخدام تقنيات مختلفة. إذا كان الرسم البياني الموجه من نوع أويلر، يكفي إيجاد دورة أويلر. أما إذا لم يكن كذلك، فيجب إيجاد وصلات من النوع T ، وهو ما يستلزم في هذه الحالة إيجاد مسارات من الرؤوس ذات درجة الدخول الأكبر من درجة الخروج إلى تلك التي تكون درجة الخروج منها أكبر من درجة الدخول ، بحيث تجعل درجة الدخول لكل رأس مساوية لدرجة الخروج منه. يمكن حل هذه المسألة كمثال على مشكلة تدفق التكلفة الدنيا، حيث توجد وحدة عرض واحدة لكل وحدة زيادة في درجة الدخول، ووحدة طلب واحدة لكل وحدة زيادة في درجة الخروج. وبذلك، يمكن حلها في زمن قدره O(| V | ^² | E |). يوجد حل إذا وفقط إذا كان الرسم البياني المعطى متصلاً اتصالاً قوياً . ^{[ 2 ] [ 8 ]}

تم اختزال العديد من المسائل التوافقية إلى مسألة ساعي البريد الصيني، بما في ذلك إيجاد القطع الأقصى في الرسم البياني المستوي ودائرة ذات طول متوسط ​​أدنى في الرسم البياني غير الموجه. ^{[ 9 ]}

تمت دراسة بعض المتغيرات لمسألة ساعي البريد الصيني وثبت أنها مسألة كاملة من فئة NP . ^{[ 10 ]}

• مسألة ساعي البريد العاصف هي شكلٌ مُعدَّل من مسألة فحص المسار، حيث يكون المُدخل عبارة عن رسم بياني غير مُوجَّه، ولكن قد تختلف تكلفة عبور كل حافة فيه في اتجاه عن تكلفتها في الاتجاه الآخر. وعلى عكس حلول الرسوم البيانية المُوجَّهة وغير المُوجَّهة، تُصنَّف هذه المسألة ضمن فئة NP-complete . ^{[ 11 ] [ 12 ]}
• مسألة ساعي البريد الصيني المختلط : في هذه المسألة، قد تكون بعض الحواف موجهة، وبالتالي لا يمكن زيارتها إلا من اتجاه واحد. عندما تتطلب المسألة اجتيازًا بأقل عدد ممكن من المسارات في رسم بياني موجه (أو رسم بياني متعدد التوجيهات)، تُعرف باسم "مسألة كاسح شوارع نيويورك". ^{[ 13 ]}
• مسألة ساعي البريد الصيني k : إيجاد k دورة تبدأ جميعها من موقع محدد بحيث يمر عبر كل حافة منها دورة واحدة على الأقل. الهدف هو تقليل تكلفة الدورة الأغلى.
• مسألة "ساعي البريد الريفي": حل المسألة مع عدم الحاجة إلى بعض الحواف. ^{[ 12 ]}

• مشكلة البائع المتجول
• توجيه القوس
• مشكلة ساعي البريد الصيني المختلط

• وايستين، إريك دبليو ، “مشكلة ساعي البريد الصيني” ، MathWorld
• الوسائط المتعلقة بمشكلة فحص المسار على ويكيميديا ​​كومنز