مسألة البائع المتجول: ما الذي يجمع خرائط جوجل وتسلسل الحمض النووي؟

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

لأن العدد أربعة صغيرٌ نسبيًا، فتستطيع قبل أن تباشر رحلتك بجلب خريطة للمواقع، وتقوم بحساب المسافات بين شركتك وبين الشركات الأخرى، لكل من التباديل المختارة. إن افترضنا أن المواقع يرمز لها بالحروف (أ، ب، جـ، د)، بالإضافة إلى موقع شركتك والذي سنرمز له بالحرف (م)، فتستطيع أن تكتب الاحتمالات لهذه الرحلة بتبديل المواقع الأربعة، فبتدأ بإحدى الأربع، ثم تختار ما تبقى من الثلاثة، ثم تختار ما تبقى من الاثنتين، ثم تختار المتبقية الأخيرة، فيصبح مجموع الاحتمالات هو 4×3×2×1 = 24 والذي قد تعرفه منذ دراستك في المدرسة باسم المضروب، أو 4! بالتعبير الرياضي.
ولكن هناك افتراضًا قد يسهل علينا المسألة بشكل، إن افترضنا أن طريق الإياب مساوٍ في المسافة لطريق الذهاب، فنلاحظ أن نصف الطرق الموجودة في الاحتمالات متكررة، فيصبح لدينا مجموع اثني عشر طريقًا محتملًا. 

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

ولكن لنفترض أن هذه المشكلة توسعت لإحدى شركات الشحن البري، حيث قامت شركة كبرى بتنظيم إيصال عشرين أمر شحن لإحدى العاملين في يومٍ واحد، وهي تعد بخاصية التوصيل في نفس اليوم. كيف بإمكان هذه الشركة أن تخطط رحلتها في أقل مسافة ووقت وحتى استهلاك وقود ممكنين؟ لنتبع الطريقة السابقة، فنقوم بوضع جميع الاحتمالات الممكنة على ورقة صغيرة، ففي البداية لدينا 20 موقعًا، ثم يكون لدينا 19 موقعًا متبقيًا، ثم 18، ثم 17،... لحظة! كم عدد الاحتمالات مجددًا؟ حتى وإن افترضت تساوي طرق الذهاب والإياب؟ 
لدينا 20!÷2 = 1216451004088320000 طريقًا محتملًا. لن تتسع الورقة الموجودة لدينا، وقطعًا لن يتسع لدينا الوقت المتاح حتى وإن قمنا بكتابة كل طريق محتمل في ثانية واحدة، فيسحتاج منا الأمر نحو 38 مليار سنة، وهو ما يقارب ثلاثة أضعاف عمر الكون! 

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

هذا هو أساس مسألة البائع المتجول (Traveling Salesman Problem, TSP) والتي تأتي في العديد من المسائل اليومية والتي ذكرنا بضعها في عنوان هذا المقال، مثل تطبيقات الخرائط وحساب المسافات أو الأوقات الأقصر لطريق ما، أو إيجاد طرق حركة لفوهات الطابعات ثلاثية الأبعاد التي قد تتحرك حركة تقوم فيها بصب المادة المصهورة للطباعة، ما يعرف بالحافة المخصصة للطباعة (Printing edge) أو الانتقال من نقطة طباعة إلى نقطة أخرى دون صب أي مادة مصهورة، ما تسمى الحافة العابرة (Traversing edge). فإن اختيار اتجاه حركة الفوهة في هذه الحالة يعتمد على اختيار الطريق الأقصر الأمثل لتوفير أكبر وقت ممكن للطباعة، وغيرها الكثير من المسائل التي نبحث في الحلول المُثلى لها يوميًا. 

لطالما لاقت هذه المسألة رواجًا بين المبرمجين وعلماء الرياضيات والمهندسين وحتى الباحثين في المجالات الأخرى، لنطاق المجالات التي تحتاج إلى حساب المسافات الأقصر بين نقطتين في مسألة ما يمكن تمثيلها ببيان (graph) معين، بحيث تمثل رؤوسه بأنها نقاط أو حالات أو قيم يراد التنقل بينها، وتمثل أضلاعه كلفة التنقل، إن كانت مسافةً أو وقتًا أو غير ذلك.

فلنأخذ مثال المدن مثلًا، ولننظر إلى المدن في البيان أعلاه، لتي يرمز لها بالحروف A, B, C, D، حيث ترمز الأرقام الموجودة على أضلاع هذا البيان. كما قمنا في البداية، بإمكاننا حساب المسافات في هذا البيان بين نقطة بداية ونقطة نهاية معينتين. ولكن فلنفترض أنك ستقوم بإعداد رحلة تقوم فيها بزيارة كل مدينة أوروبية كبرى، من تالين في إستونيا شرقًا إلى لشبونة في البرتغال غربًا، ومن فاليتا في مالطا جنوبًا إلى ريكيافيك في آيسلندا شمالًا. كيف ستبدأ بتخطيط رحلتك؟

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

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

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

وأنتم، أين ستسافرون قريبًا؟