Diskuze: Uloha obchodního cestujíciho

Volná diskuze Uloha obchodního cestujíciho

Avatar
dominik077
Člen
Avatar
dominik077:

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
Redaktor
Avatar
Odpovídá na dominik077
Kit:

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  +1 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
Redaktor
Avatar
Odpovídá na dominik077
Petr Nymsa:

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:

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
Redaktor
Avatar
Odpovídá na dominik077
Petr Nymsa:

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  +1 10.12.2013 22:02
Pokrok nezastavíš, neusni a jdi s ním vpřed
Avatar
Kit
Redaktor
Avatar
Odpovídá na dominik077
Kit:

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:

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
Redaktor
Avatar
Odpovídá na dominik077
Petr Nymsa:

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:

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:

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

 
Nahoru Odpovědět 10.12.2013 22:09
Avatar
Kit
Redaktor
Avatar
Odpovídá na Petr Nymsa
Kit:

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
Odpovídá na dominik077
Vojtěch Pospíchal:

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  -1 10.12.2013 22:18
Avatar
coells
Redaktor
Avatar
Odpovídá na dominik077
coells:

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
Jiří Gracík
Redaktor
Avatar
Odpovídá na coells
Jiří Gracík:

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

Nahoru Odpovědět 10.12.2013 22:36
Creating websites is awesome till you see the result in another browser ...
Avatar
coells
Redaktor
Avatar
Odpovídá na Jiří Gracík
coells:

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:

je to vejska 2 semestr Algoritmy 2

 
Nahoru Odpovědět 10.12.2013 22:44
Avatar
coells
Redaktor
Avatar
Odpovídá na dominik077
coells:

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:

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
Redaktor
Avatar
Odpovídá na dominik077
coells:

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.