Uyini umlando wenkinga yomthengisi ohambahambayo phakathi neminyaka ohlwini olufushane olunezinhlamvu?
Context:Imvelaphi yenkinga yomthengisi ojikelezayo ayicaci. Incwajana yabathengisi abahambahambayo yango-1832 ikhuluma ngale nkinga futhi ihlanganisa nezibonelo zokuvakasha eJalimane naseSwitzerland, kodwa ayinakho ukuchazwa kwezibalo.   UWilliam Rowan Hamilton I-TSP yaklanywa ngokwezibalo ngekhulu le-19 isazi sezibalo sase-Ireland uWilliam Rowan Hamilton nesazi sezibalo saseBrithani uThomas Kirkman. Umdlalo kaHamilton wase-Icosian wawuyiphazili yokuzilibazisa esekelwe ekutholeni umjikelezo kaHamilton. Uhlobo olujwayelekile lwe-TSP lubonakala luqale lwafundwa izazi zezibalo ngeminyaka yo-1930 eVienna naseHarvard, ikakhulukazi nguKarl Menger, ochaza inkinga, ucabanga nge-algorithm ye-brute-force esobala, futhi ubona ukungabi kahle kwe-heuristic yomakhelwane oseduze:  Sibonisa inkinga yesithunywa (ngoba empeleni lo mbuzo kufanele uxazululwe yilowo nalowo oposa, noma kunjalo futhi ngabahambi abaningi) umsebenzi wokuthola, ngamaphuzu amaningi anqunyelwe amabanga awo aziwa, indlela emfushane yokuxhuma amaphuzu. Yiqiniso, le nkinga ingaxazululwa ngokuvivinywa kaningi. Ayikho imithetho eyaziwayo ezokwenza ukuba inani lemizamo libe ngaphansi kwenani lokulungiswa kwamaphuzu anikeziwe. Umthetho wokuthi umuntu kufanele aqale ahambe ukusuka lapho aqala khona aye endaweni eseduze kakhulu, abese eya endaweni eseduze kakhulu nalokhu, njalonjalo, ngokuvamile awunikezi indlela emfushane kakhulu.  Kwaqala ukucatshangelwa ngokwezibalo ngawo-1930 nguMerrill M. Flood owayefuna ukuxazulula inkinga yokuqondisa ibhasi lesikole. UHassler Whitney wasePrinceton University wabangela isithakazelo kule nkinga, ayibiza ngokuthi "inkinga yezifundazwe ezingu - 48". Incwadi yokuqala eyasebenzisa inkulumo ethi "inkinga yomthengisi ohambahambayo" kwakuyincwadi ka-1949 ye-RAND Corporation kaJulia Robinson, ethi "On the Hamiltonian game (a traveling salesman problem)".  Ngawo-1950 nawo-1960, le nkinga yathandwa kakhulu emibuthanweni yesayensi eYurophu nase-United States ngemva kokuba i-RAND Corporation eSanta Monica inikeze imiklomelo ngezinyathelo zokuxazulula le nkinga. Iminikelo ephawulekayo yenziwa nguGeorge Dantzig, uDelbert Ray Fulkerson noSelmer M. Johnson waseRAND Corporation, owaveza le nkinga njengohlelo lomugqa ophelele futhi wasungula indlela yokusika indiza yokuxazulula kwayo. Babhala lokho okubhekwa njengephepha eliyisisekelo ngale ndaba lapho ngalezi zindlela ezintsha baxazulula khona isibonelo esinamadolobha angama-49 ukuze kube ngcono ngokwakha uhambo futhi kufakazelwe ukuthi alukho olunye uhambo olungaba mfushane. Nokho, uDantzig, uFulkerson noJohnson, bacabanga ukuthi uma sinikezwa ikhambi eliseduze nelingcono kakhulu singakwazi ukuthola okungcono kakhulu noma ukufakazela okungcono kakhulu ngokungeza inani elincane lokungalingani okungeziwe (ukusika). Basebenzisa lo mbono ukuxazulula inkinga yabo yokuqala yamadolobha angu-49 besebenzisa imodeli yochungechunge. Bathola ukuthi babedinga ukusikeka okungu-26 kuphela ukuze bafinyelele esixazululweni senkinga yabo yamadolobha angu-49. Nakuba leli phepha alinikezanga indlela ye-algorithmic ezinkingeni ze-TSP, imibono eyayikuyo yayidingeka ekudaleni kamuva izindlela eziqondile zokuxazulula i-TSP, nakuba kwakuzothatha iminyaka engu-15 ukuthola indlela ye-algorithmic ekudaleni lezi zinqamuleli. Kanye nezindlela zokusika ezindizeni, uDantzig, uFulkerson noJohnson basebenzisa amagatsha nama-algorithm aboshiwe mhlawumbe okokuqala ngqa.  Ngo-1959, uJillian Beardwood, uJ. H. Halton noJohn Hammersley banyathelisa isihloko esithi "Indlela Emfushane Kunazo Zonke Ezindaweni Eziningi" kuyi-journal yeCambridge Philosophical Society. I-Beardwood<unk>Halton<unk>Hammersley theorem inikeza ikhambi elisebenzayo lenkinga yomthengisi ohambahambayo. Abalobi bathola ifomula ye-asymptotic yokunquma ubude bomzila omfushane kunayo yonke womthengisi oqala ekhaya noma ehhovisi futhi avakashele inani elithile lezindawo ngaphambi kokuba abuyele lapho eqale khona.  Emashumini eminyaka alandela, le nkinga yafundwa abacwaningi abaningi bezibalo, isayensi yama - computer, isayensi yokuthakwa kwamakhemikhali, isayensi yezinto zemvelo, nezinye. Nokho, ngawo-1960, kwasungulwa indlela entsha, okwathi esikhundleni sokufuna izixazululo ezinhle kakhulu kwakudingeka kukhiqizwe isixazululo ubude baso obungakhonjwa ukuthi bunqunywe ngokuphindaphindiwe kobude obuhle kakhulu, futhi ngokwenza kanjalo kwakudingeka kudaleke imingcele engezansi yenkinga; le mingcele engezansi yayizosetshenziswa ngezindlela ezihambisanayo nezihambisanayo. Enye indlela yokwenza lokhu kwakuwukudala umuthi wokulinganisa ubuncane begrafu bese uphinda kabili yonke imiphetho yayo, okwenza umkhawulo wokuthi ubude bokuvakasha okuhle kakhulu buphindwe kabili kunesisindo somuthi wokulinganisa ubuncane.  Ngo-1976, uChristofides noSerdyukov ngokuzimela komunye nomunye benza intuthuko enkulu kulokhu: i-algorithm kaChristofides-Serdyukov iveza isisombululo, esimweni esibi kakhulu, esiphindwe izikhathi eziyi-1.5 kunesisombululo esihle kakhulu. Njengoba i-algorithm yayilula futhi ishesha, abaningi babenethemba lokuthi yayizonikeza indlela eseduze nesixazululo esihle kakhulu. Kodwa-ke, leli themba lokuthuthuka alizange ligcwaliseke ngokushesha, futhi iChristofides-Serdyukov yahlala iyindlela enesimo esibi kunazo zonke kuze kube ngu-2011, lapho kwakhiwa i-algorithm yokusondela (ethuthukiswe kakhulu) kancane ye-subset ye-TSP "yegraphical". Ngo-2020 lokhu kuthuthukiswa okuncane kwahanjiswa ku-TSP ephelele (metric).  URichard M. Karp wabonisa ngo-1972 ukuthi inkinga yomjikelezo kaHamiltonian yayiphelele ku-NP, okusho ukuthi i-NP-hardness ye-TSP. Lokhu kwanikeza incazelo yezibalo yobunzima bokubalwa kokuthola izinkambo ezinhle kakhulu.  Intuthuko enkulu yenziwa ngasekupheleni kwawo-1970 no-1980, lapho uGrötschel, Padberg, Rinaldi nabanye bekwazile ukuxazulula ngokunembile izibonelo ezinamadolobha afinyelela ku-2,392, besebenzisa izindiza zokusika kanye negatsha futhi baboshwe.  Ngawo-1990, u-Applegate, u-Bixby, u-Chvátal, noCook basungula uhlelo lweConcorde olusetshenziswe ezixazululweni eziningi zakamuva zamarekhodi. UGerhard Reinelt washicilela i-TSPLIB ngo-1991, iqoqo lezimo zokuqhathanisa zobunzima obuhlukahlukene, osekusetshenziswe amaqembu amaningi ocwaningo ukuqhathanisa imiphumela. Ngo-2006, uCook nabanye babala uhambo oluhle kakhulu ngokusebenzisa isibonelo sedolobha elingu-85,900 elinikezwe inkinga yokuhlelwa kwe-microchip, okwamanje okuyisibonelo esikhulu kunazo zonke se-TSPLIB esixazululiwe. Kwamanye amacala amaningi anezigidi zamadolobha, kungatholakala izixazululo eziqinisekisiwe ukuba zibe ngaphakathi kwe-2<unk>3% yohambo oluhle kakhulu.
* Ngekhulu le-19 - kwasungulwa izibalo okokuqala ngqa isazi sezibalo sase-Ireland uWilliam Rowan Hamilton nesazi sezibalo saseBrithani uThomas Kirkman * 1930s - Kwaqale kwafundwa izazi zezibalo eVienna naseHarvard, ikakhulukazi uKarl Menger noMerill M. Flood ababefuna ukuxazulula inkinga yokuhamba kwebhasi lesikole. * Ngo - 1959 - UJillian Beardwood, uJ.H. Halton noJohn Hammersley banyathelisa isihloko esithi "The Shortest Path Through Many Points" kuyi - journal yeCambridge Philosophical Society, eyanikeza ikhambi lokuqala elisebenzayo. * 1960s - indlela entsha yakhiwa, okuyinto ukukhiqiza isixazululo ogama ubude kuyinto provably kuvinjelwe ngu kaningi ubude ekahle. * 1972 - URichard M. Karp wabonisa ukuthi inkinga yomjikelezo kaHamiltonian yayiphelele ku-NP, okusho ukuthi inkinga yomthengisi ohambahambayo i-NP-hardness. * 1976 - UChristofides noSerdyukov ngokuzimela basungula i-algorithm entsha, enikeza isixazululo esisesimweni esibi kakhulu esiphindwe izikhathi ezingu-1,5 kunesixazululo esihle kakhulu. * Ngo - 1990 - U - Applegate, u - Bixby, u - Chvátal, noCook basungula uhlelo i - Concorde olusetshenziswe ezixazululweni eziningi zakamuva zamarekhodi. * 1991 - UGerhard Reinelt washicilela i-TSPLIB, iqoqo lezimo zokuqhathanisa ezinobunzima obuhlukahlukene, esezisetshenziswe amaqembu amaningi ocwaningo ukuqhathanisa imiphumela * 2006 - UCook nabanye babala uhambo oluhle kakhulu ngokusebenzisa isibonelo sedolobha elingu-85,900 elinikezwe inkinga yokuhlelwa kwe-microchip, okwamanje okuyisibonelo esikhulu kunazo zonke se-TSPLIB esixazululiwe. * 2011 - I-algorithm esondele kancane ithuthukisiwe yenzelwe isethi engaphansi yenkinga yomthengisi ohambahambayo "egraphic". * 2020 - I-algorithm yokuqhathanisa ethuthukiswe kancane eyenzelwe isethi engezansi "yemifanekiso" iyanwetshwa ukuze ihlanganise inkinga ephelele yomthengisi ohambahambayo.