خوارزمية كريستوفيدس

خوارزمية كريستوفيدس، أو خوارزمية كريستوفيدس-سيرديوكوف، هي خوارزمية لإيجاد حلول تقريبية لمسألة البائع المتجول ، في الحالات التي تشكل فيها المسافات فضاءً متريًا (متناظرة وتخضع لمتباينة المثلث ). ^{[ 1 ]} وهي خوارزمية تقريبية تضمن أن تكون حلولها ضمن عامل 3/2 من طول الحل الأمثل، وقد سُميت نسبةً إلى نيكوس كريستوفيدس وأناتولي سيرديوكوف ( بالروسية : Анатолий Иванович Сердюков ). نشر كريستوفيدس الخوارزمية عام 1976، واكتشفها سيرديوكوف بشكل مستقل في نفس العام، لكنه نشرها عام 1978. ^{[ 2 ] [ 3 ] [ 4 ]}

ليكن G = ( V , w ) مثالاً على مسألة البائع المتجول. أي أن G رسم بياني كامل على مجموعة الرؤوس V ، والدالة w تُسند وزنًا حقيقيًا غير سالب لكل حافة من حواف G. وفقًا لمتباينة المثلث، لكل ثلاثة رؤوس u و v و x ، يجب أن يكون w ( uv ) + w ( vx ) ≥ w ( ux ) .

ويمكن وصف الخوارزمية باستخدام الشفرة الزائفة على النحو التالي. ^{[ 1 ]}

1. أنشئ شجرة امتداد دنيا T للجدول G.
2. ليكن O مجموعة الرؤوس ذات الدرجة الفردية في T. وبحسب نظرية المصافحة ، فإن O يحتوي على عدد زوجي من الرؤوس.
3. أوجد تطابقًا مثاليًا بأقل وزن M في الرسم البياني الفرعي المستحث في G بواسطة O.
4. قم بدمج حواف M و T لتشكيل رسم بياني متعدد متصل H حيث يكون لكل رأس درجة زوجية.
5. قم بتكوين دائرة أويلرية في H.
6. قم بتحويل الدائرة الموجودة في الخطوة السابقة إلى دائرة هاميلتونية عن طريق تخطي الرؤوس المتكررة ( الاختصار ).

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

تكلفة الحل الذي ينتجه الخوارزمية لا تتجاوز 3/2 من التكلفة المثلى. ولإثبات ذلك، لنفترض أن C هي جولة البائع المتجول المثلى. يؤدي حذف حافة من C إلى إنشاء شجرة ممتدة، يجب أن يكون وزنها على الأقل وزن الشجرة الممتدة الدنيا، مما يعني أن w ( T ) ≤ w ( C ) - وهو الحد الأدنى لتكلفة الحل الأمثل.

تعالج الخوارزمية مشكلة عدم كون T مسارًا من خلال تحديد جميع الرؤوس ذات الدرجات الفردية في T ؛ وبما أن مجموع الدرجات في أي رسم بياني زوجي (بحسب نظرية المصافحة )، فإن عدد هذه الرؤوس زوجي. وتجد الخوارزمية تطابقًا مثاليًا M بأقل وزن ممكن بين الرؤوس ذات الدرجات الفردية.

بعد ذلك، رتب رؤوس O بترتيب دوري حول C ، وقسم C إلى مجموعتين من المسارات: مسارات يكون فيها رأس المسار الأول برقم فردي، ومسارات يكون فيها رأس المسار الأول برقم زوجي. كل مجموعة مسارات تُقابل تطابقًا تامًا لـ O يُطابق نقطتي نهاية كل مسار، ويكون وزن هذا التطابق مساويًا على الأكثر لوزن المسارات. في الواقع، ستكون كل نقطة نهاية مسار متصلة بنقطة نهاية أخرى، والتي بدورها لها عدد فردي من الزيارات نظرًا لطبيعة المسار.

بما أن مجموعتي المسارات هاتين تقسمان حواف C ، فإن وزن إحدى المجموعتين لا يتجاوز نصف وزن C ، وبفضل متباينة المثلث، فإن وزن المطابقة المقابلة لها لا يتجاوز أيضًا نصف وزن C. لا يمكن أن يكون وزن المطابقة المثالية ذات الوزن الأدنى أكبر من ذلك، لذا فإن w ( M ) ≤ w ( C )/2 . بجمع وزني T و M نحصل على وزن مسار أويلر، والذي لا يتجاوز 3w ( C )/2 . وبفضل متباينة المثلث، حتى لو أعاد مسار أويلر زيارة بعض الرؤوس، فإن اختصار المسار لا يزيد الوزن، لذا فإن وزن الناتج لا يتجاوز أيضًا 3w ( C )/2 . ^{[ 1 ]}

