* 19 व्या शतकात - आयरिश गणितज्ञ विल्यम रोवन हॅमिल्टन आणि ब्रिटीश गणितज्ञ थॉमस किर्कमन यांनी प्रथमच गणितीदृष्ट्या तयार केले * १९३० - प्रथम व्हिएन्ना आणि हार्वर्डमधील गणितज्ञांनी अभ्यास केला, विशेषतः कार्ल मेन्जर आणि मेरिल एम. फ्लड यांनी शालेय बस मार्गाची समस्या सोडविण्याचा प्रयत्न केला. * १९५९ - जिलियन बीर्डवुड, जे. एच. हॉल्टन आणि जॉन हॅमरस्ली यांनी केंब्रिज फिलॉसॉफिकल सोसायटीच्या जर्नलमध्ये "द शॉर्टेस्ट पाथ थ्रू मल्टि पॉइंट्स" हा लेख प्रकाशित केला, ज्याने प्रथम व्यावहारिक उपाय प्रदान केला. * १९६० - नवीन दृष्टिकोन तयार केला जातो, ज्यामुळे एक उपाय तयार होतो ज्याची लांबी इष्टतम लांबीच्या एकाधिक प्रमाणात मर्यादित असते. * १९७२ - रिचर्ड एम. कार्प यांनी हॅमिल्टनियन चक्र समस्या एनपी-पूर्ण असल्याचे दर्शविले, ज्याचा अर्थ असा आहे की प्रवासी विक्रेता समस्येची एनपी-कठोरता. * १९७६ - क्रिस्टोफिड्स आणि सेरड्यूकोव्ह यांनी स्वतंत्रपणे नवीन अल्गोरिदम शोधला, ज्यामुळे सर्वात वाईट परिस्थितीत इष्टतम समाधानापेक्षा जास्तीत जास्त १.५ पट जास्त समाधान मिळते. * १९९० च्या दशकात - ऍपलेगेट, बिक्सबी, च्वाटल आणि कुक यांनी कॉनकॉर्ड हा प्रोग्राम विकसित केला जो अलीकडील अनेक रेकॉर्ड सोल्यूशन्समध्ये वापरला गेला आहे. 1991 - गेर्हार्ड राईनल्ट यांनी टीएसपीएलआयबी प्रकाशित केले, जे वेगवेगळ्या अडचणीचे बेंचमार्क उदाहरणांचे संग्रह आहे, जे बर्याच संशोधन गटांनी परिणामांची तुलना करण्यासाठी वापरले आहे. * 2006 - कुक आणि इतरांनी मायक्रोचिप लेआउट समस्येद्वारे दिलेल्या 85,900 शहरांच्या उदाहरणाद्वारे इष्टतम टूरची गणना केली, सध्या सर्वात मोठी सोडविलेली टीएसपीएलआयबी उदाहरणे. * २०११ - "ग्राफिकल" ट्रॅव्हलिंग सेल्समॅन समस्येच्या उपसंचसाठी किंचित सुधारित सान्निध्य अल्गोरिदम विकसित केले गेले आहे. * २०२० - "ग्राफिकल" च्या उपसमुहासाठी विकसित केलेला थोडासा सुधारित अंदाजे अल्गोरिदम संपूर्ण प्रवासी विक्रेता समस्येचा समावेश करण्यासाठी विस्तारित केला गेला आहे.
प्रवासी विक्रेता समस्येचा इतिहास काय आहे?
Context:प्रवासी विक्रेता समस्येची उत्पत्ती अस्पष्ट आहे. १८३२ सालातील प्रवासी विक्रेत्यांसाठीच्या पुस्तिकेत या समस्येचा उल्लेख आहे आणि त्यात जर्मनी आणि स्वित्झर्लंडच्या माध्यमातून उदाहरणार्थ टूर समाविष्ट आहेत, परंतु त्यात कोणतेही गणितीय उपचार नाहीत.   विल्यम रोवन हॅमिल्टन १९व्या शतकात आयरिश गणितज्ञ विल्यम रोवन हॅमिल्टन आणि ब्रिटीश गणितज्ञ थॉमस किर्कमन यांनी टीएसपीचे गणितीय सूत्र तयार केले होते. हॅमिल्टनचा आयकोसियन खेळ हा हॅमिल्टनियन चक्र शोधण्यावर आधारित एक मनोरंजक कोडे होता. टीएसपीचे सामान्य स्वरूप प्रथम 1930 च्या दशकात व्हिएन्ना आणि हार्वर्ड येथे गणितज्ञांनी अभ्यास केले होते, विशेषतः कार्ल मेन्जर यांनी, ज्याने समस्येची व्याख्या केली, स्पष्ट क्रूर-शक्ती अल्गोरिदमचा विचार केला आणि जवळच्या शेजाऱ्याच्या नॉन-ऑप्टिमालिटीचे निरीक्षण केले.  आम्ही मेसेंजर प्रॉब्लेम (कारण प्रत्यक्षात हा प्रश्न प्रत्येक पोस्टमनने सोडवला पाहिजे, तरीही बर्याच प्रवाशांनी देखील) हे कार्य दर्शविले आहे, ज्याची अंतराची अंतराची अंतरे ज्ञात आहेत, त्या बिंदूंना जोडणारा सर्वात छोटा मार्ग शोधणे. अर्थात, ही समस्या मर्यादित प्रमाणात चाचण्या करून सोडवता येते. दिलेल्या बिंदूंच्या क्रमवारीच्या संख्येच्या खाली चाचण्यांची संख्या वाढविणारे नियम ज्ञात नाहीत. सुरुवातीच्या बिंदूपासून सर्वात जवळच्या बिंदूवर जाणे, नंतर त्यास सर्वात जवळच्या बिंदूवर जाणे इत्यादी नियम सर्वसाधारणपणे सर्वात लहान मार्ग देत नाही.  हे प्रथम 1930 च्या दशकात मेरिल एम. फ्लॉड यांनी गणितीदृष्ट्या विचारात घेतले होते, जे शालेय बस रुटिंग समस्येचे निराकरण करण्याचा प्रयत्न करीत होते. प्रिन्स्टन विद्यापीठातील हॅस्लर व्हिटनी यांनी या समस्येमध्ये रस निर्माण केला, ज्याला त्यांनी "48 राज्यांचा प्रश्न" म्हटले. "प्रवासी विक्रेता समस्या" या वाक्याचा वापर करणारे सर्वात जुने प्रकाशन जुलिया रॉबिन्सन यांनी 1949 मध्ये रँड कॉर्पोरेशनचा अहवाल होता, "हॅमिल्टनियन गेम (एक प्रवासी विक्रेता समस्या) वर".  १९५० आणि १९६० च्या दशकात, सांता मोनिका येथील रँड कॉर्पोरेशनने समस्या सोडवण्याच्या पायर्यांसाठी बक्षिसे ऑफर केल्यानंतर ही समस्या युरोप आणि अमेरिकेतील वैज्ञानिक मंडळांमध्ये वाढत्या प्रमाणात लोकप्रिय झाली. जॉर्ज डॅन्टिग, डेलबर्ट रे फुल्करसन आणि सेल्मर एम. जॉन्सन यांनी रँड कॉर्पोरेशनमधून उल्लेखनीय योगदान दिले, ज्यांनी ही समस्या एक पूर्णांक रेषेचा कार्यक्रम म्हणून व्यक्त केली आणि त्याच्या समाधानासाठी कटिंग प्लेन पद्धत विकसित केली. त्यांनी या विषयावर एक मूलभूत पेपर लिहिला ज्यामध्ये त्यांनी या नवीन पद्धतींचा वापर करून 49 शहरांसह एक टूर तयार करून इष्टतमतेसाठी सोडवले आणि हे सिद्ध केले की इतर कोणतीही टूर कमी असू शकत नाही. डँटझिग, फुल्करसन आणि जॉन्सन यांनी असे अनुमान लावले की जवळजवळ इष्टतम उपाय दिल्यास आपण काही अतिरिक्त असमानता (कट) जोडून इष्टतमता शोधू किंवा इष्टतमता सिद्ध करू शकू. त्यांनी या कल्पनेचा वापर स्ट्रिंग मॉडेलचा वापर करून त्यांच्या सुरुवातीच्या ४९ शहरांच्या समस्येचे निराकरण करण्यासाठी केला. त्यांना असे आढळले की त्यांच्या 49 शहरांच्या समस्येवर तोडगा काढण्यासाठी फक्त 26 कपातीची गरज होती. या पेपरमध्ये टीएसपीच्या समस्येवर अल्गोरिदमचा दृष्टिकोन देण्यात आलेला नसला तरी, त्यातील कल्पना टीएसपीसाठी अचूक उपाय पद्धती तयार करण्यासाठी अपरिहार्य होत्या, जरी या कट तयार करण्यासाठी अल्गोरिदमचा दृष्टिकोन शोधण्यासाठी 15 वर्षे लागतील. डॅन्टिग, फुल्करसन आणि जॉन्सन यांनी कदाचित प्रथमच शाखा आणि बंधनकारक अल्गोरिदम वापरल्या.  १९५९ साली, जिलियन बीर्डवुड, जे. एच. हॉल्टन आणि जॉन हॅमरस्ली यांनी केंब्रिज फिलॉसॉफिकल सोसायटीच्या जर्नलमध्ये "द शॉर्टेस्ट पाथ थ्रू मनी पॉइंट्स" नावाचा एक लेख प्रकाशित केला. बीर्डवुड-हॅल्टन-हॅमरस्ले प्रमेय प्रवासी विक्रेता समस्येचे व्यावहारिक समाधान प्रदान करते. एका विक्रेत्याने घर किंवा कार्यालयात सुरूवात केली आणि सुरूवातीला परत येण्यापूर्वी निश्चित संख्येने स्थळांना भेट दिली.  पुढील काही दशकांमध्ये, गणित, संगणक विज्ञान, रसायनशास्त्र, भौतिकशास्त्र आणि इतर विज्ञानातील अनेक संशोधकांनी या समस्येचा अभ्यास केला. १९६० च्या दशकात, तथापि, एक नवीन दृष्टिकोन तयार करण्यात आला, जो इष्टतम उपाय शोधण्याऐवजी एक उपाय तयार करेल ज्याची लांबी इष्टतम लांबीच्या एकाधिक प्रमाणात मर्यादित असेल आणि असे केल्याने समस्येसाठी खालच्या मर्यादा तयार होतील; या खालच्या मर्यादा नंतर शाखा आणि बांधलेल्या दृष्टिकोनातून वापरल्या जातील. हे करण्यासाठी एक पद्धत म्हणजे आलेखाचे किमान व्याप्तीचे झाड तयार करणे आणि नंतर त्याच्या सर्व कडा दुप्पट करणे, ज्यामुळे इष्टतम प्रवासाची लांबी किमान व्याप्तीच्या झाडाच्या वजनापेक्षा दुप्पट असते.  १९७६ मध्ये क्रिस्टोफिड्स आणि सेरड्यूकोव्ह यांनी स्वतंत्रपणे या दिशेने मोठी प्रगती केली: क्रिस्टोफिड्स-सेरड्यूकोव्ह अल्गोरिदम एक उपाय देते, जे सर्वात वाईट परिस्थितीत, इष्टतम समाधानापेक्षा जास्तीत जास्त १.५ पट जास्त आहे. अल्गोरिदम सोपा आणि वेगवान असल्याने अनेकांना आशा होती की ते जवळजवळ इष्टतम सोल्यूशन पद्धतीला मार्ग देईल. तथापि, सुधारणा होण्याची ही आशा तत्काळ प्रत्यक्षात आली नाही आणि क्रिस्टोफिडेस-सेरड्यूकोव्ह ही 2011 पर्यंत सर्वोत्तम सर्वात वाईट परिस्थितीची पद्धत राहिली, जेव्हा "ग्राफिकल" टीएसपीच्या उपसमुहासाठी (खूप) किंचित सुधारित सान्निध्य अल्गोरिदम विकसित केले गेले. 2020 मध्ये ही किरकोळ सुधारणा पूर्ण (मेट्रिक) टीएसपीमध्ये वाढविण्यात आली.  रिचर्ड एम. कार्प यांनी १९७२ मध्ये हे दाखवून दिले की हॅमिल्टनियन चक्र समस्या एनपी-पूर्ण होती, ज्याचा अर्थ टीएसपीची एनपी-कठोरपणा आहे. यामुळे इष्टतम टूर शोधण्याच्या स्पष्ट संगणकीय अडचणीचे गणितीय स्पष्टीकरण दिले गेले.  १९७० आणि १९८० च्या दशकाच्या उत्तरार्धात मोठी प्रगती झाली, जेव्हा ग्रोचेल, पॅडबर्ग, रिनाल्डी आणि इतरांनी २,३९२ शहरांसह प्रकरणे अचूकपणे सोडविण्यात यश मिळवले.  १९९० च्या दशकात, अॅपलेगेट, बिक्सबी, च्वाटल आणि कुक यांनी कॉनकॉर्ड प्रोग्राम विकसित केला जो अलीकडील बर्याच रेकॉर्ड सोल्यूशन्समध्ये वापरला गेला आहे. गेरहार्ड राईनल्ट यांनी 1991 मध्ये टीएसपीएलआयबी प्रकाशित केले, जे वेगवेगळ्या अडचणीच्या बेंचमार्क उदाहरणांचे संग्रह आहे, जे बर्याच संशोधन गटांनी परिणामांची तुलना करण्यासाठी वापरले आहे. 2006 मध्ये, कुक आणि इतरांनी मायक्रोचिप लेआउट समस्येद्वारे दिलेल्या 85,900 शहरांच्या उदाहरणाद्वारे एक इष्टतम टूरची गणना केली, जी सध्या सर्वात मोठी सोडविलेली टीएसपीएलआयबी उदाहरणे आहे. कोट्यवधी शहरांसह इतर अनेक उदाहरणांसाठी, उपाय शोधले जाऊ शकतात जे इष्टतम फेरफटकाच्या 2 ते 3% च्या आत असल्याची हमी दिली जाते.