Názory k článku
Nové řešení problému obchodního cestujícího

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.

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..

Pokud chceš zkoušet různá vylepšení, tak je dobré si to taky kriticky zhodnotit - v tomto případě najít protipříklady a vady toho řešení. Napadají mě následující otázky:

• jak složité je určit velikost těch čtverců
• nenarušuje to řešení trojúhelníkovou nerovnost?
• proč by ta metrika měla urychlit prohledávání?
• lze rozhodnout zda trasa patří do řešení dle toho, že blízko ní leží jiné body?

Já bych na to šel opačně... Proč by to mělo fungovat a proč rychle? ;-)

> 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

No to vadí, pokud to původní zadání splňuje a existují pro takovou variantu rychlejší algoritmy.

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.

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.)