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