Komiks xkcd 399: Problém obchodního cestujícího

17. 6. 2010 | Redakce

Články - Komiks xkcd 399: Problém obchodního cestujícího  

XKCD česky.

Problém obchodního cestujícího

← xkcd 233: Nová generace captcha | originál: http://xkcd.com/399/

Překlady xkcd vycházejí se svolením původního autora. © Randall Munroe.
Překlad: Tomáš Znamenáček, písmo: Martin Stiborský

Uvedená práce (dílo) podléhá licenci Creative Commons Uveďte autora-Neužívejte dílo komerčně 2.5

Seriál XKCD česky (dílů: 338)

První díl: Komiks xkcd 648: Podzimní listí, poslední díl: Komiks xkcd 1112: Vem si to logicky.
Předchozí díl: Komiks xkcd 233: Nová generace captcha
Následující díl: Komiks xkcd 276: Pevná šířka

Diskuse k tomuto článku

[mmmmario]

Tak tenhle mě dostal. Mazec!

[mmmmario]

http://xkcd.com/589/

[Amarok]

Jo, tenhle je daleko lepsi a jeden z mych nejoblibenejsich :D

[ntw]

A toto se líbí mně: http://geekz.co.uk/lovesraymond/archive/hacking-for-christ

[Amarok]

Tak ten bohuzel nechapu, co je "repetitive strain injury" a v jake je to souvislosti?

[Marek Bernát]

To je doslovne "zranenie z opakovanej/dlhodobej námahy". Karpálne tunely a spol. sú známa firma Ale ten komiks teda nechápem ani ja. Buď to, alebo nie je vtipný

[Martin Doucha]

RMS je autor Emacsu. Už je pointa vtipu jasná?

[Marek Bernát]

Ak to má byť pointa, tak si nie som úplne istý, či to nazvať vtip

[Amarok]

Emacs me v te souvislosti nenapadl. Ale zacinam uz chapat - RMS neni schopen uz pracovat, jelikoz tak casto mackal ty silene klavesove zkratky? A proc ten chlapek ma na tricku logo Firefox, to s tim nejak souvisi?

[Robo]

[Martin Doucha]

Dynamické algoritmy a lineární algoritmy? *facepalm* Dynamické programování a lineární programování jsou optimalizační disciplíny a ne nějaký algoritmus.

[MX]

obrázek

next_ghost se naucil nove slovo 3-/

---

Vložený obrázek jsem změnil na odkaz. Filip Jirsák

[zoul]

A nemůže být „dynamický algoritmus“ jako „algoritmus dynamického programování“? Přijde mi to podobná situace jako u genetických algoritmů. (U lineárních algoritmů by mohlo dojít k záměně s lineární složitostí, ale v tomhle kontextu asi stěží.)

[zoul]

Lineární algoritmy jsme nakonec změnili, díky za postřeh. Dynamické bych s klidem nechal.

[Martin Doucha]

Google zrovna moc dobrý argument nedává, každý z těch prvních tří odkazů dává úplně jinou definici pojmu "dynamický algoritmus" - první link ho definuje podle předvídatelnosti chování algoritmu, druhý ho definuje jako algoritmus využívající dynamické programování a třetí jako množinu výpočtů nad určitou datovou strukturou, do které se průběžně vkládají a mažou data a pokládají se dotazy.

[Ondrej 'SanTiago' Zajicek]

Dynamicke programovani je dneska brano spis jako metodika navrhu algoritmu, vyslednym algoritmum muzeme klidne rikat dynamicke algoritmy.

[holdenSK]

Nemalo by byt v 2. paneli skor "Algoritmy dynamickeho programovania" ? Aspon tak chapem ja ten originalny...

[corwin78]

Safra, síťové grafy. Že já zrovna včera dělal ty státnice

[m.florian]

nechápu! mohli by jste mě to pls. někdo vysvětlit (polopaticky)?

[pacholik]

http://cs.wikipedia.org/wiki/Problém_obchodního_cestujícího

[zoul]

Problém obchodního cestujícího je jeden z klasických příkladů z informatiky. Jde o to, že kdybys jako obchodní cestující chtěl navštívit řekněme dvacet měst, chtěl bys je navštívit v pořadí, které znamená nejmíň cestování. Když tenhle problém začneš řešit algoritmicky, rychle dojdeš k tomu, že nalézt skutečně optimální řešení znamená vyzkoušet všechny možnosti. A těch je fůra, konkrétně n! kde n je počet měst. (A n! je faktoriál n, čili počet všech možných uspořádání množiny o n prvcích.)

Existují algoritmy, které mají časovou složitost lepší než onen faktoriál, viz třeba dynamické programování. Pořád je to ale komplikované. Naproti tomu střelit něco na eBay je hračka a nemusíš nikam jezdit, čímž se dostáváme k pointě dnešního stripu :) Ovšem ani prodej na eBay není tak úplně bezpečný…

[m.florian]

diky, už to chápu :D

[belisarivs]

Ovšem ani prodej na eBay není tak úplně bezpečný…

Nebo vyhodny.

[holdenSK]

No, z hladiska TSP ide len o vyhodnost cesty, v com je eBay jasne najlepsi

[tmr]

Tohle je typ vtipu, u kteryho si rikam ze to je vtipny, ale nesmeju se. Proste xkcd asi neni pro me...

[James_ros]

tak tento me pobavil, nejen proto, ze jsem z dynamickeho programovani delal nedavno statnice

Taky bych to prelozil spis dynamicke programovani, protoze tam nejde ani tak o algoritmus ale o aproximaci, tim se hleda optimalni pruchod siti

ale jinak dobra prace :)

[zoul]

No ale abys mohl analyzovat časovou složitost, musíš mít konkrétní algoritmus, ne?

[Ash]

Ale ta složitost v komixu je složitost těch dynamických algoritmů, nikoliv složitost té tvé "aproximace" ;)