شلون تاريخ مشكلة البائعين المتنقلين على مر السنين في قائمة قصيرة من الارقام؟
Context:أصول مشكلة البائعين المسافرين غير واضحة. كتيب للمبيعين المسافرين من 1832 يذكر المشكلة ويتضمن مثال جولات عبر المانيا وسويسرا، لكن لا يحتوي على معالجة رياضية.   ويليام روان هاميلتون صُوِّر TSP رياضياً في القرن التاسع عشر من قبل عالم الرياضيات الايرلندي ويليام روان هاميلتون و عالم الرياضيات البريطاني توماس كيركمان. لعبة هاميلتون الايكوسية كانت لغز ترفيهي مبني على ايجاد دورة هاميلتونية. الشكل العام لـ TSP بدا انه تم دراسته لأول مرة من قبل علماء الرياضيات خلال الثلاثينات في فيينا وفي هارفارد، وخاصة من قبل كارل مينجر، الذي حدد المشكلة، واعتبر خوارزمية القوة الغاشمة الواضحة، ولاحظ عدم الافضل من اقرب جاره هيورستي:  نَشْرَحُ بِمَسْأَلَةِ الْمُرْسَلِ (لأنه في الممارسة هذا السؤال يَجِبُ أَنْ يُحَلَّ من قِبل كل ساعي بريد، وبالطبع أيضاً من قِبل العديد من المسافرين) المهمة لإيجاد، لعدد محدود من النقاط التي تعرف مسافاتها الزوجية، أقصر طريق يربط النقاط. بطبيعة الحال، هذي المشكلة قابلة للحل من خلال عدد محدود من التجارب. ما نعرف القوانين اللي راح تدفع عدد التجارب تحت عدد التبديلات للنقاط المعطاة. القاعدة ان واحد يجب ان يذهب اولا من نقطة البداية الى اقرب نقطة، ثم الى اقرب نقطة لهذه، إلخ، بشكل عام لا يعطي اقصر طريق.  فُكِرَ فيه لأول مرة رياضياً في الثلاثينيات من القرن العشرين من قبل ميريل إم فلوود الذي كان يبحث عن حل لمشكلة توجيه حافلة المدرسة. هاسلر ويتني من جامعة برينستون، أثار الاهتمام بالمشكلة، التي أطلق عليها "مشكلة 48 ولاية". أقدم منشور استخدم عبارة "مسألة البائع المسافر" كان تقرير شركة راند لعام 1949 من قبل جوليا روبنسون ، "على لعبة هاملتون (مسألة البائع المسافر) ".  في الخمسينات والستينات، اصبحت المشكلة مشهورة بشكل متزايد في الاطراف العلمية في اوروبا والولايات المتحدة بعد ان عرضت شركة راند في سانتا مونيكا جوائز على الخطوات في حل المشكلة. ساهمت جورج دانتزيج و ديلبرت راي فولكرسون وسيلمر ام جونسون من مؤسسة راند، والذين اعربوا عن المشكلة كبرنامج خطي صحيح وطوروا طريقة الطائرة القطع لحلها. كَتَبوا ما يعتبر ورقة أساسية عن الموضوع حيث باستخدام هذه الأساليب الجديدة حلوا حالة مع 49 مدينة للاستفادة المثلى من خلال بناء جولة وإثبات أن لا جولة اخرى يمكن أن تكون أقصر. بيد أن دانتزيغ وفولكيرسون وجونسون، افترضوا أنه بالنظر إلى حل شبه مثالي قد نتمكن من إيجاد الأمثل أو إثبات الأمثل عن طريق إضافة عدد قليل من عدم المساواة الإضافية (القطع). استخدموا الفكرة ليحلوا مشكلتهم الاولي بـ 49 مدينة باستخدام نموذج سلاسل. واكتشفوا انهم احتاجوا فقط 26 قطع للوصول الى حل لمشكلتهم 49 مدينة. وبالرغم من ان هذه الورقة ما اعطت نهج خوارزمي لمشاكل TSP، الا ان الافكار التي تكمن داخلها كانت لا غنى عنها لاحقًا لخلق طرق حل دقيقة لـ TSP، على الرغم من انه سيستغرق 15 سنة لإيجاد نهج خوارزمي في خلق هذه القطع. وبالاضافة الى طرق القطع السطحية، استخدم دانتزيج وفولكيرسون وجونسون خوارزميات التفرع والترابط ربما لأول مرة.  في عام 1959، نشرت جيليان بيردوود، جيه هالتون وجون هامرسلي مقالة بعنوان "أقصر طريق عبر العديد من النقاط" في مجلة جمعية كامبريدج الفلسفية. نظرية بياردوود هالتون هامرسلي توفر حل عملي لمشكلة بائع المتنقل. المؤلفين اخذوا صيغة غير متماثلة لتحديد طول أقصر طريق لمتجر يبدأ من المنزل او المكتب ويزور عدد محدد من المواقع قبل العودة الى البداية.  في العقود اللاحقة، دراسة المشكلة من قبل العديد من الباحثين من الرياضيات، علوم الكمبيوتر، الكيمياء، الفيزياء، وغيرها من العلوم. لكن في الستينيات من القرن العشرين ، تم إنشاء نهج جديد ، بدلاً من البحث عن الحلول المثلى ، سيوفر حل يحدد طوله بشكل مؤكد بمضاعف من الطول المثالي ، وبذلك سيخلق حدود أدنى للمشكلة ؛ سيتم استخدام هذه الحدود الدنيا بعد ذلك مع النهج المتفرعة والمحدودة. احدى الطرق للقيام بذلك هي انشاء احلى شجرة امتداد للمخطط ومن ثم مضاعفة كل حوافها، والتي تنتج الحدود ان طول الجولة المثلى هو على الأكثر مرتين من وزن احلى شجرة امتداد.  في عام 1976، عمل كريستوفيدس و سيرديوكوف بشكل مستقل من بعضهم البعض تقدم كبير في هذا الاتجاه: خوارزمية كريستوفيدس-سيرديوكوف تعطينا حل، في أسوأ حالة، أطول بحد أقصى 1.5 مرة من الحل الأمثل. وبما ان الخوارزمية كانت بسيطة وسريعة، كان كثيرين يأملون انها ستعطى المجال لطريقة الحل المثالي تقريبا. وبالرغم من ذلك، لم يتحقق هذا الأمل في التحسين على الفور، و بقي كريستوفيدس-سيرديوكوف طريقة مع أفضل سيناريو أسوأ حال حتى عام 2011، عندما تم تطوير خوارزمية تقريب (مُحسنة قليلاً جداً) للجماعة الفرعية من TSPs "الجرافيكية". في 2020، هذا التحسن الصغير تم تمديده لـ TSP الكامل (المقياسي).  ريشارد م. كارب اثبت في 1972 ان مشكلة دورة هاملتون كانت NP كاملة، والذي يعني NP صلابة TSP. هذا قدم تفسير رياضي للصعوبة الحسابية الظاهرية في ايجاد الجولات المثلى.  احرزت تقدم كبير في نهاية السبعينات والثمانينات ، عندما تمكن غروتشيل ، بادبيرج ، رينالدي وآخرون من حل الحالات بدقة مع ما يصل إلى 2392 مدينة ، باستخدام طائرات القطع والفرع والحدود.  فِي التسعينيات، طَوَّرَ أبليجيت، بيكسبي، تشواتال، وكوك برنامج كونكورد الذي استخدم في العديد من حلول التسجيلات الاخيرة. غيرهارد راينلت نشر تسبليب في 1991، مجموعة من الحالات المرجعية من صعوبة مختلفة، والتي استخدمتها العديد من المجموعات البحثية لمقارنة النتائج. فِي 2006, كوك وآخرون حَسَبوا جولة مثالية من خلال 85,900 مدينة نظراً لمشكلة تخطيط الرقاقة الدقيقة، وهي حالياً أكبر مثال حل لـ TSPLIB. للكثير من الحالات الاخرى مع الملايين من المدن، يمكن ايجاد حلول تضمن ان تكون ضمن 2-3% من الجولة المثلى.
* القرن التاسع عشر - صيغت رياضيا لأول مرة من قبل عالم الرياضيات الايرلندي ويليام روان هاميلتون ومن قبل عالم الرياضيات البريطاني توماس كيركمان * ثلاثينات القرن العشرين - درسوه اول مرة علماء الرياضيات في فيينا وفي هارفارد، وخصوصاً كارل مينجر وميريل ام فلود الذين كانوا يبحثون عن حل لمشكلة توجيه الحافلات المدرسية. * 1959 - جيليان بيردوود، جيه هالتون وجون هامرسلي نشروا مقال بعنوان "أقصر طريق عبر نقاط عديدة" في مجلة جمعية كامبريدج الفلسفية، والذي قدم أول حل عملي. * الستينيات من القرن التاسع عشر: تم تطوير نهج جديد، والذي ينتج حلا يحد طوله بشكل مؤكد بمضاعفة الطول المثالي. * 1972 - أظهر ريتشارد كارب ان مشكلة دورة هاملتون كانت NP كاملة، والتي تنطوي على NP صلابة مشكلة بائع مسافر. 1976 - اخترع كريستوفيدس و سيرديوكوف بشكل مستقل خوارزمية جديدة، والتي تعطينا حل في أسوأ حالة هو أطول بـ 1.5 مرة من الحل الأمثل. * التسعينيات من القرن العشرين - أبلجيت وبيكسبي وشواتال وكوك طوروا برنامج كونكورد الذي تم استخدامه في العديد من حلول التسجيلات الاخيرة. 1991 - غيرهارد راينلت نشرت تسبليب، مجموعة من الحالات المرجعية من صعوبة مختلفة، والتي استخدمتها العديد من المجموعات البحثية لمقارنة النتائج * 2006 - كوك وآخرين حاسبوا جولة مثالية من خلال مثال 85,900 مدينة يعطيها مشكلة تخطيط الرقاقة الدقيقة، وهي حالياً أكبر مثال TSPLIB محلول. * 2011 - تم تطوير خوارزمية تقريبية محسنة قليلاً لمجموعة فرعية من مشكلة البائع المتنقل "الرسومية". * 2020 - خوارزمية التقريب المطورة قليلاً للجماعة الفرعية من " الرسوم البيانية " تمت توسيعها لتغطي مشكلة بائع المتنقل بالكامل.