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