Ndeipi iri nhau yechinetso chomutengesi anofambira mumakore ose ari munhevedzano pfupi ine mabara?
Context:Mabviro edambudziko revatengesi vanofambira haana kujeka. Bhuku ravatengesi vanofambira ra1832 rinotaura nezvedambudziko racho uye rinosanganisira mienzaniso yenzendo dzokuGermany neSwitzerland, asi harina rondedzero yemasvomhu.   William Rowan Hamilton TSP yakagadzirwa nemasvomhu muzana remakore rechi19 nemunyori wemasvomhu wokuIreland William Rowan Hamilton uye nemunyori wemasvomhu wokuBritain Thomas Kirkman. Mutambo waHamilton weIcosian waiva mutambo wokuzvivaraidza wakavakirwa pakuwana kutenderera kwaHamiltonian. Maumbirwo akajairika eTSP anoratidzika kunge akatanga kuongororwa nemasvomhu mukati memakore e1930 muVienna neHarvard, kunyanya naKarl Menger, uyo anotsanangura dambudziko, anofunga nezvekuratidzika kwehutano hwehutano, uye anocherechedza kusagadzikana kwevavakidzani vepedyo vepedyo:  Tinoratidzira nechinetso chomutumwa (sezvo muchiito mubvunzo uyu uchifanira kugadziriswa nomuposita mumwe nomumwe, zvisineiwo navafambi vazhinji) basa rokuwana, nokuda kwamapfundo akawanda ane madaro akaparadzana anozivikanwa, nzira ipfupi zvikurusa inobatanidza mapfundo. Chokwadika, chinetso ichi chinogadziriswa nokuedza kwakawanda. Mitemo iyo yaizosundira chiverengero chemiedzo pasi pechiverengero chemichinjiko yamapfundo akapiwa, haizivikanwi. Mutemo wokuti munhu anofanira kutanga kuenda kubva panzvimbo yokutanga kusvika panzvimbo iri pedyo zvikuru, ipapo kusvika kunzvimbo iri pedyo zvikuru nayo, nezvimwewo, kazhinji kazhinji haugumi nenzira ipfupi zvikuru.  Yakatanga kuongororwa nemasvomhu muma1930 naMerrill M. Flood uyo akanga achitsvaka kugadzirisa chinetso chokufambisa mabhazi echikoro. Hassler Whitney paPrinceton University akaita kuti vanhu vafarire chinetso chacho, chaakadana kuti "chinetso chenyika 48". Chinyorwa chekare chakashandisa mashoko okuti "chinetso chemutengesi anofamba-famba" chaiva mushumo weRAND Corporation wa1949 naJulia Robinson, "Pamutambo weHamiltonian (chinetso chemutengesi anofamba-famba)".  Muma1950 nama1960, chinetso chacho chakava chakakurumbira zvikuru mumasangano ezvesayenzi muEurope neUnited States pashure pokunge RAND Corporation muSanta Monica yakapa mibayiro nokuda kwenzira dzokugadzirisa dambudziko racho. Mipiro inokosha yakaitwa naGeorge Dantzig, Delbert Ray Fulkerson naSelmer M. Johnson vanobva kuRAND Corporation, avo vakaratidza chinetso chacho sechirongwa chetsetse chechiverengero chakaperera uye vakagadzira mutoo wokugadzira ndege nokuda kwemhinduro yacho. Ivo vakanyora icho chinorangarirwa sebasa rinokosha panhau yacho umo kupfurikidza neiyi mitoo mitsva ivo vakagadzirisa muenzaniso namaguta 49 kusvikira kuukoshi hwakanakisisa kupfurikidza nokuvaka rwendo uye kubvumikisa kuti hakuna rumwe rwendo rwaigona kuva mupfupi. Dantzig, Fulkerson naJohnson, zvisinei, vakafungidzira kuti kupiwa mhinduro iri pedyo yakanakisisa tingagona kuwana zvakanakisisa kana kuratidza zvakanakisisa nokuwedzera nhamba duku yezvisina kuenzana zvakawedzerwa (kucheka). Vakashandisa pfungwa iyi kupedza chinetso chavo chokutanga chemaguta 49 vachishandisa muenzaniso wetsamba. Vakawana kuti vaida bedzi kucheka 26 kuti vasvike pamhinduro yechinetso chavo chemaguta 49. Nepo pepa iri rakanga risina kupa nzira yealgorithmic kumatambudziko eTSP, pfungwa dzaivamo dzaikosha pakugadzira nzira dzakarurama dzekugadzirisa dzeTSP, kunyange zvaizotora makore gumi nemashanu kuwana nzira yealgorithmic mukugadzira zvidimbu izvi. Kunze kwokugadzira mapurani, Dantzig, Fulkerson naJohnson vakashandisa nzira dzokugadzira mapazi uye dzokubatanidza zvimwe kokutanga.  Muna 1959, Jillian Beardwood, J.H. Halton naJohn Hammersley vakabudisa nyaya yaiva nomusoro unoti "The Shortest Path Through Many Points" mumagazini yeCambridge Philosophical Society. Beardwood<unk>Halton<unk>Hammersley theorem inopa mhinduro inoshanda kudambudziko romutengesi anofamba. Vanyori vacho vakashandisa nzira yokufungidzira kuti vazive kureba kwenzira pfupi kupfuura dzose yomutengesi anotanga ari pamba kana kuti muhofisi obva ashanyira nzvimbo dzinoverengeka asati adzokera kwaakatanga.  Mumakumi emakore akazotevera, dambudziko iri rakadzidzwa nevatsvakurudzi vakawanda vemasvomhu, zvemakombiyuta, zvemakemikari, zvephysics, nezvimwewo. Mumakore ekuma 1960, zvisinei, nzira itsva yakasikwa, iyo panzvimbo pokutsvaka mhinduro dzakanakisisa yaizobereka mhinduro iyo urefu hwayo hunopedzwa nehuwandu hwehurefu hwakareba, uye mukuita kudaro hwaizogadzira miganhu yakaderera yechinetso; iyi miganhu yakaderera yaizoshandiswa nemapazi uye nzira dzakasungwa. Imwe nzira yokuita izvi yakanga iri yokugadzira muti muduku unotambanudza wegrafu uye ipapo kaviri micheto yayo yose, iyo inobereka muganhu kuti urefu hwerwendo rwakanaka zvikuru hunopfuura kaviri uremu hwomuti muduku unotambanudza.  Muna 1976, Christofides naSerdyukov vakabudirira zvikuru mune izvi: Christofides-Serdyukov algorithm inopa mhinduro iyo, mumamiriro ezvinhu akaipisisa, inenge yakareba kakapetwa ka1.5 kupfuura mhinduro yakanaka. Sezvo gadziriro yacho yakanga iri nyore uye ichikurumidza, vakawanda vaitarisira kuti yaizopa nzira yokuwana nayo mhinduro yakanakisisa. Zvisinei, tariro iyi yekuvandudza haina kuzadzikiswa pakarepo, uye Christofides-Serdyukov akaramba ari nzira ine yakanakisa mamiriro ezvinhu akaipisisa kusvika 2011, apo (zvishoma) yakagadziridzwa approximation algorithm yakagadzirirwa subset ye "graphical" TSPs. Muna 2020 kuvandudzwa kuduku uku kwakawedzerwa kune yakazara (metric) TSP.  Richard M. Karp akaratidza muna 1972 kuti dambudziko reHamiltonian cycle raive NP-rakakwana, izvo zvinoreva NP-kuoma kweTSP. Ikoku kwakapa tsananguro yemasvomhu nokuda kwokuva kwakaoma kwokurangarira kwokuwana nzendo dzakanakisisa.  Kufambira mberi kukuru kwakaitwa mukupera kwema1970 na1980, apo Grötschel, Padberg, Rinaldi navamwe vakakwanisa kugadzirisa zvakarurama zviitiko nemaguta anosvika 2.392, vachishandisa ndege dzekucheka uye bazi uye vakasungwa.  Mumakore ekuma1990, Applegate, Bixby, Chvátal, naCook vakagadzira purogiramu yeConcorde iyo yakashandiswa mumhinduro dzakawanda dzekurekodha dzichangobva kuitika. Gerhard Reinelt akabudisa TSPLIB muna 1991, muunganidzwa wezviitiko zvekutarisa zvekuoma kwakasiyana-siyana, izvo zvakashandiswa nemapoka mazhinji ekutsvakurudza kuenzanisa migumisiro. Muna 2006, Cook nevamwe vakaverenga rwendo rwakanakisa kuburikidza ne85,900-guta rakapihwa nedambudziko rekuisa microchip, parizvino rakakura kwazvo rakagadziriswa TSPLIB. Nokuda kwezvimwe zviitiko zvakawanda zvine mamiriyoni emaguta, mhinduro dzinogona kuwanwa dzinovimbiswa kuva mukati me2<unk>3% yenzendo dzakanakisisa.
* 19th century - mathematically formulated for the first time by the Irish mathematician William Rowan Hamilton and by the British mathematician Thomas Kirkman * 19th century - mathematically formulated for the first time by the Irish mathematician William Rowan Hamilton and by the British mathematician Thomas Kirkman * 1930s - Yakatanga kuongororwa nenyanzvi dzemasvomhu muVienna uye paHarvard, kunyanya naKarl Menger naMerill M. Flood uyo akanga achitsvaka kugadzirisa chinetso chokufambisa bhazi rechikoro. * 1959 - Jillian Beardwood, J.H. Halton naJohn Hammersley vakabudisa nyaya yaiva nomusoro unoti "The Shortest Path Through Many Points" mumagazini yeCambridge Philosophical Society, iyo yakapa mhinduro yokutanga inoshanda. * 1960s - nzira itsva inogadzirwa, iyo inogadzira mhinduro iyo urefu hwayo hunopedzwa nehuwandu hwehurefu hwakanaka. * 1972 - Richard M. Karp akaratidza kuti dambudziko reHamiltonian cycle raive NP-rakakwana, izvo zvinoreva NP-kuoma kwedambudziko remutengesi anofamba. * 1976 - Christofides naSerdyukov vakazvimiririra vakagadzira algorithm itsva, iyo inobereka mhinduro iyo mumamiriro ezvinhu akaipisisa inenge yakareba nguva 1.5 kupfuura mhinduro yakanakisisa. * 1990s - Applegate, Bixby, Chvátal, naCook vakagadzira purogiramu yeConcorde iyo yakashandiswa mumhinduro zhinji dzekurekodha dzichangobva kuitika. * 1991 - Gerhard Reinelt akabudisa TSPLIB, muunganidzwa wemienzaniso yekuenzanisa yezvakaoma zvakasiyana, iyo yakashandiswa nemapoka mazhinji ekutsvakurudza kuenzanisa migumisiro * 2006 - Cook nevamwe vakaverenga rwendo rwakanaka kuburikidza nechiitiko chemaguta 85,900 chakapihwa nedambudziko rekuisa microchip, parizvino ndiyo yakakura kwazvo yakagadziriswa TSPLIB. * 2011 - Yakagadziridzwa zvishoma yekufungidzira algorithm yakagadzirirwa chikamu che "graphical" chinetso chemutengesi anofamba. * 2020 - The zvishoma nani approximation algorithm dzakabudirira nokuda subset pamusoro "graphical" rwunotambanudzwa kufukidza zvizere kutama mutengesi dambudziko.