ما هو تاريخ مشكلة البائع المتنقل عبر السنين في قائمة قصيرة؟
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 - جيليان بيردوود، جيه هالتون وجون هامرسلي نشروا مقال بعنوان "أقصر طريق عبر العديد من النقاط" في مجلة الجمعية الفلسفية في كامبريدج، والذي قدم أول حل عملي. 1960s - نهج جديد يخلق، والذي ينتج حل طوله محدد بشكل مؤكد بمضاعف الطول الأمثل. 1972 - ريتشارد كارب اظهر ان مسألة دورة هاملتونيه كانت NP كاملة، والذي يعني NP صلابة مسألة تاجر مسافر. 1976 - كريستوفيدس و سيرديوكوف اخترعوا بشكل مستقل خوارزمية جديدة، والتي تعطى حل في أسوأ الحالات هو أطول 1.5 مرات على الأكثر من الحل الأمثل. تسعينيات القرن التاسع عشر - ابلغيت، بيكسبي، تشواتال وكوك طوروا برنامج كونكورد الذي استخدم في العديد من حلول التسجيلات الحديثة. 1991 - جيرارد راينيلت نشر "تسبليب"، مجموعة من الحالات المرجعية ذات صعوبة مختلفة، والتي استخدمتها العديد من مجموعات البحث لمقارنة النتائج * 2006 - كوك وآخرين حسابوا جولة مثالية من خلال مثال 85,900 مدينة من خلال مشكلة تخطيط الرقاقة الدقيقة، وهي حاليًا أكبر مثال TSPLIB محلول. 2011 - تم تطوير خوارزمية تقريبية متطورة قليلاً لمجموعة فرعية من مشكلة بائع متنقل "جرافيكي". 2020 - خوارزمية التقريب المتطورة قليلاً التي تم تطويرها لمجموعة فرعية من "الجرافيك" تمت توسيعها لتغطي مشكلة بائع متنقل كاملة.