Valentínska akcia je tu! Získaj až 80 % extra kreditov ZADARMO na náš interaktívny e-learning. ZISTIŤ VIAC:
NOVINKA: Najžiadanejšie rekvalifikačné kurzy teraz s 50% zľavou + kurz AI ZADARMO. Nečakaj, táto ponuka dlho nevydrží! Zisti viac:
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

 
Odpovedať
10.12.2013 21:53
Avatar
Kit
Tvůrce
Avatar
Odpovedá 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.

Hore Odpovedať
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
Odpovedá na dominik077
Petr Nymsa:10.12.2013 21:58

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

Hore Odpovedať
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?

 
Hore Odpovedať
10.12.2013 22:01
Avatar
Petr Nymsa
Tvůrce
Avatar
Odpovedá 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 ?

Hore Odpovedať
10.12.2013 22:02
Pokrok nezastavíš, neusni a jdi s ním vpřed
Avatar
Kit
Tvůrce
Avatar
Odpovedá 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.

Hore Odpovedať
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

 
Hore Odpovedať
10.12.2013 22:05
Avatar
Petr Nymsa
Tvůrce
Avatar
Odpovedá 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

Hore Odpovedať
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 :-(

 
Hore Odpovedať
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:-)

 
Hore Odpovedať
10.12.2013 22:09
Avatar
Kit
Tvůrce
Avatar
Odpovedá 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í.

Hore Odpovedať
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
Odpovedá 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š.

 
Hore Odpovedať
10.12.2013 22:18
Avatar
coells
Tvůrce
Avatar
Odpovedá 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.

 
Hore Odpovedať
10.12.2013 22:31
Avatar
Neaktivní uživatel
Tvůrce
Avatar
Odpovedá na coells
Neaktivní uživatel:10.12.2013 22:36

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

Hore Odpovedať
10.12.2013 22:36
Neaktivní uživatelský účet
Avatar
coells
Tvůrce
Avatar
Odpovedá 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 :-)

 
Hore Odpovedať
10.12.2013 22:39
Avatar
dominik077
Člen
Avatar
Odpovedá na coells
dominik077:10.12.2013 22:44

je to vejska 2 semestr Algoritmy 2

 
Hore Odpovedať
10.12.2013 22:44
Avatar
coells
Tvůrce
Avatar
Odpovedá na dominik077
coells:10.12.2013 23:15

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

 
Hore Odpovedať
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

 
Hore Odpovedať
10.12.2013 23:26
Avatar
coells
Tvůrce
Avatar
Odpovedá 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.

 
Hore Odpovedať
10.12.2013 23:33
Robíme čo je v našich silách, aby bola tunajšia diskusia čo najkvalitnejšia. Preto do nej tiež môžu prispievať len registrovaní členovia. Pre zapojenie sa do diskusie sa zaloguj. Ak ešte nemáš účet, zaregistruj sa, je to zadarmo.

Zobrazené 19 správy z 19.