Pro upřesnění, jak Christofides, tak nový algoritmus, neřeší obecné TSP, ale jen metrické TSP -- mezi každými dvěma body musí být přímá cesta v obou směrech za stejnou cenu a platí trojúhelníková nerovnost. Obecné TSP aproximovat vůbec nejde (s konstantním faktorem) a naopak třeba TSP v rovině jde aproximovat s faktorem 1+c pro libovolně malé c.
Len tak zo zvedavosti, co keby sme vzali suradnice miest a umiestnili ich do xy/2d mriezky s tym ze mriezka bude odstupnovana tak ze kazde mesto/bod musi lezat v co najvecsom samostatnom stvorci. cize velkost kachliciek na x/y bude zavysiet od vzdialenosti jendotlivych miest medzi sebou. moze to byt 1km stvorce ale aj 1000km stvorce napriklad. no a potom pri prechadzani mestami len skaceme na stvorce meiest ktore maju najmenej stvorcov medzi sebou. inak povedane rozdelime vzdialenost medzi mestami z absolutnej dlzky na "kvantitativnu" a velkost stvorca/"kvantu" diktuje hustota miest sama o sebe. na prvy krat asi idealnu trasu nenajdeme ale mohlo by to znizit pocet slepich ciest.
A to ta len tak po nedelnom obede napadla chvilka poezie a nevedel si co s tym tak si nieco vymyslel, coze na tom ze sa tomu venuju matematici dlhe hodiny ty si to proste vymyslel po dobrom nedelnom obede.
Ona to není tak špatná heuristika, ovšem s problémem hned na začátku - to rozdělování do čtverců bude náročnější, než hledání nejkratší cesty..
> nenarušuje to řešení trojúhelníkovou nerovnost?
to nicemu nevadi, ale v zadani nemate souradnice, proto nedava smysl bavit se o ctvercich.
12. 10. 2020, 10:16 editováno autorem komentáře
puvodni zadani takovou podminku neobsahuje, podle me grafove problemy obecne s nicim takovym nepocitaji, kdyz bude existovat hrana z A do B, ktera je delsi nez cesta pres nejaky dalsi uzel, tak se do reseni nedostane.
Právě že se může dostat. Obchodní cestující musí projít každým městem právě jednou. A tou delší hranou může jít proto, že se nějakému uzlu potřebuje vyhnout aby ho nenavštívíl dvakrát.
Tohle slyším poprvé. Co jsem zatím potkal, tak to byla vždycky Hamiltonovská kružnice. Ještě jsem viděl pár zobecnění, ale tam to bylo trochu o něčem jiném než o opakování měst.
Byl by nějaký odkaz nebo klíčové slovo?
Vypadá to, že to často bude jen opomenutí (třeba na české Wikipedii v úvodní definici problému), ale třeba Martin Kot explicitně uvádí obě varianty.
Ono to má ještě jednu pihu na kráse: se souřadnicemi lze operovat v případě, že je znáte - tedy že jde například o zeměpisné údaje. Ale v úloze se počítá spíše s "cenou" a ta nemusí nutně odpovídat poloze. (Ani ta vzdálenost - dva body relativně blízko sebe mohou být spojeny "objížďkou", například kvůli překážce.)