ايه تاريخ مشكلة البائع المتنقل على مر السنين في قائمة قصيرة مشفرة؟
Context:أصول مشكلة بائع السفر مش واضحة. كتيب للمبيعين المتنقلين من سنة 1832 بذكر المشكلة وبيتضمن جولات مثالية عبر ألمانيا وسويسرا، بس ما بيحتويش على علاج رياضي.   ويليام روان هاميلتون تم صياغة TSP رياضياً في القرن التسعتاشر من قبل عالم الرياضيات الأيرلندي ويليام روان هاملتون ومن قبل عالم الرياضيات البريطاني توماس كيركمان. كانت لعبة هاميلتون إيكوسيان لغز ترفيهي مبني على إيجاد دورة هاميلتونية. الشكل العام لـ TSP بدا أنه تم دراسته لأول مرة من قبل علماء الرياضيات خلال ثلاثينيات القرن العشرين في فيينا وفي جامعة هارفارد، وخاصة من قبل كارل منغر، اللي حدد المشكلة، واعتبر خوارزمية القوة الغاشمة الواضحة، ولاحظ عدم الأمثلية لهيورستيك أقرب جار:  بنشير بمشكلة الرسول (لأن في الممارسة العملية يجب أن يحل هذا السؤال كل ساعي بريد، على أي حال أيضًا من قبل العديد من المسافرين) مهمة العثور، لعدد محدود من النقاط اللي المسافات بينها معروفة، أقصر طريق يربط النقاط. بطبيعة الحال، المشكلة دي ممكن تحلها بمحاولات كتير. القواعد اللي بتدفع عدد التجارب تحت عدد الترتيبات للنقاط المعطاة مش معروفة. القاعدة اللي بيقول إن الواحد لازم يروح أولًا من نقطة البداية لأقرب نقطة، وبعدين لأقرب نقطة ليها، إلخ، بشكل عام مش بتعمل أقصر طريق.  تم النظر فيها لأول مرة رياضياً في ثلاثينيات القرن العشرين من قبل ميريل إم فلود اللي كان بيبحث عن حل مشكلة توجيه حافلة مدرسية. خلق هاسلر ويتني في جامعة برينستون اهتمام بالمشكلة، واللي أطلق عليها "مشكلة 48 ولاية". كانت أول منشور استخدم عبارة "مشكلة البائع المسافر" هي تقرير شركة راند لعام 1949 من قبل جوليا روبنسون ، "على لعبة هاملتون (مشكلة البائع المسافر) ".  في الخمسينات والستينات، بقت المشكلة مشهورة بشكل متزايد في الدوائر العلمية في أوروبا والولايات المتحدة بعد ما عرضت شركة راند في سانتا مونيكا جوائز على الخطوات في حل المشكلة. قدم جورج دانتزيغ و ديلبرت راي فولكرسون وسيلمر إم جونسون مساهمات ملحوظة من مؤسسة راند، اللي أعربوا عن المشكلة باعتبارها برنامج خطي صحيح و طوروا طريقة طائرة القطع لحلها. كتبوا اللي بيتم اعتباره الورقة الأساسية في الموضوع اللي فيه مع هذه الأساليب الجديدة حلوا حالة مع 49 مدينة إلى الأمثل عن طريق بناء جولة وإثبات أنه ما في جولة أخرى ممكن تكون أقصر. بالرغم من كده، افترض دانتزيغ وفولكرسون وجونسون إنه بالنظر لحل شبه مثالي ممكن نقدر نلاقي الأمثل أو نثبت الأمثل عن طريق إضافة عدد قليل من عدم المساواة الإضافية (القطع). استخدموا الفكرة دي علشان يحلوا مشكلة المدن الـ 49 الأولي بتاعهم باستخدام نموذج سلسلة. وجدوا إنهم محتاجين 26 خفض فقط للوصول لحل لمشكلة مدينتهم البالغ عددها 49 مدينة. في حين إن الورقة دي ما أعطتش نهج خوارزمي لمشاكل TSP، إلا إن الأفكار اللي موجودة فيها كانت ضرورية لإنشاء أساليب حل دقيقة لـ TSP في وقت لاحق، على الرغم من أنها ستستغرق 15 سنة لإيجاد نهج خوارزمي في إنشاء هذه التخفيضات. بالإضافة إلى أساليب قطع الطائرة، استخدم دانتزيغ وفولكرسون وجونسون خوارزميات فرع وترابط ربما لأول مرة.  في سنة ١٩٥٩، نشرت جيليان بيردوود، جيه هالتون، وجون هامرسلي مقالة بعنوان "أقصر طريق عبر نقاط كتير" في مجلة جمعية كامبريدج الفلسفية. بتوفر نظرية بياردوود هالتون هامرسلي حل عملي لمشكلة بائع السفر. استخلص المؤلفون صيغة غير متماثلة عشان يحددوا طول أقصر طريق لمتجر بيبدأ في بيت أو مكتب ويزور عدد محدد من المواقع قبل ما يرجع للبداية.  في العقود اللي بعده، درس المشكلة كتير من الباحثين من الرياضيات وعلم الكمبيوتر والكيمياء والفيزياء والعلوم التانية. ومع كده، في الستينيات، اتعمل نهج جديد، بدل البحث عن الحلول المثلى، بيخلق حل طوله محدد بشكل مؤكد بمضاعفة الطول المثالي، وبذلك بيخلق حدود أدنى للمشكلة؛ الحدود الدنيا دي بعد كده بيتم استخدامها مع الأساليب المتفرعة والمحدودة. كانت طريقة واحدة للقيام بذلك هي إنشاء شجرة امتداد أدنى للمخطط ومن ثم مضاعفة جميع حوافها، واللي بتنتج الحد اللي طول الجولة المثلى هو أكتر من ضعف وزن شجرة امتداد أدنى.  في سنة 1976، عمل كريستوفيدس وسيرديوكوف بشكل مستقل عن بعضهم البعض تقدم كبير في الاتجاه ده: خوارزمية كريستوفيدس-سيرديوكوف بتعطي حل، في أسوأ الحالات، أطول من الحل الأمثل 1.5 مرة. لما كانت الخوارزمية بسيطة وسريعة، كان كتير بتمنى إنها تترك الطريق لطريقة حل شبه مثالية. ومع ذلك ، لم يتحقق الأمل في التحسن ده على الفور ، وبقي Christofides-Serdyukov طريقة مع أفضل سيناريو أسوأ الحالات حتى عام 2011 ، عندما تم تطوير خوارزمية تقريب (محسنة قليلاً) للجماعة الفرعية من TSPs "الرسوم البيانية". في سنة 2020 تم توسيع هذا التحسن الصغير ليتم تطبيقه على نظام التجارة العالمي الكامل (المقياسي).  أظهر ريتشارد إم كارب في سنة 1972 أن مشكلة دورة هاملتون كانت NP كاملة، واللي بيعني صلابة NP لـ TSP. ده قدم تفسير رياضي للصعوبة الحسابية الواضحة للعثور على الجولات المثلى.  اتحقق تقدم كبير في أواخر السبعينيات والثمانينيات ، لما تمكن غروتشيل وبادبيرج ورينالدي وغيرهم من حل الحالات بدقة مع ما يصل إلى 2392 مدينة ، باستخدام طائرات القطع والفرع والحدود.  في التسعينات ، طور Applegate و Bixby و Chvátal و Cook برنامج Concorde الذي استخدم في العديد من حلول السجلات الحديثة. نشر جيرارد راينلت TSPLIB في سنة 1991، وهي مجموعة من الحالات المرجعية بتختلف صعوبة، واللي استخدمتها كتير من المجموعات البحثية لمقارنة النتائج. في عام 2006 ، قام كوك وآخرون بحساب جولة مثالية من خلال مثال 85,900 مدينة من خلال مشكلة تخطيط الرقاقة الدقيقة ، وهي حاليًا أكبر مثال TSPLIB محلول. بالنسبة لكثير من الحالات التانية مع الملايين من المدن، ممكن نلاقي حلول بضمان تكون ضمن 2 <unk> 3٪ من الجولة الأمثل.
* القرن التسعتاشر - صيغ رياضيا لأول مرة من قبل عالم الرياضيات الإيرلندي ويليام روان هاميلتون ومن قبل عالم الرياضيات البريطاني توماس كيركمان سنة 1930 - درسوا لأول مرة من قبل علماء الرياضيات في فيينا وفي جامعة هارفارد، وخصوصاً من قبل كارل مينجر وميريل إم فلوود اللي كان يبحث عن حل مشكلة توجيه حافلة مدرسية. 1959 - جيليان بيردوود، جيه هالتون وجون هامرسلي نشروا مقال بعنوان "أقصر طريق عبر نقاط كتير" في مجلة الجمعية الفلسفية في كامبريدج، واللي قدم أول حل عملي. * الستينيات - اتعمل نهج جديد، اللي بيدي حل طوله محدد بشكل مؤكد بمضاعف الطول المثالي. 1972 - أظهر ريتشارد إم كارب إن مشكلة دورة هاملتون كانت NP كاملة، واللي بيعني صلابة NP لمشكلة بائع السفر. 1976 - اخترع كريستوفيدس وسيرديوكوف خوارزمية جديدة بشكل مستقل، واللي بتعطي حل في أسوأ الحالات أطول 1.5 مرة على الأكثر من الحل الأمثل. * التسعينيات - أبلجيت وبيكسبي وشواتال وكوك طوروا برنامج كونكورد اللي استخدم في كتير من حلول التسجيلات الأخيرة. 1991 - نشر جيرارد راينيلت تسبليب، مجموعة من الحالات المرجعية بتختلف صعوبة، واللي استخدمتها كتير من مجموعات البحث لمقارنة النتائج 2006 - كوك وآخرين حسبوا جولة مثالية من خلال مثال 85,900 مدينة من خلال مشكلة تخطيط الرقاقة الدقيقة ، وهي حاليًا أكبر مثال TSPLIB محلول. 2011 - تم تطوير خوارزمية تقريب محسنة شوية لمجموعة فرعية لمشكلة بائع متنقل "جرافيكي". 2020 - خوارزمية التقريب المطورة شوية لمجموعة فرعية من "الجرافيكال" تمت توسيعها لتغطية مشكلة بائع السفر الكاملة.