توجد مدخلات لمسألة البائع المتجول تجعل خوارزمية كريستوفيدس تجد حلاً بنسبة تقريب قريبة جدًا من 3/2 . أحد هذه المدخلات يتكون من مسار ذي n رأسًا، حيث يكون وزن حواف المسار 1 ، بالإضافة إلى مجموعة من الحواف التي تربط الرؤوس التي تفصل بينها خطوتان في المسار، ويكون وزنها 1 + ε، حيث ε عدد موجب قريب من الصفر.

جميع الحواف المتبقية في الرسم البياني الكامل لها مسافات تُحددها أقصر المسارات في هذا الرسم البياني الفرعي. عندئذٍ، ستكون الشجرة الممتدة الدنيا مُحددة بالمسار، الذي يبلغ طوله n − 1 ، وسيكون الرأسان الفرديان الوحيدان هما طرفا المسار، اللذان يتكون تطابقهما التام من حافة واحدة بوزن يقارب n /2 .

اتحاد الشجرة والمطابقة يُشكّل دورةً، بدون أي اختصارات ممكنة، ووزنها يُقارب 3n /2 . مع ذلك، يستخدم الحل الأمثل حوافًا بوزن 1 + ε بالإضافة إلى حافتين بوزن 1 متصلتين بنهايتي المسار، ويبلغ وزنه الإجمالي (1 + ε )( n - 2) + 2 ، وهو قريب من n للقيم الصغيرة لـ ε . ومن ثم نحصل على نسبة تقريبية قدرها 3/2. ^{[ 5 ]}

لم تعد هذه الخوارزمية أفضل خوارزمية تقريبية متعددة الحدود لمسألة البائع المتجول على الفضاءات المترية العامة. قدّم كارلين وكلاين وغاران خوارزمية تقريبية عشوائية بنسبة تقريب 1.5 − 10 ⁻³⁶ . تتبع هذه الخوارزمية مبادئ مشابهة لخوارزمية كريستوفيدس، ولكنها تستخدم شجرة مختارة عشوائيًا من توزيع عشوائي مُختار بعناية بدلًا من الشجرة الممتدة الدنيا. ^{[ 6 ] [ 7 ]} حازت هذه الورقة البحثية على جائزة أفضل ورقة بحثية في ندوة نظرية الحوسبة لعام 2021. ^{[ 8 ]}  

في الحالة الخاصة للفضاء الإقليدي ذي البعد${\displaystyle d}$، لأي${\displaystyle c>0}$يوجد خوارزمية تعمل في وقت متعدد الحدود، وتجد مسارًا بطول لا يتجاوز${\displaystyle 1+{\tfrac {1}{c}}}$مرات الأمثل للحالات الهندسية لمسألة البائع المتجول في

${\displaystyle O\left(n(\log n)^{(O(c{\sqrt {d}}))^{d-1}}\right)}$وقت.

لكل ثابت${\displaystyle c}$هذا الحد الزمني يقع ضمن نطاق زمني متعدد الحدود ، ولذلك يُطلق عليه اسم مخطط تقريبي متعدد الحدود (PTAS). ^{[ 9 ]} مُنح سانجيف أرورا وجوزيف إس بي ميتشل جائزة غودل في عام 2010 لاكتشافهما المتزامن لمخطط تقريبي متعدد الحدود لمسألة البائع المتجول الإقليدية.

يمكن أيضًا استخدام الطرق القائمة على خوارزمية كريستوفيدس-سيرديوكوف لتقريب مسألة رافعة التكديس ، وهي تعميم لمسألة البائع المتجول (TSP) حيث تتكون المدخلات من أزواج مرتبة من النقاط من فضاء متري يجب اجتيازها بالتتابع وبالترتيب. بالنسبة لهذه المسألة، تحقق هذه الطريقة نسبة تقريب تبلغ 9/5. ^{[ 10 ]}

• تعريف خوارزمية كريستوفيدس التابعة للمعهد الوطني للمعايير والتكنولوجيا