Waa maxay taariikhda dhibaatada ganacsadaha safarka ah sanadihii la soo dhaafay ee liiska dhibcaha yar?
Context:Asalka dhibaatada ganacsadaha safarka ah ma cadda. Buug-gacmeed loogu talagalay ganacsatada safarka ah ee ka soo jeeda 1832 ayaa ku xusan dhibaatada waxaana ku jira tusaalooyin safarro ah oo loo maro Jarmalka iyo Switzerland, laakiin ma jiraan wax daaweyn ah oo xisaab ah.   William Rowan Hamilton TSP waxaa si xisaab ahaan ah u qaabeeyey qarnigii 19aad xisaabyahankii reer Ireland William Rowan Hamilton iyo xisaabyahankii Ingiriiska Thomas Kirkman. Ciyaarta Icosia ee Hamilton waxay ahayd halxiraale madadaalo oo ku saleysan helitaanka wareegga Hamilton. Qaabka guud ee TSP wuxuu u muuqdaa in markii ugu horreysay ay barteen xisaabiyeyaashu intii lagu jiray 1930-meeyadii Vienna iyo Harvard, gaar ahaan Karl Menger, oo qeexaya dhibaatada, wuxuu tixgeliyaa algorithm-ka xoogga xoogan ee muuqda, wuxuuna fiiriyaa aan fiicnayn ee deriska ugu dhow ee heuristic:  Waxaan ku tilmaameynaa dhibaatada farriinta (maadaama ficil ahaan su'aashan ay tahay in lagu xaliyo qof kasta oo boostada, si kasta oo ay tahay sidoo kale dad badan oo safar ah) hawsha ah in la helo, dhibco badan oo dhammaad leh oo masaafada u dhexeysa loo yaqaan, wadada ugu gaaban ee isku xirta dhibcaha. Dabcan, dhibaatadan waa la xalin karaa iyadoo la isticmaalayo tijaabooyin badan. Xeerarka hoos u riixaya tirada tijaabooyinka ee ka hooseeya tirada isku-habeynta dhibcaha la bixiyay, lama yaqaan. Xeerka ah in qofku marka hore ka bilaabo meesha uu ka bilaabayo ilaa meesha ugu dhow, ka dibna ilaa meesha ugu dhow, iwm, guud ahaan ma bixiyo wadada ugu gaaban.  Waxaa markii ugu horeysay xisaab ahaan loo tixgeliyey 1930-yadii Merrill M. Flood oo raadinayay xalinta dhibaatada marinka basaska dugsiga. Hassler Whitney oo ka tirsan jaamacada Princeton ayaa soo saaray xiisaha dhibaatada, kaasoo uu ugu yeeray "dhibaatada 48 gobol". Qoraalkii ugu horreeyay ee adeegsanaya weedha "dhibaatada iibiyaha safarka ah" wuxuu ahaa warbixintii shirkadda RAND ee 1949 ee Julia Robinson, "On the Hamiltonian game (a traveling salesman problem) ".  Sanadihii 1950-naadkii iyo 1960-naadkii, dhibaatadu waxay caan ka noqotay goobaha sayniska ee Yurub iyo Mareykanka ka dib markii Shirkadda RAND ee Santa Monica ay abaalmarino u fidisay tallaabooyinka lagu xallinayo dhibaatada. Waxyaabaha muhiimka ah ee ay gacan ka geysteen waxaa ka mid ahaa George Dantzig, Delbert Ray Fulkerson iyo Selmer M. Johnson oo ka tirsan shirkadda RAND Corporation, kuwaas oo dhibaatada ku muujiyay barnaamij toosan oo nambar buuxa ah isla markaana horumariyay habka goynta diyaaradda xallinta. Waxay qoreen waxa loo tixgeliyo warqadda aasaasiga ah ee mawduuca taas oo qaababkan cusub ay ku xalliyeen tusaale ahaan 49 magaalo oo ku habboon iyaga oo dhisaya dalxiis isla markaana caddeynaya in dalxiis kale uusan ka gaabin karin. Dantzig, Fulkerson iyo Johnson, si kastaba ha noqotee, waxay ku qiyaaseen in marka la eego xalka ugu dhow ee ugu fiican aan awoodi karno inaan helno ugu fiican ama aan caddeyno ugu fiican adoo ku daraya tiro yar oo isku dheelitirnaan dheeraad ah (jaritaan). waxay isticmaaleen fikradan si ay u xaliyaan dhibaatadii ugu horeysay ee 49 magaalo iyaga oo isticmaalaya qaab isku xigxiga waxay ogaadeen in 26 go'aan oo keliya ay u baahan yihiin si ay u gaaraan xalka dhibaatada 49 magaalo Inkastoo warqadan aysan bixin hab algorithmic ah oo ku saabsan dhibaatooyinka TSP, fikradaha ku jira waxay ahaayeen kuwo lama huraan u ah abuurista habab xallinta saxda ah ee TSP, in kasta oo ay qaadan doonto 15 sano in la helo hab algorithmic ah oo lagu abuuro jaristaas. Marka lagu daro hababka goynta diyaaradda, Dantzig, Fulkerson iyo Johnson waxay adeegsadeen algorithms laamo iyo laamo laga yaabee markii ugu horreysay.  Sanadkii 1959, Jillian Beardwood, J.H. Halton iyo John Hammersley waxay daabaceen maqaal cinwaan looga dhigay "Wadada ugu gaaban ee dhinacyo badan" oo ku saabsan joornaalka Bulshada Falsafadda ee Cambridge. The Beardwood <unk> Halton <unk> Hammersley theorem wuxuu xal wax ku ool ah u yahay dhibaatada ganacsadaha safarka ah. Qoraayaashu waxay soo saareen qaaciddo asymptotic ah si loo go'aamiyo dhererka wadada ugu gaaban ee iibiyaha ka bilaabaya guriga ama xafiiska oo booqda tiro goobo ah oo go'an ka hor inta uusan ku laaban bilowga.  Tobannaankii sano ee soo socda, cilmi baarayaal badan oo ka tirsan xisaabta, sayniska kumbuyuutarka, kiimikada, fiisikiska, iyo cilmiga sayniska kale ayaa baaray dhibaatadan. Sanadihii 1960-kii, si kastaba ha ahaatee, waxaa la abuuray hab cusub, taas oo halkii laga raadin lahaa xalka ugu fiican waxay soo saari lahayd xalka oo dhererkiisu si cad u xaddidan yahay dhererka ugu fiican, sidaas darteedna waxay abuuri doontaa xadka hoose ee dhibaatada; xadka hoose ayaa markaa loo isticmaali doonaa laamaha iyo hababka xaddidan. Mid ka mid ah habka loo sameynayo tani waxay ahayd in la abuuro geed ugu yar ee garaafka ka dibna la labanlaabo dhammaan cidhifyadiisa, taas oo soo saarta xadka in dhererka safarka ugu habboon uu ugu badnaan yahay laba jeer culeyska geedka ugu yar.  Sanadkii 1976, Christofides iyo Serdyukov si madaxbanaan oo midba midka kale ka mid ah ayaa horumar weyn ka sameeyay jihadaas: Christofides-Serdyukov algorithm wuxuu soo saaraa xalka, xaalada ugu xun, ugu badnaan waa 1.5 jeer ka dheer xalka ugu fiican. Maadaama ay algorithmku ahaa mid fudud oo dhakhso leh, dad badan ayaa rajeynayay in ay jidka u furi doonto habka xalka ugu dhow. Si kastaba ha noqotee, rajadii hagaajinta si dhakhso leh uma aysan dhicin, Christofides-Serdyukov wuxuu sii ahaaday habka ugu wanaagsan ee xaalada ugu xun ilaa 2011, markii (aad) waxyar loo hagaajiyay algorithm qiyaas loogu talagalay qaybta "graphical" TSPs. Sanadkii 2020 horumarkan yar ayaa loo kordhiyay TSP-ga buuxa (mitirka).  Richard M. Karp wuxuu muujiyay 1972 in dhibaatada wareegga Hamilton ay ahayd NP-dhameystiran, taas oo muujineysa adkaanta NP ee TSP. Tani waxay bixisey sharaxaad xisaab ahaan ah oo ku saabsan dhibaatada xisaabinta ee muuqata ee helitaanka safarada ugu fiican.  Horumar weyn ayaa la sameeyay dabayaaqadii 1970-yadii iyo 1980-yadii, markii Grötschel, Padberg, Rinaldi iyo kuwo kale ay ku guuleysteen inay si sax ah u xalliyaan kiisaska illaa 2,392 magaalo, iyagoo adeegsanaya diyaaradaha goynta iyo laanta iyo ku xiran.  Sannadihii 1990-meeyadii, Applegate, Bixby, Chvátal, iyo Cook waxay soo saareen barnaamijka Concorde oo loo adeegsaday xalal badan oo rikoor ah oo dhowaan la soo saaray. Gerhard Reinelt wuxuu daabacay TSPLIB sanadkii 1991, oo ah ururinta tijaabooyinka tijaabada ah ee kala duwan ee kala duwan, kaas oo ay adeegsadeen kooxo badan oo cilmi baaris ah si loo isbarbar dhigo natiijooyinka. Sannadkii 2006, Cook iyo kuwa kale waxay xisaabiyeen safarka ugu wanaagsan ee loo maro tusaale 85,900-magaalo oo ay siisay dhibaatada qaabeynta microchip, oo hadda ah kiiskii ugu weynaa ee TSPLIB ee la xaliyo. Xaalado kale oo badan oo malaayiin magaalo ku yaal, xal ayaa la heli karaa taas oo la damaanad qaadayo inay kujirto 2-3% safarka ugufiican.
* qarnigii 19aad - waxaa markii ugu horreysay si xisaab ahaan u qaabeeyey xisaabyahankii reer Ireland William Rowan Hamilton iyo xisaabyahankii Ingiriiska Thomas Kirkman * 1930-kii - Markii ugu horreysay waxaa bartay xisaabyahanno ku sugan Vienna iyo Harvard, gaar ahaan Karl Menger iyo Merill M. Flood oo raadinayay xalinta dhibaatada waddooyinka basaska dugsiga. * 1959 - Jillian Beardwood, J.H. Halton iyo John Hammersley waxay daabaceen maqaal cinwaan looga dhigay "Jidka ugu gaaban ee loo maro dhibco badan" oo ku yaal joornaalka Bulshada Falsafadda ee Cambridge, kaas oo bixiyay xalka ugu horreeya ee wax ku oolka ah. * 1960-kii - waxaa la sameeyay hab cusub, kaas oo soo saara xalka dhererkiisu si cad u xaddidan yahay oo leh dhererka ugu habboon. 1972 - Richard M. Karp wuxuu muujiyay in dhibaatada wareegga Hamilton ay ahayd NP-dhameystiran, taas oo muujineysa NP-adagida dhibaatada iibiyaha socda. * 1976 - Christofides iyo Serdyukov waxay si madaxbanaan u soo saareen algorithm cusub, kaas oo soo saara xalka taas oo kiiska ugu xun ugu badnaan 1.5 jeer ka dheer xalka ugu fiican. * 1990s - Applegate, Bixby, Chvátal, iyo Cook waxay soo saareen barnaamijka Concorde oo loo adeegsaday xalal badan oo rikoor ah oo dhowaan la sameeyay. 1991 - Gerhard Reinelt ayaa daabacay TSPLIB, oo ah ururinta tijaabooyinka tijaabada ah ee kala duwan ee kala duwan, kaas oo loo adeegsaday kooxo badan oo cilmi baaris ah si loo isbarbar dhigo natiijooyinka * 2006 - Cook iyo kuwa kale waxay xisaabiyeen safarka ugu wanaagsan ee 85,900-magaalo ee ay bixiso dhibaatada qaabeynta microchip, oo hadda ah kiiskii ugu weynaa ee TSPLIB ee la xaliyo. * 2011 - Wax yar oo la hagaajiyay oo loo yaqaan 'approximation algorithm' ayaa loo sameeyay qaybta "graphical" ee dhibaatada iibiyaha socda. * 2020 - Algorithm-ka wax yar la hagaajiyay ee loo soo saaray qaybta "graphical" ayaa loo kordhiyay si loo daboolo dhibaatada ganacsadaha socdaalka oo dhan.