Diskuze: Napis algorytmus a cestuj okolo sveta

shaman

Člen

shaman:22.2.2017 14:58

Ista ceska firma vyhlasila sutaz o cestu okolo sveta. Staci len napisat jednoduchy algoritmus ktory vypocita najlacnejsiu multicity trasu.

Viac info na stranke sutaze: https://travellingsalesman.cz/

Odpovědět

22.2.2017 14:58

try {...} catch (Exception ignored) { echo " ¯\_(ツ)_/¯ "; }

shaman

Člen

shaman:22.2.2017 15:00

Nadpis sa uz neda editovat, pravopisnych trolov vopred pozdravujem.

Nahoru Odpovědět

22.2.2017 15:00

try {...} catch (Exception ignored) { echo " ¯\_(ツ)_/¯ "; }

Matúš Petrofčík

Tvůrce

Matúš Petrofčík:22.2.2017 15:06

Oni už majú takú súťaž už minimálne pol roka. Aj na PyCon 2016 v Brne som videl tie ich letáky.

Ale tak nie zle

Nahoru Odpovědět

22.2.2017 15:06

obsah kocky = r^2 ... a preto vlak drnká

shaman

Člen

shaman:23.2.2017 14:54

To som nevedel. Viem ze pracuju s pythonom lebo zhanaju furt python developerov ale sutaz celkom zaujimava.

Nahoru Odpovědět

23.2.2017 14:54

try {...} catch (Exception ignored) { echo " ¯\_(ツ)_/¯ "; }

Matúš Petrofčík

Tvůrce

Matúš Petrofčík:23.2.2017 15:58

Myslím že to bola súťaž, už si nepamätám presne, a ani neviem či im tam vôbec niekto prispel. Také papiere boli kde bolo veľmi podobné zadanie, a na druhej strane prázdne miesto kde sa to dalo riešiť, prípadne mail a ich web tam bol tuším.

Nahoru Odpovědět

23.2.2017 15:58

obsah kocky = r^2 ... a preto vlak drnká

Martin Dráb

Tvůrce

Martin Dráb:23.2.2017 21:59

Staci len napisat jednoduchy algoritmus ktory vypocita najlacnejsiu multicity trasu.

Jestli to dobře chápu, tak se jedná o problém obchodního cestujícího, i když asi zjednodušený tím, že platí trojúhelníková nerovnost. Pokud se ale chceme dostat k optimu, tak to je prostě NP-hard, takže se moc nedá čekat, že by "jednoduchý algoritmus" pomohl. Heuristiky existují (a pokud vím, dost dobré), ale o nich oni určitě vědí.

Nahoru Odpovědět

23.2.2017 21:59

2 + 2 = 5 for extremely large values of 2

coells

Tvůrce

coells:24.2.2017 17:10

Ano, zmínka o jednoduchém algoritmu mě také pobavila :-)

Máš pravdu, že je to hledání Hamiltonovské kružnice, ale zadání je složitější než původní TS.
Kvůli časové souslednosti máš K množin o N vrcholech, které vzájemně tvoří bipartitní dvojice.
Takže místo o(N²) hran jich máš O(K*N²) s omezujícími podmínkami a neplatí trojúhelníková nerovnost.

Pro zajímavost, u NP úloh v soutěžích, co jsem viděl, vždy vyhrály s obrovským náskokem genetické algoritmy.

Nahoru Odpovědět

24.2.2017 17:10

shaman

Člen

shaman:28.2.2017 9:49

Rad som pobavil. Co su geneticke algoritmy? Mas nejaky link?

Nahoru Odpovědět

28.2.2017 9:49

try {...} catch (Exception ignored) { echo " ¯\_(ツ)_/¯ "; }

Petr Nymsa

Tvůrce

Petr Nymsa:28.2.2017 13:33

Jak se vůbec dají hodnotit algoritmy na NP-hard úlohách? Pdole jakých kriterií? Čistě rychlost nebo něco i jiného?

Nahoru Odpovědět

28.2.2017 13:33

Pokrok nezastavíš, neusni a jdi s ním vpřed

coells

Tvůrce

coells:28.2.2017 14:05

V podstatě je můžeš hodnotit, jak chceš.
Soutěžní úlohy bývají doplněné o ohodnocovací funkci, kterou musíš optimalizovat.
Například Hamiltonovská cesta je rozhodovací úloha v NP-hard, ale délka nejdelší nalezené cesty na ohodnoceném grafu je typická optimalizační úloha a není o nic jednodušší.
Čas nemá smysl řešit, obvykle se uměle omezí čas i pamět na nějaký limit.

shaman stačí googlit, najdeš toho tuny

Nahoru Odpovědět

28.2.2017 14:05

dez1nd

Člen

dez1nd:19.9.2017 6:37

a já chtěl napsat "Algoritmus"

Nahoru Odpovědět

19.9.2017 6:37

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 11 zpráv z 11.