Zadání :
Na zaciatku vytvoríme cyklus z jednoho lub. bodu.
V jednotlivých krokoch postupne hladáme vrchol u, ktorý
nie je v cykle a je najbližšie k cyklu, k nejakému vrcholu
v. Rozšírime cyklus pridaním u za v a opakujeme, kým
v cykle nie sú všetky vrcholy. Ukážte, že táto heuristika
vracia cyklus, ktorý je najviac dvaktát dlhší než optimálna
cesta (pri platnosti trojuholnikovej nerovnosti).
Pomoc s příkladem - Obchodní cestující
- Ellrohir
- Matfyz(ák|ačka) level III
- Příspěvky: 140
- Registrován: 21. 12. 2007 13:29
- Typ studia: Informatika Bc.
- Login do SIS: secka7am
- Bydliště: Praha
- Kontaktovat uživatele:
Pomoc s příkladem - Obchodní cestující
Naposledy upravil(a) Ellrohir dne 1. 3. 2009 18:13, celkem upraveno 2 x.
- Ellrohir
- Matfyz(ák|ačka) level III
- Příspěvky: 140
- Registrován: 21. 12. 2007 13:29
- Typ studia: Informatika Bc.
- Login do SIS: secka7am
- Bydliště: Praha
- Kontaktovat uživatele:
Re: Pomoc s příkladem - Heuristika najbližšieho bodu
tak mi bylo porazeno, že důkaz má co dělat s důkazem správnosti Algoritmu obchodního cestujícího...což dává rozhodně větší smysl než ten můj "původní" návrh (který nezohlednil, že půjde o graf s ohodnocenými hranami)
nicméně ani to mi zatím moc nepomohlo, protože Mareš ve svých skriptech má ten agloritmus popsaný podle mého jinak než vypadá tahle Hricova heuristika (aspoň mi to tak přijde - "udělat minimální kostru, tu obejít sledem a pak ten sled postupně "předělávat" až to bude cyklus" se mi nezdá shodný s tímhle "udělat cylkus 3 vrcholů a přidávat další" ), takže z toho pořád nejsem moudrej fakt nikdo tohle neví? prej jsme to "určitě dělali na přednášce"...
nicméně ani to mi zatím moc nepomohlo, protože Mareš ve svých skriptech má ten agloritmus popsaný podle mého jinak než vypadá tahle Hricova heuristika (aspoň mi to tak přijde - "udělat minimální kostru, tu obejít sledem a pak ten sled postupně "předělávat" až to bude cyklus" se mi nezdá shodný s tímhle "udělat cylkus 3 vrcholů a přidávat další" ), takže z toho pořád nejsem moudrej fakt nikdo tohle neví? prej jsme to "určitě dělali na přednášce"...
-
- Supermatfyz(ák|ačka)
- Příspěvky: 403
- Registrován: 11. 11. 2006 14:10
- Typ studia: Informatika Mgr.
- Bydliště: Praha
- Kontaktovat uživatele:
Re: Pomoc s příkladem - Heuristika najbližšieho bodu
Nedala by se využít nějak myšlenka ze stavění MINIMÁLNÍ kostry? Pokud stavíš minimální kostru, tak to můžeš udělat tak, že začneš s pseudokostrou, která obsahuje jeden vrchol a přidáváš ty hrany, které jsou nejmenší, až posléze dostaneš kostru (spotřebuješ všechny vrcholy). Tohle je stejné, akorát s cyklem, mělo by to jít nějak modifikovat, nebo ne?Ellrohir píše:...
Osiris
- Ellrohir
- Matfyz(ák|ačka) level III
- Příspěvky: 140
- Registrován: 21. 12. 2007 13:29
- Typ studia: Informatika Bc.
- Login do SIS: secka7am
- Bydliště: Praha
- Kontaktovat uživatele:
Re: Pomoc s příkladem - Obchodní cestující
no kdybych věděl, jak to udělat, tak se tu neptám...
když podle tý heuristiky přidávám vrchol do už existujícího cyklu, tak se délka cyklu zmenší o délku jedné hrany a prodlouží o délku 2 nově vzniklých hran...ale o těch vzniklejch hranách neumím podle mého říct nic než to, že budou dohromady delší, než ta zmizelá, což mi ale není celkem k ničemu...no a ještě taky vím, že délka jedné z těch dvou hran je nejmenší možná - přidávám vrchol "nejblíže k cyklu"...ale co z toho? furt mi nic v hlavě nesecvakává...
když podle tý heuristiky přidávám vrchol do už existujícího cyklu, tak se délka cyklu zmenší o délku jedné hrany a prodlouží o délku 2 nově vzniklých hran...ale o těch vzniklejch hranách neumím podle mého říct nic než to, že budou dohromady delší, než ta zmizelá, což mi ale není celkem k ničemu...no a ještě taky vím, že délka jedné z těch dvou hran je nejmenší možná - přidávám vrchol "nejblíže k cyklu"...ale co z toho? furt mi nic v hlavě nesecvakává...
- hippies
- Admin(ka) level I
- Příspěvky: 990
- Registrován: 29. 9. 2004 12:46
- Typ studia: Informatika Mgr.
- Login do SIS: procj4am
- Bydliště: Mladá Boleslav
- Kontaktovat uživatele:
Re: Pomoc s příkladem - Obchodní cestující
,,Nejblize k cyklu" - nejblize k vrcholu v cyklu = hledani minimalni kostry. Pokud to nebude k vrcholum, ale budes uvazovat i hrany, tak si muzes jen polepsit (vrchol je konec hrany) .. jeste musis ukazat, ze si muzes jen polepsit, nad tim se mi nechce ted dumat.
Chjo, dovede te si představit svět, kde by byla každá harmonická diferenciální forma (jistého typu) nesingulární projektivní algebraické variety racionální kombinací kohomologických tříd algebraických cyklů..
- Ellrohir
- Matfyz(ák|ačka) level III
- Příspěvky: 140
- Registrován: 21. 12. 2007 13:29
- Typ studia: Informatika Bc.
- Login do SIS: secka7am
- Bydliště: Praha
- Kontaktovat uživatele:
Re: Pomoc s příkladem - Obchodní cestující
možná planej poplach, ale myslím, že se myšlenka objevila a už to dohromady dám každopádně díky za "nakopnutí"