කෙටි බුලට් ලැයිස්තුවක් තුළ වසර ගණනාවක් පුරා සංචාරක විකුණුම්කරුගේ ගැටලුවේ ඉතිහාසය කුමක්ද?
සංචාරක විකුණුම්කරුගේ ගැටලුවේ මූලාරම්භය අපැහැදිලි ය. 1832 සිට සංචාරක අලෙවිකරුවන් සඳහා වූ අත්පොතක ගැටලුව ගැන සඳහන් කර ඇති අතර ජර්මනිය සහ ස්විට්සර්ලන්තය හරහා නිදර්ශන චාරිකා ඇතුළත් වේ, නමුත් ගණිතමය ප්‍රතිකාරයක් අඩංගු නොවේ. විලියම් රෝවන් හැමිල්ටන් TSP 19 වැනි සියවසේදී අයර්ලන්ත ජාතික ගණිතඥ විලියම් රෝවන් හැමිල්ටන් සහ බ්‍රිතාන්‍ය ගණිතඥ තෝමස් කර්ක්මන් විසින් ගණිතමය වශයෙන් සකස් කරන ලදී. හැමිල්ටන්ගේ ඉකෝසියන් ක්‍රීඩාව හැමිල්ටෝනියානු චක්‍රයක් සොයා ගැනීම මත පදනම් වූ විනෝදාත්මක ප්‍රහේලිකාවකි. TSP හි සාමාන්‍ය ස්වරූපය 1930 ගණන්වල වියානාහි සහ හාවඩ්හිදී ගණිතඥයින් විසින් ප්‍රථම වරට අධ්‍යයනය කර ඇති බව පෙනේ, විශේෂයෙන් කාල් මෙන්ගර් විසින් ගැටළුව නිර්වචනය කරන, පැහැදිලි තිරිසන් බල ඇල්ගොරිතම සලකා බලන අතර ළඟම ඇති ප්‍රශස්ත නොවන බව නිරීක්ෂණය කරයි. අසල්වැසි හූරිස්ටික්: අපි මැසෙන්ජර් ප්‍රශ්නයෙන් දක්වන්නෙමු (ප්‍රායෝගිකව මෙම ප්‍රශ්නය සෑම තැපැල්කරු විසින්ම විසඳිය යුතු බැවින්, කෙසේ වෙතත් බොහෝ සංචාරකයින් විසින්) යුගල වශයෙන් දුර දන්නා සීමිත බොහෝ ලකුණු සඳහා, ලකුණු සම්බන්ධ කරන කෙටිම මාර්ගය සොයා ගැනීමේ කාර්යය. ඇත්ත වශයෙන්ම, මෙම ගැටළුව බොහෝ අත්හදා බැලීම් මගින් විසඳිය හැකිය. ලබා දී ඇති ලක්ෂ්‍යවල ප්‍රතිවර්තන සංඛ්‍යාවට වඩා අඩුවෙන් අත්හදා බැලීම් ගණන තල්ලු කරන රීති නොදනී. මුලින්ම ආරම්භක ස්ථානයේ සිට ආසන්නතම ස්ථානයට, පසුව මෙයට ආසන්නතම ස්ථානයට යනාදී රීතිය පොදුවේ කෙටිම මාර්ගය ලබා දෙන්නේ නැත. එය ප්‍රථම වරට ගණිතමය වශයෙන් සලකා බලන ලද්දේ 1930 ගණන්වල පාසල් බස් රථ මාර්ගගත කිරීමේ ගැටලුවක් විසඳීමට සොයමින් සිටි මෙරිල් එම්. ප්‍රින්ස්ටන් විශ්ව විද්‍යාලයේ හැස්ලර් විට්නි මෙම ගැටලුව කෙරෙහි උනන්දුවක් ඇති කළේය, ඔහු එය හැඳින්වූයේ "ප්‍රාන්ත 48 ගැටලුව" ලෙසිනි. "සංචාරක විකුණුම්කරු ගැටලුව" යන වාක්‍ය ඛණ්ඩය භාවිතා කරන මුල්ම ප්‍රකාශනය වූයේ 1949 ජූලියා රොබින්සන් විසින් රචිත RAND සංස්ථා වාර්තාවයි, "හැමිල්ටෝනියානු ක්‍රීඩාව (සංචාරක විකුණුම්කරුගේ ගැටලුවක්)". 1950 සහ 1960 ගණන් වලදී, සැන්ටා මොනිකා හි RAND සංස්ථාව ගැටලුව විසඳීමේ පියවර සඳහා ත්‍යාග පිරිනැමීමෙන් පසු යුරෝපයේ සහ එක්සත් ජනපදයේ විද්‍යාත්මක කවයන් තුළ ගැටලුව වැඩි වැඩියෙන් ජනප්‍රිය විය. RAND සංස්ථාවේ ජෝර්ජ් ඩැන්ට්සිග්, ඩෙල්බර්ට් රේ ෆුල්කර්සන් සහ සෙල්මර් එම්. ජොන්සන් විසින් සැලකිය යුතු දායකත්වයක් ලබා දී ඇති අතර, ඔවුන් ගැටලුව පූර්ණ සංඛ්‍යා රේඛීය වැඩසටහනක් ලෙස ප්‍රකාශ කළ අතර එහි විසඳුම සඳහා කැපුම් තල ක්‍රමය සකස් කළහ. මෙම නව ක්‍රම මගින් නගර 49ක් සමඟ චාරිකාවක් ගොඩනඟා වෙනත් කිසිදු සංචාරයක් කෙටි නොවිය හැකි බව ඔප්පු කරමින් ප්‍රශස්ත තත්ත්වයට පත් වූ අවස්ථාවක් ඔවුන් විසින් විසඳන ලද විෂය පිළිබඳ මූලික පත්‍රිකාව ලෙස සැලකෙන දේ ඔවුන් ලියා ඇත. කෙසේ වෙතත්, Dantzig, Fulkerson සහ Johnson අනුමාන කළේ ආසන්න ප්‍රශස්ත විසඳුමක් ලබා දීමෙන් අපට අමතර අසමානතා (කප්පාදු) කුඩා සංඛ්‍යාවක් එකතු කිරීමෙන් ප්‍රශස්ත බව සොයා ගැනීමට හෝ ප්‍රශස්ත බව ඔප්පු කිරීමට හැකි වනු ඇති බවයි. තන්තු ආකෘතියක් භාවිතයෙන් ඔවුන්ගේ මුල් 49 නගර ගැටලුව විසඳීමට ඔවුන් මෙම අදහස භාවිතා කළහ. ඔවුන්ගේ 49 නගර ප්‍රශ්නයට විසඳුමකට පැමිණීමට අවශ්‍ය වූයේ කප්පාදු 26ක් පමණක් බව ඔවුහු සොයා ගත්හ. මෙම පත්‍රිකාව TSP ගැටළු සඳහා ඇල්ගොරිතම ප්‍රවේශයක් ලබා නොදුන් අතර, TSP සඳහා නිශ්චිත විසඳුම් ක්‍රම නිර්මාණය කිරීම සඳහා එය තුළ ඇති අදහස් අත්‍යවශ්‍ය විය, නමුත් මෙම කප්පාදු නිර්මාණය කිරීමේදී ඇල්ගොරිතම ප්‍රවේශයක් සොයා ගැනීමට වසර 15 ක් ගතවනු ඇත. ගුවන් යානා කැපීමේ ක්‍රම මෙන්ම, ඩැන්සිග්, ෆුල්කර්සන් සහ ජොන්සන් ප්‍රථම වරට ශාඛා සහ බැඳුනු ඇල්ගොරිතම භාවිතා කළහ. 1959 දී, Jillian Beardwood, JH Halton සහ John Hammersley විසින් Cambridge Philosophical Society සඟරාවේ "The Shortest Path From Many Points" යන මාතෘකාවෙන් ලිපියක් ප්‍රකාශයට පත් කරන ලදී. Beardwood-Halton-Hammersley ප්‍රමේයය සංචාරක විකුණුම්කරුගේ ගැටලුවට ප්‍රායෝගික විසඳුමක් සපයයි. නිවසකින් හෝ කාර්යාලයකින් ආරම්භ කර නැවත ආරම්භයට පැමිණීමට පෙර නිශ්චිත ස්ථාන ගණනකට පැමිණෙන විකුණුම්කරුවෙකු සඳහා කෙටිම මාර්ගයේ දිග තීරණය කිරීම සඳහා කතුවරුන් අසමමිතික සූත්‍රයක් ව්‍යුත්පන්න කර ඇත. ඊළඟ දශක කිහිපය තුළ, මෙම ගැටලුව ගණිතය, පරිගණක විද්යාව, රසායන විද්යාව, භෞතික විද්යාව සහ වෙනත් විද්යාවන්ගෙන් බොහෝ පර්යේෂකයන් විසින් අධ්යයනය කරන ලදී. කෙසේ වෙතත්, 1960 ගණන්වලදී, නව ප්‍රවේශයක් නිර්මාණය කරන ලදී, ප්‍රශස්ත විසඳුම් සොයනවා වෙනුවට, දිග ප්‍රශස්ත දිගේ ගුණාකාරයකින් මායිම් කර ඇති විසඳුමක් නිපදවනු ඇති අතර, එසේ කිරීමෙන් ගැටලුව සඳහා පහළ සීමාවන් නිර්මාණය වනු ඇත; මෙම පහළ මායිම් පසුව ශාඛා හා බැඳුනු ප්රවේශයන් සමඟ භාවිතා කරනු ඇත. මෙය සිදු කිරීමේ එක් ක්‍රමයක් වූයේ ප්‍රස්ථාරයේ අවම විහිදෙන ගසක් නිර්මාණය කර එහි සියලු දාර දෙගුණ කිරීම, එමඟින් ප්‍රශස්ත චාරිකාවක දිග අවම වශයෙන් විහිදෙන ගසක බර මෙන් දෙගුණයක් වන බව බන්ධනය කරයි. 1976 දී, Christofides සහ Serdyukov එකිනෙකාගෙන් ස්වාධීනව මෙම දිශාවට විශාල දියුණුවක් ලබා ගත්හ: Christofides-Serdyukov ඇල්ගොරිතම විසඳුමක් ලබා දෙයි, නරකම අවස්ථාවක, ප්රශස්ත විසඳුමට වඩා 1.5 ගුණයක් දිගු වේ. ඇල්ගොරිතම සරල සහ ඉක්මන් වූ බැවින්, එය ආසන්න ප්‍රශස්ත විසඳුම් ක්‍රමයකට මග පාදනු ඇතැයි බොහෝ දෙනා බලාපොරොත්තු වූහ. කෙසේ වෙතත්, වැඩිදියුණු කිරීම සඳහා වූ මෙම බලාපොරොත්තුව ක්ෂණිකව ක්‍රියාත්මක නොවූ අතර, ක්‍රිස්ටෝෆයිඩ්ස්-සර්ඩියුකොව් 2011 වන තෙක් හොඳම නරකම අවස්ථාව සහිත ක්‍රමය ලෙස පැවතුනි, "චිත්‍රක" TSPs උප කුලක සඳහා (ඉතා) තරමක් වැඩි දියුණු කළ ආසන්න ඇල්ගොරිතමයක් සංවර්ධනය කරන ලදී. 2020 දී මෙම කුඩා වැඩිදියුණු කිරීම සම්පූර්ණ (මෙට්‍රික්) TSP දක්වා ව්‍යාප්ත විය. රිචඩ් එම්. කාර්ප් 1972 දී හැමිල්ටෝනියානු චක්‍ර ගැටලුව NP-සම්පූර්ණ බව පෙන්නුම් කළේය, එයින් ඇඟවෙන්නේ TSP හි NP-දෘඪතාවයි. මෙය ප්‍රශස්ත චාරිකා සොයාගැනීමේ පෙනෙන ගණනය කිරීමේ දුෂ්කරතාව සඳහා ගණිතමය පැහැදිලි කිරීමක් සැපයීය. Grötschel, Padberg, Rinaldi සහ වෙනත් අය 1970 ගණන්වල අගභාගයේදී සහ 1980 දී විශාල ප්‍රගතියක් ලබා ඇති අතර, ගුවන් යානා සහ අතු කපන ලද සහ බැඳුණු නගර 2,392 ක් දක්වා වූ අවස්ථා නිවැරදිව විසඳීමට සමත් විය. 1990 ගණන්වලදී, Applegate, Bixby, Chvátal සහ Cook විසින් Concorde වැඩසටහන සංවර්ධනය කරන ලද අතර එය බොහෝ මෑත වාර්තාගත විසඳුම් සඳහා භාවිතා කරන ලදී. Gerhard Reinelt විසින් 1991 දී TSPLIB ප්‍රකාශයට පත් කරන ලද අතර, ප්‍රතිඵල සංසන්දනය කිරීම සඳහා බොහෝ පර්යේෂණ කණ්ඩායම් විසින් භාවිතා කරන ලද විවිධ දුෂ්කරතා පිළිබඳ මිණුම් දණ්ඩ එකතුවකි. 2006 දී, කුක් සහ අනෙකුත් අය මයික්‍රොචිප් පිරිසැලසුම් ගැටලුවක් මගින් ලබා දුන් නගර 85,900 ක් හරහා ප්‍රශස්ත සංචාරයක් ගණනය කරන ලදී, දැනට විශාලතම විසඳා ඇති TSPLIB අවස්ථාවයි. මිලියන ගණනක් නගර සහිත වෙනත් බොහෝ අවස්ථාවන් සඳහා, ප්‍රශස්ත සංචාරයකින් 2-3%ක් තුළ සහතික කළ හැකි විසඳුම් සොයාගත හැකිය.
 19 වැනි සියවස - අයර්ලන්ත ජාතික ගණිතඥ විලියම් රෝවන් හැමිල්ටන් සහ බ්‍රිතාන්‍ය ගණිතඥ තෝමස් කිර්ක්මන් විසින් ප්‍රථම වරට ගණිතමය වශයෙන් සකස් කරන ලදී * 1930s - ප්‍රථම වරට වියානා සහ හාවර්ඩ් හි ගණිතඥයින් විසින් අධ්‍යයනය කරන ලදී, විශේෂයෙන් කාල් මෙන්ගර් සහ මෙරිල් එම්. ෆ්ලඩ් විසින් අධ්‍යයනය කරන ලදී. පාසල් බස් මාර්ගගත කිරීමේ ගැටලුවක් විසඳන්න. * 1959 - Jillian Beardwood, JH Halton සහ John Hammersley විසින් "The Shortest Path through Many Points" යන මාතෘකාවෙන් යුත් ලිපියක් Cambridge Philosophical Society සඟරාවේ පළ කළ අතර එය පළමු ප්‍රායෝගික විසඳුම ලබා දුන්නේය. * 1960s - නව ප්‍රවේශයක් නිර්මාණය කරන ලද අතර, එහි දිග ප්‍රශස්ත දිගේ ගුණාකාරයකින් සීමා කළ හැකි විසඳුමක් නිපදවයි. * 1972 - රිචඩ් එම්. කාර්ප් විසින් හැමිල්ටෝනියානු චක්‍ර ගැටලුව NP-සම්පූර්ණ බව පෙන්නුම් කළේය, එයින් ගම්‍ය වන්නේ සංචාරක විකුණුම්කරුගේ ගැටලුවේ NP-දෘඪතාවයි. * 1976 - Christofides සහ Serdyukov ස්වාධීනව නව ඇල්ගොරිතමයක් නිර්මාණය කරන ලද අතර, නරකම අවස්ථාවකදී ප්‍රශස්ත විසඳුමට වඩා 1.5 ගුණයක් දිගු විසඳුමක් ලබා දෙයි. * 1990 දශකය - Applegate, Bixby, Chvátal, සහ Cook විසින් Concorde වැඩසටහන සංවර්ධනය කරන ලද අතර එය බොහෝ මෑත වාර්තාගත විසඳුම් සඳහා භාවිතා කරන ලදී. * 1991 - Gerhard Reinelt විසින් TSPLIB ප්‍රකාශයට පත් කරන ලදී, එය ප්‍රතිඵල සංසන්දනය කිරීම සඳහා බොහෝ පර්යේෂණ කණ්ඩායම් විසින් භාවිතා කරන ලද විවිධ දුෂ්කරතා පිළිබඳ මිණුම් දණ්ඩ එකතුවක් * 2006 - කුක් සහ අනෙකුත් අය මයික්‍රොචිප් පිරිසැලසුමකින් ලබා දුන් නගර 85,900 ක් හරහා ප්‍රශස්ත සංචාරයක් ගණනය කළහ. ගැටලුව, දැනට විසඳා ඇති විශාලතම TSPLIB අවස්ථාව. * 2011 - "චිත්‍රක" සංචාරක විකුණුම්කරු ගැටලුවේ උප කුලක සඳහා තරමක් වැඩි දියුණු කරන ලද ආසන්න ඇල්ගොරිතම සංවර්ධනය කරන ලදී. * 2020 - "චිත්‍රක" හි උප කුලකය සඳහා සංවර්ධනය කරන ලද තරමක් වැඩි දියුණු කරන ලද ආසන්න ඇල්ගොරිතම සම්පූර්ණ සංචාරක විකුණුම්කරුගේ ගැටලුව ආවරණය කිරීම සඳහා දීර්ඝ කර ඇත.