شنيا تاريخ مشكلة البائع المتنقل خلال السنين في القائمة القصيرة؟
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 مدينة، باستخدام طائرات القطع والفرع والحدود.  في التسعينات، ابليجيت، بيكسبي، تشواتال، وكوك طوروا برنامج كونكورد واللي استخدم في كتير من حلول التسجيلات الحديثة. Gerhard Reinelt نشر TSPLIB في عام 1991، مجموعة من الحالات المرجعية من صعوبة مختلفة، واللي استخدمتها العديد من المجموعات البحثية لمقارنة النتائج. في عام 2006، كوك و غيره حشرو جولة مثالية من خلال 85,900 مدينة، و هذا هو أكبر مثال حل ل TSPLIB. في بضايع أخرى، مع ملايين المدن، فما حلول ممكن نلقاوها و هي مضمونة بلي هي ضمن 2 <unk> 3% من الجولة المثلى.
القرن التاسع عشر - صياغة رياضية لأول مرة من قبل عالم الرياضيات الايرلندي وليام روان هاميلتون و عالم الرياضيات البريطاني توماس كيركمان 1930s - درسوا لأول مرة من قبل علماء الرياضيات في فيينا وفي هارفارد، وخاصة من قبل كارل مينجر و ميريل إم فلود اللي كان يبحث عن حل لمشكلة توجيه الحافلات المدرسية. 1959 - جيليان بيردوود، جيه هالتون وجون هامرسلي نشروا مقال بعنوان "أقصر طريق عبر نقاط كثيرة" في جريدة جمعية كامبريدج الفلسفية، واللي قدم أول حل عملي. 1960s - نهج جديد يتخلق، واللي يخلق حل طوله محدد بشكل مؤكد بمضاعف طول الأمثل. 1972 - ريتشارد م. كارب أظهر أن مشكلة دورة هاملتون كانت NP كاملة، واللي يعني صلابة NP لمشكلة البائع المتنقل. 1976 - كريستوفيدس و سيرديوكوف اخترعوا خوارزمية جديدة بشكل مستقل، واللي توفر حل في أسوأ حالة أطول ب 1.5 مرة من الحل الأمثل. 1990s - Applegate، Bixby، Chvátal، و Cook طوروا برنامج كونكورد واللي استخدم في كتير من الحلول القياسية الحديثة. 1991 - جيرارد راينيلت نشر تسبليب، مجموعة من الحالات المرجعية من صعوبة مختلفة، واللي استخدمتها كتير من مجموعات البحث لمقارنة النتائج 2006 - كوك وآخرين حشرو جولة مثالية من خلال مثال 85,900 مدينة المعطى بواسطة مشكلة تخطيط ميكروتشيب، في الوقت الحالي أكبر مثال حل لTSPLIB. 2011 - تم تطوير خوارزمية تقريبية محسنة شوية لمجموعة فرعية لمشكلة البائع المتنقل "الجرافيكي". 2020 - الخوارزمية المتقريبة المتحسنة شوية والتي تم تطويرها للجماعة الفرعية من "الجرافيكال" تمت توسيعها لتغطي مشكلة بائع المتنقل الكاملة.