Histori ea bothata ba mohoebi ea tsamaeang ka lilemo tse ngata ke efe lenaneng le lenyenyane le nang le lintlha?
Context:Tšimoloho ea bothata ba barekisi ba tsamaeang ha e hlake. Buka e ngotsoeng ka 1832 ea barekisi ba tsamaeang e bua ka bothata bona'me e akarelletsa mehlala ea maeto a ho tsamaea Jeremane le Switzerland, empa ha e na tlhaloso ea lipalo.   William Rowan Hamilton TSP e ile ea thehoa ka tsela ea lipalo lekholong la bo19 la lilemo ke setsebi sa lipalo sa Ireland William Rowan Hamilton le setsebi sa lipalo sa Brithani Thomas Kirkman. Papali ea Hamilton ea Icosian e ne e le papali ea boithabiso e thehiloeng ho fumaneng potoloho ea Hamiltonian. Sebopeho se akaretsang sa TSP se bonahala se ile sa ithutoa ka lekhetlo la pele ke litsebi tsa lipalo lilemong tsa bo-1930 Vienna le Harvard, haholo-holo ke Karl Menger, ea hlalosang bothata, a nahana ka algorithm ea matla a makatsang, mme a hlokomela ho se be hantle ha moahelani ea haufi le eena:  Re bolela ka bothata ba lenģosa (kaha ha e le hantle potso ena e lokela ho rarolloa ke motho e mong le e mong ea tsamaisang poso, leha ho le joalo le ke baeti ba bangata) mosebetsi oa ho fumana, bakeng sa lintlha tse ngata tse nang le libaka tse tsejoang ka bobeli, tsela e khutšoanyane ka ho fetisisa e hokahanyang lintlha. Ha e le hantle, bothata bona bo ka rarolloa ka liteko tse ngata. Melao e neng e tla sutumetsa palo ea liteko ka tlaase ho palo ea liphetoho tsa lintlha tse fanoeng, ha e tsejoe. Molao oa hore motho o lokela ho qala ka ho tloha moo a qalang teng ho ea sebakeng se haufi le moo a qalang teng, ebe o ea sebakeng se haufi le moo a qalang teng, joalo-joalo, ka kakaretso ha o fane ka tsela e khutšoanyane ka ho fetisisa.  E ile ea hlahlojoa ka lekhetlo la pele ka thuto ea lipalo lilemong tsa bo-1930 ke Merrill M. Flood ea neng a batla ho rarolla bothata ba ho tsamaisa libese tsa sekolo. Hassler Whitney oa Univesithi ea Princeton o ile a thahasella bothata bona, boo a ileng a bo bitsa "bothata ba linaha tse 48". Phatlalatso ea pele-pele e sebelisang poleloana "bothata ba morekisi ea tsamaeang" e ne e le tlaleho ea RAND Corporation ea 1949 ea Julia Robinson, "On the Hamiltonian game (a traveling salesman problem) ".  Lilemong tsa bo-1950 le tsa bo-1960, bothata bona bo ile ba tsebahala haholo lichabeng tsa saense Europe le United States ka mor'a hore RAND Corporation e Santa Monica e fane ka meputso bakeng sa mehato ea ho rarolla bothata bona. George Dantzig, Delbert Ray Fulkerson le Selmer M. Johnson ba tsoang RAND Corporation ba ile ba kenya letsoho haholo, ba ileng ba hlalosa bothata bona e le lenaneo la linomoro tse felletseng'me ba hlahisa mokhoa oa ho seha sefofane bakeng sa tharollo ea sona. Ba ile ba ngola seo ho nkoang e le pampiri ea seminal ka taba eo ka eona ka mekhoa ena e mecha ba ileng ba rarolla mohlala o nang le metse e 49 ho ea ka mokhoa o nepahetseng ka ho haha leeto le ho paka hore ha ho leeto le leng le neng le ka ba khutšoanyane. Leha ho le joalo, Dantzig, Fulkerson le Johnson, ba ile ba nahana hore ha re fuoa tharollo e batlang e le molemo ka ho fetisisa re ka khona ho fumana ho nepahala kapa ho paka ho nepahala ka ho eketsa palo e nyenyane ea ho se lekane ho eketsehileng (ho khaola). Ba ile ba sebelisa khopolo ena ho rarolla bothata ba bona ba pele ba metse e 49 ba sebelisa mohlala oa likhoele. Ba ile ba fumana hore ba hloka feela ho khaola ka makhetlo a 26 e le hore ba rarolle bothata ba metse ea bona e 49. Le hoja pampiri ena e ne e sa fane ka mokhoa oa algorithm ho mathata a TSP, mehopolo e neng e le ka hare ho eona e ne e le ea bohlokoa bakeng sa ho theha mekhoa e nepahetseng ea tharollo bakeng sa TSP, le hoja ho ne ho tla nka lilemo tse 15 ho fumana mokhoa oa algorithm ho theha li-cuts tsena. Ntle le mekhoa ea ho seha sefofane, Dantzig, Fulkerson le Johnson ba ile ba sebelisa li-algorithm tsa makala le tse tlamang mohlomong ka lekhetlo la pele.  Ka 1959, Jillian Beardwood, J.H. Halton le John Hammersley ba ile ba hatisa sehlooho se reng "Tsela e Khuts'oane ka ho Fetisisa e Fetisisang Lintlha Tse Ngata" koranteng ea Cambridge Philosophical Society. Theorem ea Beardwood<unk>Halton<unk>Hammersley e fana ka tharollo e sebetsang bothateng ba morekisi ea tsamaeang. Bangoli ba ile ba fumana mokhoa oa ho fumana bolelele ba tsela e khutšoanyane bakeng sa morekisi ea qalang lapeng kapa ofising'me a etela libaka tse itseng pele a khutlela moo a qalang teng.  Lilemong tse mashome tse ileng tsa latela, bothata bona bo ile ba ithutoa ke bafuputsi ba bangata ba tsoang lithutong tsa lipalo, saense ea k'homphieutha, k'hemistri, fisiks le lithutong tse ling. Leha ho le joalo, lilemong tsa bo-1960, ho ile ha qaptjoa mokhoa o mocha, oo ho e-na le ho batla tharollo e molemohali o neng o tla hlahisa tharollo eo bolelele ba eona bo lekantsoeng ka makhetlo a mangata a bolelele bo botle,'me ka ho etsa joalo e ne e tla etsa meeli e tlase bakeng sa bothata; meeli ena e tlase e ne e tla sebelisoa le makala le mekhoa e tlamang. Mokhoa o mong oa ho etsa sena e ne e le ho etsa sefate se fokolang sa graph ebe o eketsa mahlakore a eona kaofela, e leng se hlahisang moeli oa hore bolelele ba leeto le letle ka ho fetisisa ke boholo ba habeli boima ba sefate se fokolang sa sefate.  Ka 1976, Christofides le Serdyukov ba ikemetse ka bomong ba ile ba tsoela pele haholo ntlheng ena: algorithm ea Christofides-Serdyukov e fana ka tharollo eo, maemong a mabe ka ho fetisisa, e leng nako e telele ho feta 1.5 ho feta tharollo e nepahetseng. Kaha algorithm e ne e le bonolo ebile e potlakile, ba bangata ba ne ba e - na le tšepo ea hore e ne e tla fana ka mokhoa o batlang o le molemo ka ho fetisisa oa ho rarolla bothata. Leha ho le joalo, tšepo ena ea ntlafatso ha ea ka ea phethahala hanghang,'me Christofides-Serdyukov e ile ea lula e le mokhoa o nang le boemo bo bobe ka ho fetisisa ho fihlela ka 2011, ha algorithm e ntlafalitsoeng hanyane e ntlafalitsoe hanyane bakeng sa karolo ea "graphical" TSPs. Ka 2020 ntlafatso ena e nyane e ile ea fetisetsoa ho TSP e felletseng (metric).  Richard M. Karp o ile a bontša ka 1972 hore bothata ba potoloho ea Hamiltonian e ne e le NP-e phethehileng, e leng se bolelang hore NP-e thata ea TSP. Sena se ile sa fana ka tlhaloso ea lipalo bakeng sa bothata bo bonahalang ba ho fumana maeto a matle ka ho fetisisa.  Tsoelo-pele e khōlō e ile ea etsoa qetellong ea bo-1970 le bo-1980, ha Grötschel, Padberg, Rinaldi le ba bang ba khona ho rarolla hantle maemo a nang le litoropo tse 2,392, ba sebelisa lifofane tse sehang le makala le ho hokahana.  Lilemong tsa bo-1990, Applegate, Bixby, Chvátal le Cook ba ile ba qapa lenaneo la Concorde le 'nileng la sebelisoa litharollong tse ngata tsa morao-rao tsa rekoto. Gerhard Reinelt o ile a hatisa TSPLIB ka 1991, pokello ea mehlala ea maemo a fapaneng, e sebelisitsoeng ke lihlopha tse ngata tsa lipatlisiso ho bapisa liphetho. Ka 2006, Cook le ba bang ba ile ba bala leeto le letle ka mohlala oa litoropo tse 85,900 tse fanoeng ke bothata ba ho hlophisoa ha microchip, eo hajoale e leng mohlala o moholo ka ho fetisisa oa TSPLIB o rarollotsoeng. Bakeng sa maemo a mang a mangata a nang le metse e limilione, ho ka fumanoa tharollo e tiisitsoeng hore e tla ba ka hare ho 2<unk>3% ea leeto le nepahetseng.
Lekholong la bo19 la lilemo - e ile ea thehoa ka lekhetlo la pele ke setsebi sa lipalo sa Ireland e leng William Rowan Hamilton le setsebi sa lipalo sa Brithani e leng Thomas Kirkman * Lilemong tsa bo-1930 - E ile ea ithutoa ka lekhetlo la pele ke litsebi tsa lipalo Vienna le Harvard, haholo-holo ke Karl Menger le Merill M. Flood ba neng ba batla ho rarolla bothata ba ho tsamaisa libese tsa sekolo. * 1959 - Jillian Beardwood, J.H. Halton le John Hammersley ba ile ba hatisa sehlooho se reng "Tsela e Khuts'oane ka ho Fetisisa e Fetisisang Lintlha Tse Ngata" koranteng ea Cambridge Philosophical Society, e ileng ea fana ka tharollo ea pele e sebetsang. * Lilemong tsa bo-1960 - ho ile ha etsoa mokhoa o mocha oa ho fumana tharollo eo bolelele ba eona bo lekantsoeng ka makhetlo a mangata ho feta bolelele bo loketseng. 1972 - Richard M. Karp o ile a bontša hore bothata ba potoloho ea Hamiltonian e ne e le NP-e phethehileng, e leng se bolelang bothata ba NP ba bothata ba mohoebi ea tsamaeang. * 1976 - Christofides le Serdyukov ba ile ba qapa algorithm e ncha ka boikemelo, e hlahisang tharollo eo maemong a mabe ka ho fetisisa e leng nako e telele ho feta ea 1.5 ho feta tharollo e nepahetseng. * Lilemong tsa bo-1990 - Applegate, Bixby, Chvátal le Cook ba ile ba qapa lenaneo la Concorde le sebelisitsoeng haufinyane litharollong tse ngata tsa lirekoto. 1991 - Gerhard Reinelt o ile a phatlalatsa TSPLIB, pokello ea mehlala ea litekanyetso tsa maemo a sa tšoaneng, e 'nileng ea sebelisoa ke lihlopha tse ngata tsa lipatlisiso bakeng sa ho bapisa liphello * 2006 - Cook le ba bang ba ile ba bala leeto le letle ka mohlala oa litoropo tse 85,900 tse fanoeng ke bothata ba ho hlophisoa ha microchip, hajoale ke mohlala o moholo ka ho fetisisa oa TSPLIB o rarollotsoeng. * 2011 - Ho ntlafalitsoe hanyenyane algorithm ea approximation e ntlafalitsoeng bakeng sa karoloana ea "graphical" ea mohoebi ea tsamaeang. * 2020 - Ho ntlafalitsoe hanyenyane algorithm ea approximation e ntlafalitsoeng bakeng sa karoloana ea "graphical" e atolosoa ho koahela bothata bo felletseng ba morekisi ea tsamaeang.