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