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