مسألة البائع المتجول-Travelling Salesman Problem

بفرض لديك عدداً من المناطق عليك زيارتها، ولديك مسافة بين كل منطقتين، وتريد المرور بأقصر طريق يمر من كل هذه المناطق بحيث لا تمر من المنطقة نفسها مرتين وبحيث تعود في النهاية إلى المنطقة التي انطلقت منها بالفعل، إن مسألة إيجاد هكذا طريق تسمى بمسألة البائع المتجول.

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

طبعاً الإجابة تعتمد على ما تعنيه "الفترة الزمنية المنطقية ". الوقت الذي يلزم خوارزمية ما لتنهي مهمتها يتناسب مع عدد الخطوات التي عليها تنفيذها. قد تجد خوارزمية تحتاج ²n خطوة لحل المسألة من أجل n منطقة.

وهذا يعني تنفيذ 100 خطوة في حال كانت المسألة تتطلب زيارة 10 مناطق وتنفيذ 400 خطوة في حال كانت المسألة تتطلب زيارة 20 منطقة. لربما هذا يبدو سيئاً وطويلاً في نظرك ولكن إن الخوارزمية الحالية الموجودة لحل هذه المسألة أسوء حيث تأخذ ⁿ2 خطوة من أجل n منطقة. وبالتالي 10 مناطق تتطلب تنفيذ 1024 خطوة و20 منطقة تتطلب تنفيذ أكثر من مليون خطوة!

لدى علماء الرياضيات صورة واضحة عن ما تعنيه "الفترة الزمنية المنطقية " في هذا السياق. العبارات المتضمنة قوى لـ n ، مثل ²n و ³n و ⁴n تدعى بكثيرات حدود لـ n . والخوارزمية تعتبر فعالة في حال كان عدد الخطوات التي تنفذها هو كثير حدود لـ n . وتدعى هذه الخوارزميات بخوارزميات كثير الحدود الزمني ( كثير حدود متغيره هو الزمن ) .

إذاً أصبح السؤال الذي يواجهنا هل يوجد خوارزمية كثير حدود زمني لحل مسألة البائع المتجول؟

الإجابة هي أن لا أحد يعلم فعلاً . لا أحد استطاع إيجاد هكذا خوارزمية ولا أحد استطاع أن يبرهن عدم وجود هكذا خوارزمية أيضاً. فإذاً لنحاول جعل هذه المسألة أسهل قليلاً فبدلاً من محاولة إيجاد أقصر طريق، لنحاول معرفة إذا كان يوجد طريق أقصر من عدد ما D حُدِّد مسبقاً. وهذه المسألة تسمى بنسخة القرار من مسألة البائع المتجول لأن الإجابة عليها هي إما نعم يوجد طريق أقصر من D أو لا لايوجد. ولسوء الحظ، لا يوجد أيضاً خوارزمية كثير حدود زمني لحل نسخة القرار من مسألة البائع المتجول، ولكن على الأقل إن قام أحدهم بإعطائك حل لهذه المسألة فإن التحقق من صحة هذا الحل سهل للغاية.

حيث إنّ مجموعة جميع مسائل القرار التي يمكن التحقق من صحة حل ما لها بسهولة (أي أنّه يوجد خوارزمية كثير حدود زمني للتحقق من الحل) تسمى بمسائل الصف NP. من المسائل الأخرى في هذا الصف هي مسألة كيفية تحليل أعداد ضخمة جداً إلى عواملها الأولية، على سبيل المثال لدينا:

44926453 = 13^5 x 2^11

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

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

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

ويوجد أيضاً تطبيقات أخرى لموضوعنا هذا . فالمسائل من الصف NP تستخدم غالباً في التشفير، على سبيل المثال نظام ال RSA الذي يُستخدم لجعل معاملات الانترنت آمنة. وفي الأساس، إن الإجابة على مسألة NP ما (لنقل مثلاً مسألة إيجاد العوامل الأولية) تستخدم كمفتاح يستخدم لفك تشفير الرسائل. وحقيقة أنه لا يوجد أي خوارزميات فعالة لحل مسائل NP فإن هذا يعني أن معرفة هذا المفتاح صعبة للغاية.

لذا تخيل معي أنك وجدت خوارزمية فعالة لحل المسألة. هذا يعني حصولك على مليون دولار وعلى مفتاح الدخول للأكواد الأكثر سرية في العالم وحياتك على الأرجح ستصبح في خطر..

المصدر:هنا