Az utazó ügynök problémája
gráfelméleti probléma / From Wikipedia, the free encyclopedia
Az utazó ügynök problémája egy kombinatorikus optimalizálási probléma. Kiváló példa a bonyolultság-elmélet által NP-nehéznek nevezett problémaosztályra. Az utazó ügynök problémájához kapcsolódó matematikai feladatokkal először Sir William Rowan Hamilton és Thomas Penyngton Kirkman foglalkoztak az 1800-as években. Hamilton és Kirkman ezen korai munkájáról szóló értekezés megtalálható a Graph Theory 1736-1936.[1] című munkában. Az utazóügynök-probléma általános változatát először az 1930-as években vizsgálták Bécsben, illetve a Harvardon, kiváltképp Karl Menger. A problémával később Hassler Whitney és Merrill M. Flood is komolyan foglalkozott a Princetoni Egyetemen. Az utazóügynök-probléma fejlődéséről, valamint Menger és Whitney kapcsolatáról részletes információk találhatók Alexander Schrijver publikációjában.[2]