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