Ni nini historia ya mfanyabiashara msafiri tatizo katika miaka yote katika orodha fupi bulleted?
Context:Chanzo cha tatizo la mfanyabiashara anayesafiri hakijulikani. Mwongozo kwa ajili ya kusafiri wafanyabiashara kutoka 1832 anataja tatizo na inajumuisha mfano ziara kwa njia ya Ujerumani na Uswisi, lakini haina matibabu ya hisabati.   William Rowan Hamilton TSP iliundwa kisayansi katika karne ya 19 na mwanahisabati wa Ireland William Rowan Hamilton na mwanahisabati wa Uingereza Thomas Kirkman. Hamilton's icosian mchezo ilikuwa puzzle burudani msingi juu ya kutafuta mzunguko Hamiltonian. fomu ya jumla ya TSP inaonekana kuwa na kwanza alisoma na wanahisabati wakati wa 1930 katika Vienna na katika Harvard, hasa kwa Karl Menger, ambaye inafafanua tatizo, inachukua wazi nguvu-brute algorithm, na anaona yasiyo ya ubora wa jirani karibu heuristic:  Tunaonyesha kwa ujumbe tatizo (kwa kuwa katika mazoezi swali hili lazima kutatuliwa na kila postman, anyway pia na wasafiri wengi) kazi ya kupata, kwa mwisho wengi pointi ambao umbali pairwise ni inayojulikana, njia fupi kuunganisha pointi. Bila shaka, tatizo hili linaweza kutatuliwa kwa majaribio mengi. Sheria ambayo ingekuwa kushinikiza idadi ya majaribio chini ya idadi ya permutations ya pointi kutokana, si inajulikana. Kanuni ya kwamba mtu anapaswa kwanza kwenda kutoka sehemu ya kuanzia hadi sehemu iliyo karibu zaidi, kisha kwenye sehemu iliyo karibu zaidi na hii, na kadhalika, kwa ujumla haitoi njia fupi zaidi.  Ni mara ya kwanza kuchukuliwa kihesabu katika miaka ya 1930 na Merrill M. mafuriko ambaye alikuwa kuangalia kutatua tatizo la njia ya basi shule. Hassler Whitney katika Chuo Kikuu cha Princeton alianzisha upendezi katika tatizo hilo, ambalo aliliita "tatizo la majimbo 48". Chapisho la kwanza kutumia maneno "safari mfanyabiashara tatizo" ilikuwa 1949 RAND Corporation ripoti na Julia Robinson, "On Hamiltonian mchezo (safari mfanyabiashara tatizo)".  Katika miaka ya 1950 na 1960, tatizo hilo lilipata umaarufu mkubwa katika duru za kisayansi huko Ulaya na Marekani baada ya Shirika la RAND huko Santa Monica kutoa zawadi kwa hatua za kutatua tatizo hilo. Michango mashuhuri yalitolewa na George Dantzig, Delbert Ray Fulkerson na Selmer M. Johnson kutoka RAND Corporation, ambao walielezea tatizo kama programu ya mstari wa integer na kuendeleza njia ya ndege ya kukata kwa ufumbuzi wake. Waliandika kile kinachochukuliwa karatasi ya msingi juu ya mada hiyo ambayo kwa njia hizi mpya walitatua mfano na miji 49 kwa ufanisi kwa kujenga ziara na kuthibitisha kuwa hakuna ziara nyingine inaweza kuwa fupi. Dantzig, Fulkerson na Johnson, hata hivyo, walidhani kwamba kutokana na suluhisho karibu na bora tunaweza kupata ubora au kuthibitisha ubora kwa kuongeza idadi ndogo ya usawa wa ziada (kupunguzwa). Walitumia wazo hili kutatua tatizo lao la awali la miji 49 kwa kutumia mfano wa kamba. Waligundua kwamba walihitaji tu kukata 26 ili kupata suluhisho la tatizo lao la miji 49. Wakati karatasi hii hakuwa na kutoa algorithmic mbinu ya TSP matatizo, mawazo ambayo kuweka ndani yake walikuwa muhimu kwa baadaye kujenga sahihi ufumbuzi mbinu kwa ajili ya TSP, ingawa itachukua miaka 15 kupata algorithmic mbinu katika kujenga vipandikizi haya. Kama vile kukata mbinu ndege, Dantzig, Fulkerson na Johnson kutumika tawi na algorithms amefungwa labda kwa mara ya kwanza.  Mnamo 1959, Jillian Beardwood, J.H. Halton na John Hammersley walichapisha makala yenye kichwa "The Shortest Path Through Many Points" katika jarida la Cambridge Philosophical Society. Theorem ya Beardwood<unk>Halton<unk>Hammersley hutoa suluhisho la vitendo kwa tatizo la mfanyabiashara anayesafiri. Waandishi wa kitabu hicho walitumia kanuni ya asymptotic ili kuamua urefu wa njia fupi zaidi ambayo mfanyabiashara anayeanza kazi nyumbani au ofisini anaweza kutumia na kutembelea maeneo kadhaa kabla ya kurudi mahali anapoanzia.  Katika miongo iliyofuata, tatizo hilo lilichunguzwa na watafiti wengi wa hesabu, sayansi ya kompyuta, kemia, fizikia, na sayansi nyinginezo. Katika miaka ya 1960, hata hivyo, mbinu mpya iliundwa, kwamba badala ya kutafuta ufumbuzi bora itazalisha ufumbuzi ambao urefu ni provably bounded na mara ya urefu bora, na kwa kufanya hivyo kujenga mipaka ya chini kwa tatizo; mipaka hii ya chini itakuwa kisha kutumika na tawi na masharti mbinu. Njia moja ya kufanya hivyo ilikuwa kujenga kiwango cha chini spanning mti wa grafu na kisha mara mbili kingo zake zote, ambayo inazalisha bound kwamba urefu wa ziara bora ni zaidi ya mara mbili ya uzito wa kiwango cha chini spanning mti.  Katika 1976, Christofides na Serdyukov bila ya kila mmoja alifanya maendeleo makubwa katika mwelekeo huu: Christofides-Serdyukov algorithm inazalisha ufumbuzi kwamba, katika kesi mbaya, ni zaidi ya mara 1.5 zaidi ya ufumbuzi bora. Kwa kuwa taratibu hiyo ilikuwa rahisi na ya haraka, wengi walitumaini kwamba ingeweza kutokeza njia bora zaidi ya kutatua tatizo hilo. Hata hivyo, matumaini haya kwa ajili ya uboreshaji si mara moja materialized, na Christofides-Serdyukov alibakia njia na bora mbaya zaidi hali ya hadi 2011, wakati (sana) kidogo kuboreshwa approximation algorithm ilitengenezwa kwa ajili ya subset ya "graphical" TSPs. Mnamo mwaka 2020 uboreshaji huu mdogo uliongezwa kwa TSP kamili (ya kipimo).  Richard M. Karp alionyesha mwaka 1972 kwamba tatizo la mzunguko wa Hamiltoni lilikuwa NP-kamili, ambayo inamaanisha ugumu wa NP wa TSP. Hii ilitoa maelezo ya hisabati kwa ugumu dhahiri wa kuhesabu wa kutafuta ziara bora.  Maendeleo makubwa yalifanywa mwishoni mwa miaka ya 1970 na 1980, wakati Grötschel, Padberg, Rinaldi na wengine waliweza kutatua kwa usahihi matukio na miji 2,392, kwa kutumia ndege za kukata na tawi na kushikamana.  Katika miaka ya 1990, Applegate, Bixby, Chvátal, na Cook maendeleo ya mpango Concorde ambayo imekuwa kutumika katika ufumbuzi wa rekodi nyingi za hivi karibuni. Gerhard Reinelt kuchapishwa TSPLIB katika 1991, mkusanyiko wa mifano ya kiwango cha ugumu mbalimbali, ambayo imekuwa kutumika na makundi mengi ya utafiti kwa kulinganisha matokeo. Katika 2006, Cook na wengine kuhesabiwa ziara bora kwa njia ya 85,900 mji mfano kutokana na tatizo microchip mpangilio, sasa kubwa kutatuliwa mfano TSPLIB. Kwa mifano mingine mingi na mamilioni ya miji, ufumbuzi inaweza kupatikana kwamba ni uhakika wa kuwa ndani ya 2 <unk> 3% ya ziara bora.
* Karne ya 19 - kwa mara ya kwanza iliandaliwa kisayansi na mwanahisabati Mwingereza William Rowan Hamilton na mwanahisabati Mwingereza Thomas Kirkman * 1930 - Kwanza alisoma na wanahisabati katika Vienna na katika Harvard, hasa na Karl Menger na Merill M. mafuriko ambaye alikuwa kuangalia kutatua tatizo la shule bus routing. * 1959 - Jillian Beardwood, J.H. Halton na John Hammersley walichapisha makala yenye kichwa "The Shortest Path Through Many Points" katika jarida la Cambridge Philosophical Society, ambayo ilitoa suluhisho la kwanza la vitendo. * 1960 - mbinu mpya ni kuundwa, ambayo kuzalisha ufumbuzi ambao urefu ni provably bounded na mara ya urefu bora. * 1972 - Richard M. Karp alionyesha kuwa tatizo la mzunguko wa Hamiltoni lilikuwa NP-kamilifu, ambayo inamaanisha ugumu wa NP wa tatizo la mfanyabiashara anayesafiri. * 1976 - Christofides na Serdyukov kujitegemea zuliwa algorithm mpya, ambayo inazalisha ufumbuzi kwamba katika kesi mbaya zaidi ni zaidi ya mara 1.5 zaidi ya ufumbuzi bora. * 1990s - Applegate, Bixby, Chvátal, na Cook maendeleo ya mpango Concorde ambayo imekuwa kutumika katika ufumbuzi wa rekodi nyingi za hivi karibuni. * 1991 - Gerhard Reinelt kuchapishwa TSPLIB, mkusanyiko wa mifano benchmark ya ugumu mbalimbali, ambayo imekuwa kutumika na makundi mengi ya utafiti kwa kulinganisha matokeo * 2006 - Cook na wengine kuhesabiwa ziara bora kwa njia ya mfano 85,900-mji kutokana na tatizo la mpangilio microchip, kwa sasa kubwa kutatuliwa mfano TSPLIB. * 2011 - kidogo kuboreshwa approximation algorithm ni maendeleo kwa ajili ya subset ya "graphical" kusafiri mfanyabiashara tatizo. * 2020 - kidogo kuboreshwa approximation algorithm maendeleo kwa ajili ya subset ya "graphical" ni kupanuliwa ili kufunika kamili kusafiri mfanyabiashara tatizo.