Nové výhodné předplatné namísto kreditů je tu! Více informací. Upravili jsme také naše provozní podmínky.
NOVINKA: Staň se datovým analytikem a získej jistotu práce, lepší plat a nové kariérní možnosti. Více informací:

Diskuze: Uloha obchodního cestujíciho

Aktivity
Avatar
dominik077
Člen
Avatar
dominik077:10.12.2013 21:53

Mohl by mi prosím vysvětlit řešení teto ulohy nejak aby se to dalo pochopit i pro matematickou lamu..... Stačí 5 měst uplně... nebo nějaký odkaz kde to pochopí i lama..
Díky

 
Odpovědět
10.12.2013 21:53
Avatar
Kit
Tvůrce
Avatar
Odpovídá na dominik077
Kit:10.12.2013 21:56

Je to NP-úplná úloha, která se dá řešit jen intuicí nebo hrubou silou. Možná by to zvládl nějaký kvantový počítač, ale těch je zatím málo.

Nahoru Odpovědět
10.12.2013 21:56
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Petr Nymsa
Tvůrce
Avatar
Odpovídá na dominik077
Petr Nymsa:10.12.2013 21:58

Tak toto by ani Einstein nevyřešil. Co takto tu úlohu nám říct ? :`

Nahoru Odpovědět
10.12.2013 21:58
Pokrok nezastavíš, neusni a jdi s ním vpřed
Avatar
dominik077
Člen
Avatar
dominik077:10.12.2013 22:01

Ja vim,ale bude se mě na to u zkoušky ptat a nic nám o tom neřekl ani ve školním systemu nic neni...Tak co byste mi poradili abych tam řekl prosim?

 
Nahoru Odpovědět
10.12.2013 22:01
Avatar
Petr Nymsa
Tvůrce
Avatar
Odpovídá na dominik077
Petr Nymsa:10.12.2013 22:02

Jako asi nejsem jediný který nechápe absolutně na co se ptáš ? :D Jak to souvisí s matematikou ? Jakých 5 měst ?

Nahoru Odpovědět
10.12.2013 22:02
Pokrok nezastavíš, neusni a jdi s ním vpřed
Avatar
Kit
Tvůrce
Avatar
Odpovídá na dominik077
Kit:10.12.2013 22:03

Uděláš všechny možné permutace měst a spočítáš vzdálenosti mezi nimi. Z výsledků vybereš ten, který bude mít minimální součet.

Nahoru Odpovědět
10.12.2013 22:03
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
dominik077
Člen
Avatar
dominik077:10.12.2013 22:05

Problém obchodního cestujícího je obtížný diskrétní optimalizační problém, matematicky vyjadřující a zobecňující úlohu nalezení nejkratší možné cesty procházející všemi zadanými body na mapě. My máme 5 měst a popsat mu co s tim jakým zpusobem tu optimální trasu najít

 
Nahoru Odpovědět
10.12.2013 22:05
Avatar
Petr Nymsa
Tvůrce
Avatar
Odpovídá na dominik077
Petr Nymsa:10.12.2013 22:08

Aha :) tak to je moje neznalost že něco takovéhle existuje :) bohužel neporadím

Nahoru Odpovědět
10.12.2013 22:08
Pokrok nezastavíš, neusni a jdi s ním vpřed
Avatar
dominik077
Člen
Avatar
dominik077:10.12.2013 22:08

TO KIT .Jo ja vím,ale to je právě to co je špatně...protože nejaké faktory a podobné blablbla čím nás krmí,ale nic nevysvetli pořádně... Tahle uoha neni moc na logiku tady se hraje na nejaký algoritmus a Hamiltona :-(

 
Nahoru Odpovědět
10.12.2013 22:08
Avatar
dominik077
Člen
Avatar
dominik077:10.12.2013 22:09

To Zirko.O nic nepřicházíš ,je to strašná haluz:-)

 
Nahoru Odpovědět
10.12.2013 22:09
Avatar
Kit
Tvůrce
Avatar
Odpovídá na Petr Nymsa
Kit:10.12.2013 22:16

Podobný je i Problém batohu. Jsou to úlohy, které na které člověk dokáže najít přijatelné řešení za přijatelnou dobu, ale počítač si na nich vyláme zuby. Už 20 měst se standardním postupem nedá na počítači vyřešit a proto se hledají přijatelná, i když ne zcela správná řešení.

Nahoru Odpovědět
10.12.2013 22:16
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Vojtěch Pospíchal
Tvůrce
Avatar
Odpovídá na dominik077
Vojtěch Pospíchal:10.12.2013 22:18

Místo TO jméno používej prosím tlačítko odpověděd pod příspěvkem na který reaguješ.

 
Nahoru Odpovědět
10.12.2013 22:18
Avatar
coells
Tvůrce
Avatar
Odpovídá na dominik077
coells:10.12.2013 22:31

No ono by to taky chtělo říct, co přesně vám o tom říkal:

  1. co studuješ za školu, střední nebo výšku?
  2. zajímá tě převoditelnost na jiné NP-úplné úlohy?
  3. musíš vysvětlit základní algoritmus nebo heuristický?
  4. je to zkouška z Diskrétní matematiky nebo Složitosti a NP?

Hamiltonovská cesta v grafu je taková cesta, která prochází každým vrcholem grafu právě jednou. Hamiltonovský cyklus je Hamiltonovská cesta, která začíná a končí ve stejném vrcholu.

Algoritmus pro nalezení optimálního řešení obchodního cestujícího musí ve váženém grafu najít Hamiltonovský cyklus s co nejnižším ohodnocením. Neznáme žádný deterministický algoritmus, který by úlohu řešil rychleji než v O(2N), ale existuje polynomiální nedeterministický algoritmus řešící úlohu - úloha je tedy NP.

Také ji lze převést na další NP-úplné úlohy použitím polynomiálního deterministického algoritmu, takže problém obchodního cestujícího je NP-úplný.

Na internetu najdeš tunu materiálů k problému.

 
Nahoru Odpovědět
10.12.2013 22:31
Avatar
Neaktivní uživatel
Tvůrce
Avatar
Odpovídá na coells
Neaktivní uživatel:10.12.2013 22:36

NP asi není no-problemo, což :D?

Nahoru Odpovědět
10.12.2013 22:36
Neaktivní uživatelský účet
Avatar
coells
Tvůrce
Avatar
Odpovídá na Neaktivní uživatel
coells:10.12.2013 22:39

NP = nondeterministic polynomial time

No problemo si můžeš říkat před zkouškou ze složitosti, protože zrovna NP-complete problems jsou složité jako sviňa :-)

 
Nahoru Odpovědět
10.12.2013 22:39
Avatar
dominik077
Člen
Avatar
Odpovídá na coells
dominik077:10.12.2013 22:44

je to vejska 2 semestr Algoritmy 2

 
Nahoru Odpovědět
10.12.2013 22:44
Avatar
coells
Tvůrce
Avatar
Odpovídá na dominik077
coells:10.12.2013 23:15

No tak to si toho z přednášek pamatuješ opravdu hodně...

 
Nahoru Odpovědět
10.12.2013 23:15
Avatar
dominik077
Člen
Avatar
dominik077:10.12.2013 23:26

je to distancni studium...takze vicemene samostudium...tech par prednasek co mame 3x za semestr je spis takovy chaos co vse kde vse jak dokdy a tak

 
Nahoru Odpovědět
10.12.2013 23:26
Avatar
coells
Tvůrce
Avatar
Odpovídá na dominik077
coells:10.12.2013 23:33

No jo, jenže já nevím, co po tobě chtějí. Po nás chtěli převoditelnost NPC problémů KACHL->SAT->k-klika->HK. To, že obchodní cestující je HK (hamiltonovský cyklus), jsem ti ukázal už v předchozím příspěvku.

Na začátku píšeš o vysvětlení pro matematickou lamu - tohle je jenom matematika a bez ní to nejde.

 
Nahoru Odpovědět
10.12.2013 23:33
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 19 zpráv z 19.