ஒரு குறுகிய புல்லட் பட்டியலில் வருடங்கள் முழுவதும் பயணிக்கும் விற்பனையாளர் பிரச்சனையின் வரலாறு என்ன?
பயண விற்பனையாளர் பிரச்சனையின் தோற்றம் தெளிவாக இல்லை. 1832 இல் பயணிக்கும் விற்பனையாளர்களுக்கான கையேடு இந்த சிக்கலைக் குறிப்பிடுகிறது மற்றும் ஜெர்மனி மற்றும் சுவிட்சர்லாந்தின் எடுத்துக்காட்டு சுற்றுப்பயணங்களை உள்ளடக்கியது, ஆனால் கணித சிகிச்சை இல்லை. வில்லியம் ரோவன் ஹாமில்டன் TSP ஐ 19 ஆம் நூற்றாண்டில் ஐரிஷ் கணிதவியலாளர் வில்லியம் ரோவன் ஹாமில்டன் மற்றும் பிரிட்டிஷ் கணிதவியலாளர் தாமஸ் கிர்க்மேன் ஆகியோரால் கணித ரீதியாக உருவாக்கப்பட்டது. ஹாமில்டனின் ஐகோசியன் விளையாட்டு, ஹாமில்டோனியன் சுழற்சியைக் கண்டுபிடிப்பதை அடிப்படையாகக் கொண்ட ஒரு பொழுதுபோக்கு புதிர். TSP இன் பொதுவான வடிவம் 1930 களில் வியன்னா மற்றும் ஹார்வர்டில் கணிதவியலாளர்களால் முதன்முதலில் ஆய்வு செய்யப்பட்டதாகத் தெரிகிறது, குறிப்பாக கார்ல் மெங்கர், சிக்கலை வரையறுத்து, வெளிப்படையான முரட்டு-விசை வழிமுறையைக் கருதுகிறார், மேலும் அருகிலுள்ளவற்றின் உகந்ததாக இல்லாததைக் கவனிக்கிறார். அண்டை வீட்டார்: நாங்கள் மெசஞ்சர் பிரச்சனையால் குறிக்கிறோம் (நடைமுறையில் இந்தக் கேள்வியை ஒவ்வொரு தபால்காரரும், எப்படியும் பல பயணிகளும் தீர்க்க வேண்டும்) ஜோடிவரிசை தூரம் தெரிந்த பல புள்ளிகளுக்கு, புள்ளிகளை இணைக்கும் குறுகிய பாதையைக் கண்டறியும் பணியைக் குறிக்கிறோம். நிச்சயமாக, இந்த சிக்கலை பல சோதனைகள் மூலம் தீர்க்க முடியும். கொடுக்கப்பட்ட புள்ளிகளின் வரிசைமாற்றங்களின் எண்ணிக்கைக்குக் கீழே சோதனைகளின் எண்ணிக்கையைத் தள்ளும் விதிகள் தெரியவில்லை. முதலில் தொடக்கப் புள்ளியில் இருந்து நெருங்கிய இடத்திற்குச் செல்ல வேண்டும், பின்னர் இதற்கு மிக நெருக்கமான புள்ளிக்கு செல்ல வேண்டும் என்ற விதி பொதுவாக குறுகிய பாதையை வழங்காது. இது முதன்முதலில் 1930 களில் மெரில் எம். ஃப்ளட் என்பவரால் கணித ரீதியாகக் கருதப்பட்டது, அவர் பள்ளி பேருந்து வழித்தடப் பிரச்சனையைத் தீர்க்க முயன்றார். பிரின்ஸ்டன் பல்கலைக்கழகத்தில் ஹாஸ்லர் விட்னி இந்த பிரச்சனையில் ஆர்வத்தை உருவாக்கினார், அதை அவர் "48 மாநிலங்கள் பிரச்சனை" என்று அழைத்தார். "பயண விற்பனையாளர் பிரச்சனை" என்ற சொற்றொடரைப் பயன்படுத்தி ஆரம்பகால வெளியீடு ஜூலியா ராபின்சனின் 1949 ஆம் ஆண்டு RAND கார்ப்பரேஷன் அறிக்கை, "ஹாமில்டோனியன் விளையாட்டில் (ஒரு பயண விற்பனையாளர் பிரச்சனை)." 1950 கள் மற்றும் 1960 களில், சாண்டா மோனிகாவில் உள்ள RAND கார்ப்பரேஷன் சிக்கலைத் தீர்ப்பதற்கான நடவடிக்கைகளுக்கு பரிசுகளை வழங்கிய பின்னர், ஐரோப்பா மற்றும் அமெரிக்காவில் உள்ள விஞ்ஞான வட்டங்களில் சிக்கல் பெருகிய முறையில் பிரபலமடைந்தது. RAND கார்ப்பரேஷனைச் சேர்ந்த ஜார்ஜ் டான்ட்ஜிக், டெல்பர்ட் ரே ஃபுல்கர்சன் மற்றும் செல்மர் எம். ஜான்சன் ஆகியோர் குறிப்பிடத்தக்க பங்களிப்புகளைச் செய்தனர், அவர்கள் சிக்கலை ஒரு முழு எண் நேரியல் நிரலாக வெளிப்படுத்தினர் மற்றும் அதன் தீர்வுக்கான வெட்டு விமான முறையை உருவாக்கினர். இந்த புதிய முறைகள் மூலம் அவர்கள் 49 நகரங்களில் உள்ள ஒரு நிகழ்வை ஒரு சுற்றுப்பயணத்தை உருவாக்கி, வேறு எந்த சுற்றுப்பயணமும் குறுகியதாக இருக்க முடியாது என்பதை நிரூபிப்பதன் மூலம் ஒரு நிகழ்வைத் தீர்த்தனர். எவ்வாறாயினும், டான்ட்ஜிக், ஃபுல்கர்சன் மற்றும் ஜான்சன், ஒரு சிறந்த தீர்வைக் கொடுத்தால், குறைந்த எண்ணிக்கையிலான கூடுதல் ஏற்றத்தாழ்வுகளை (வெட்டுகள்) சேர்ப்பதன் மூலம் நாம் உகந்த தன்மையைக் கண்டறியலாம் அல்லது உகந்ததை நிரூபிக்க முடியும் என்று ஊகித்தனர். சரம் மாதிரியைப் பயன்படுத்தி அவர்களின் ஆரம்ப 49 நகரப் பிரச்சனையைத் தீர்க்க இந்த யோசனையைப் பயன்படுத்தினார்கள். அவர்களின் 49 நகரப் பிரச்சனைக்கு தீர்வு காண 26 வெட்டுக்கள் மட்டுமே தேவை என்று அவர்கள் கண்டறிந்தனர். இந்தத் தாள் TSP பிரச்சனைகளுக்கு அல்காரிதம் அணுகுமுறையைக் கொடுக்கவில்லை என்றாலும், TSPக்கான சரியான தீர்வு முறைகளை உருவாக்குவதற்கு அதில் உள்ள யோசனைகள் இன்றியமையாததாக இருந்தது, இருப்பினும் இந்த வெட்டுக்களை உருவாக்குவதில் ஒரு வழிமுறை அணுகுமுறையைக் கண்டறிய 15 ஆண்டுகள் ஆகும். விமானத்தை வெட்டும் முறைகளுடன், டான்ட்ஜிக், ஃபுல்கர்சன் மற்றும் ஜான்சன் முதன்முறையாக கிளை மற்றும் கட்டுப்பட்ட அல்காரிதம்களைப் பயன்படுத்தினர். 1959 ஆம் ஆண்டில், ஜில்லியன் பியர்ட்வுட், ஜே.ஹெச் ஹால்டன் மற்றும் ஜான் ஹேமர்ஸ்லி ஆகியோர் கேம்பிரிட்ஜ் பிலாசபிகல் சொசைட்டியின் இதழில் "தி ஷார்டெஸ்ட் பாத் த்ரூ மெனி பாயின்ட்ஸ்" என்ற தலைப்பில் ஒரு கட்டுரையை வெளியிட்டனர். பியர்டுவுட் ஹால்டன் ஹம்மர்ஸ்லி தேற்றம் பயண விற்பனையாளர் பிரச்சனைக்கு ஒரு நடைமுறை தீர்வை வழங்குகிறது. வீடு அல்லது அலுவலகத்தில் தொடங்கி, தொடக்கத்திற்குத் திரும்புவதற்கு முன் குறிப்பிட்ட எண்ணிக்கையிலான இடங்களைப் பார்வையிடும் விற்பனையாளருக்கான குறுகிய பாதையின் நீளத்தை தீர்மானிக்க ஆசிரியர்கள் ஒரு அறிகுறியற்ற சூத்திரத்தைப் பெற்றனர். அடுத்த தசாப்தங்களில், இந்த சிக்கலை கணிதம், கணினி அறிவியல், வேதியியல், இயற்பியல் மற்றும் பிற அறிவியல் ஆராய்ச்சியாளர்கள் ஆய்வு செய்தனர். இருப்பினும், 1960 களில், ஒரு புதிய அணுகுமுறை உருவாக்கப்பட்டது, உகந்த தீர்வுகளைத் தேடுவதற்குப் பதிலாக ஒரு தீர்வை உருவாக்கும், அதன் நீளம் உகந்த நீளத்தின் பல மடங்குகளால் கட்டுப்படுத்தப்படும், மேலும் அவ்வாறு செய்வது சிக்கலுக்கு குறைந்த வரம்புகளை உருவாக்கும்; இந்த கீழ் எல்லைகள் பின்னர் கிளை மற்றும் பிணைப்பு அணுகுமுறைகளுடன் பயன்படுத்தப்படும். இதைச் செய்வதற்கான ஒரு முறை, வரைபடத்தின் குறைந்தபட்ச பரந்த மரத்தை உருவாக்கி அதன் அனைத்து விளிம்புகளையும் இரட்டிப்பாக்குவதாகும், இது ஒரு உகந்த சுற்றுப்பயணத்தின் நீளம் குறைந்தபட்ச பரந்த மரத்தின் எடையை விட இரண்டு மடங்கு அதிகமாக இருக்கும். 1976 ஆம் ஆண்டில், Christofides மற்றும் Serdyukov ஒருவருக்கொருவர் சுயாதீனமாக இந்த திசையில் ஒரு பெரிய முன்னேற்றம் செய்தனர்: Christofides-Serdyukov அல்காரிதம் ஒரு தீர்வை அளிக்கிறது, மோசமான நிலையில், உகந்த தீர்வை விட அதிகபட்சம் 1.5 மடங்கு அதிகமாகும். அல்காரிதம் எளிமையானது மற்றும் விரைவானது என்பதால், இது ஒரு உகந்த தீர்வு முறைக்கு வழிவகுக்கும் என்று பலர் நம்பினர். இருப்பினும், முன்னேற்றத்திற்கான இந்த நம்பிக்கை உடனடியாக நிறைவேறவில்லை, மேலும் 2011 ஆம் ஆண்டு வரை Christofides-Serdyukov சிறந்த மோசமான சூழ்நிலையில் முறையாகவே இருந்தது, "வரைகலை" TSPகளின் துணைக்குழுவிற்கு (மிகவும்) சற்று மேம்படுத்தப்பட்ட தோராய வழிமுறை உருவாக்கப்பட்டது. 2020 இல் இந்த சிறிய முன்னேற்றம் முழு (மெட்ரிக்) TSP க்கு நீட்டிக்கப்பட்டது. ரிச்சர்ட் எம். கார்ப் 1972 இல் ஹாமில்டோனியன் சுழற்சி பிரச்சனை NP-முழுமையானது என்று காட்டினார், இது TSPயின் NP-கடினத்தன்மையைக் குறிக்கிறது. இது உகந்த சுற்றுப்பயணங்களைக் கண்டறிவதில் வெளிப்படையான கணக்கீட்டு சிரமத்திற்கு கணித விளக்கத்தை அளித்தது. 1970களின் பிற்பகுதியிலும் 1980களிலும் பெரும் முன்னேற்றம் ஏற்பட்டது, அப்போது க்ராட்ஷெல், பேட்பெர்க், ரினால்டி மற்றும் பிறர் 2,392 நகரங்களில் நேர்காணல்களைத் துல்லியமாகத் தீர்க்க முடிந்தது. 1990 களில், Applegate, Bixby, Chv'tal, மற்றும் Cook ஆகியோர் கான்கார்ட் திட்டத்தை உருவாக்கினர், இது பல சமீபத்திய பதிவு தீர்வுகளில் பயன்படுத்தப்பட்டது. Gerhard Reinelt 1991 இல் TSPLIB ஐ வெளியிட்டார், இது பல்வேறு சிரமங்களின் முக்கிய நிகழ்வுகளின் தொகுப்பாகும், இது பல ஆராய்ச்சி குழுக்களால் முடிவுகளை ஒப்பிடுவதற்குப் பயன்படுத்தப்பட்டது. 2006 ஆம் ஆண்டில், குக் மற்றும் பலர் மைக்ரோசிப் தளவமைப்புச் சிக்கலால் வழங்கப்பட்ட 85,900-நகர நிகழ்வின் மூலம் உகந்த சுற்றுப்பயணத்தைக் கணக்கிட்டனர், இது தற்போது மிகப்பெரிய தீர்க்கப்பட்ட TSPLIB நிகழ்வாகும். மில்லியன் கணக்கான நகரங்களில் உள்ள பல நிகழ்வுகளுக்கு, ஒரு உகந்த சுற்றுப்பயணத்தின் 2−3% க்குள் உத்தரவாதம் அளிக்கப்படும் தீர்வுகளைக் காணலாம்.
 19 ஆம் நூற்றாண்டு - முதல் முறையாக ஐரிஷ் கணிதவியலாளர் வில்லியம் ரோவன் ஹாமில்டன் மற்றும் பிரிட்டிஷ் கணிதவியலாளர் தாமஸ் கிர்க்மேன் ஆகியோரால் கணித ரீதியாக வடிவமைக்கப்பட்டது * 1930 கள் - வியன்னா மற்றும் ஹார்வர்டில் உள்ள கணிதவியலாளர்களால் முதன்முதலில் ஆய்வு செய்யப்பட்டது, குறிப்பாக கார்ல் மெங்கர் மற்றும் மெரில் எம். ஃப்ளட் ஆகியோரால் ஆய்வு செய்யப்பட்டது. பள்ளி பேருந்து வழித்தட பிரச்சனையை தீர்க்கவும். * 1959 - ஜிலியன் பியர்ட்வுட், ஜே.ஹெச் ஹால்டன் மற்றும் ஜான் ஹேமர்ஸ்லி ஆகியோர் கேம்பிரிட்ஜ் பிலாசபிகல் சொசைட்டியின் இதழில் "தி ஷார்ட்டஸ்ட் பாத் த்ரூ மெனி பாயின்ட்ஸ்" என்ற தலைப்பில் ஒரு கட்டுரையை வெளியிட்டனர், இது முதல் நடைமுறை தீர்வை வழங்கியது. * 1960கள் - புதிய அணுகுமுறை உருவாக்கப்பட்டது, இது ஒரு தீர்வை உருவாக்குகிறது, அதன் நீளம் உகந்த நீளத்தின் பெருக்கத்தால் கட்டுப்படுத்தப்படுகிறது. * 1972 - ரிச்சர்ட் எம். கார்ப் ஹாமில்டோனியன் சுழற்சிப் பிரச்சனை NP-முழுமையானது என்பதைக் காட்டினார், இது பயண விற்பனையாளர் பிரச்சனையின் NP-கடினத்தன்மையைக் குறிக்கிறது. * 1976 - கிறிஸ்டோஃபைட்ஸ் மற்றும் செர்டியுகோவ் ஆகியோர் சுயாதீனமாக புதிய வழிமுறையைக் கண்டுபிடித்தனர், இது ஒரு தீர்வை அளிக்கிறது, இது மோசமான நிலையில் உகந்த தீர்வை விட 1.5 மடங்கு நீளமானது. * 1990கள் - Applegate, Bixby, Chv'tal, மற்றும் Cook ஆகியோர் கான்கார்ட் நிரலை உருவாக்கினர், இது பல சமீபத்திய பதிவு தீர்வுகளில் பயன்படுத்தப்பட்டது. * 1991 - Gerhard Reinelt TSPLIB ஐ வெளியிட்டார், இது பல்வேறு சிரமங்களின் முக்கிய நிகழ்வுகளின் தொகுப்பாகும், இது பல ஆராய்ச்சி குழுக்களால் முடிவுகளை ஒப்பிடுவதற்குப் பயன்படுத்தப்பட்டது * 2006 - குக் மற்றும் பிறர் மைக்ரோசிப் அமைப்பால் வழங்கப்பட்ட 85,900-நகர நிகழ்வு மூலம் உகந்த சுற்றுப்பயணத்தைக் கணக்கிட்டனர். பிரச்சனை, தற்போது தீர்க்கப்பட்ட மிகப்பெரிய TSPLIB நிகழ்வு. * 2011 - "வரைகலை" பயண விற்பனையாளர் பிரச்சனையின் துணைக்குழுவிற்கு சற்று மேம்படுத்தப்பட்ட தோராய அல்காரிதம் உருவாக்கப்பட்டது. * 2020 - "கிராஃபிக்கல்" இன் துணைக்குழுவிற்காக உருவாக்கப்பட்ட சற்றே மேம்படுத்தப்பட்ட தோராய அல்காரிதம் முழு பயண விற்பனையாளர் பிரச்சனையையும் உள்ளடக்கும் வகையில் நீட்டிக்கப்பட்டது.