Hric - Příklad na zápočet - potřebuju poradit...
-
- Matfyz(ák|ačka) level II
- Příspěvky: 53
- Registrován: 3. 9. 2009 17:54
- Typ studia: Informatika Mgr.
- Login do SIS: 78761606
Re: Hric - Příklad na zápočet - potřebuju poradit...
ten problem so suctom podmnoziny sa da riesit metodou batohu, teda si vytvorime pole moznych suctov, teda cisel 1-K (K je hladany sucet), na zaciatok false (pripadne 0) a pre kazdy prvok mnoziny si pre kazde policko x, kde nie je false (0) pridame do policka x+prvok hodnotu true (pripadne prvok, ak potrebujeme dany sucet aj zreprodukovat).. v pripade, ze oznacime true aj sucet K, tak podmnozina s danym suctom existuje
toto funguje pre celociselne prvky, pre realne by som navrhoval ich najprv zaokruhlit, cim sa ale zmensi presnost vysledku...
a preco nie je polynomialny? nie som si uplne isty, ako to bolo myslene, ale tento algoritmus zavisi od K (linearne, pretoze pri kazdom prvku prejdeme celym polom velkosti K), tiez aj od velkosti mnoziny... povedal by som, ze aby to bolo polynomialne, malo by to zavisiet len od velkosti vstupnej mnoziny...
a s tym druhym problemom ti asi velmi nepomozem, lebo fakt netusim, ako sa to ma robit..
toto funguje pre celociselne prvky, pre realne by som navrhoval ich najprv zaokruhlit, cim sa ale zmensi presnost vysledku...
a preco nie je polynomialny? nie som si uplne isty, ako to bolo myslene, ale tento algoritmus zavisi od K (linearne, pretoze pri kazdom prvku prejdeme celym polom velkosti K), tiez aj od velkosti mnoziny... povedal by som, ze aby to bolo polynomialne, malo by to zavisiet len od velkosti vstupnej mnoziny...
a s tym druhym problemom ti asi velmi nepomozem, lebo fakt netusim, ako sa to ma robit..
Pitr2311
Re: Hric - Příklad na zápočet - potřebuju poradit...
dakujem, pomohlo
..v tej druhej ulohe sa jedna o problem obchodneho cestujuceho.. len nechapem ten postup co je v zadani..
Heuristika najbližšieho bodu
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).
Navrhnite zlepšenie k popísanej heuristike.
.. dame jeden bod do cyklu.. ale dalsie body len napajame.. ako to moze byt cyklus..
..museli by sme ho napojit so zaciatocnym aj koncovym bodom.. budeme body len napajat k jednemu koncovemu bodu a na konci nam zostane posledny bod.. nemoze sa stat, ze z neho nebude viest hrana k jednemu z koncovych bodov?
..v tej druhej ulohe sa jedna o problem obchodneho cestujuceho.. len nechapem ten postup co je v zadani..
Heuristika najbližšieho bodu
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).
Navrhnite zlepšenie k popísanej heuristike.
.. dame jeden bod do cyklu.. ale dalsie body len napajame.. ako to moze byt cyklus..
..museli by sme ho napojit so zaciatocnym aj koncovym bodom.. budeme body len napajat k jednemu koncovemu bodu a na konci nam zostane posledny bod.. nemoze sa stat, ze z neho nebude viest hrana k jednemu z koncovych bodov?
-
- Matfyz(ák|ačka) level II
- Příspěvky: 53
- Registrován: 3. 9. 2009 17:54
- Typ studia: Informatika Mgr.
- Login do SIS: 78761606
Re: Hric - Příklad na zápočet - potřebuju poradit...
Povedal by som, ze pri tomto probleme (alebo skor pri spominanom rieseni) sa berie akoby kompletny graf.. teda hrany, ktore v originalnom grafe nie su, nahradime akoby najkratsou cestou medzi danymi vrcholmi (po existujucich hranach) a v pripade, ze sa pri tom prechadza nejakymi inymi bodmi (mestami), tak ich pri tom prechode akoby "obideme", pripadne nimi cestujuci iba prejde bez zastavenia...banejee píše:.. dame jeden bod do cyklu.. ale dalsie body len napajame.. ako to moze byt cyklus..
..museli by sme ho napojit so zaciatocnym aj koncovym bodom.. budeme body len napajat k jednemu koncovemu bodu a na konci nam zostane posledny bod.. nemoze sa stat, ze z neho nebude viest hrana k jednemu z koncovych bodov?
teda pred samotnym spustenim toho popisaneho algoritmu by sa mal pustit Floyd-Warshallov alg. ktory medzi kazdymi dvoma vrcholmi "vytvori" hranu s dlzkou najkratsej cesty medzi danymi vrcholmi (v povodnom grafe)... tento graf potom splna trojuholnikovu nerovnost a moze sa nan spustit popisane riesenie..
Pitr2311
Re: Hric - Příklad na zápočet - potřebuju poradit...
hm.. mozno mi nieco uslo, premyslam nad tym.. ale ked si uz nahradime nehrany hranami... povedzme ze z v do u nevedie hrana a existuje cesta v -> z -> u (nech je najkratsia).. vytvorime hranu medzi v a u o velkosti (v,z) + (z,u) .. ked spustime algoritmus a sme vo vrchole v tak si hranu (v,u) aj tak nevyberieme (resp. vrchol u), lebo hrana (v,z) ma mensie ohodnotenie nez (v,u) a teda z je blizsie k v..
-
- Matfyz(ák|ačka) level II
- Příspěvky: 53
- Registrován: 3. 9. 2009 17:54
- Typ studia: Informatika Mgr.
- Login do SIS: 78761606
Re: Hric - Příklad na zápočet - potřebuju poradit...
banejee píše:Heuristika najbližšieho bodu
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.
predpokladajme, ze uz mame cyklus s vrcholmi z a u (napr. v1, v2, ... z, u, ... v1) a vrchol v je najblizsi (najblizsi vrchol z cyklu k vrcholu v je vrchol z), ktory v tom cykle este nie je... potom podla popisu alg. tento vrchol pridame za vrchol z, cim dostavame cyklus v1, v2, ... z, v, u, ... v1 - tu prave vyuzivame fakt, ze medzi vrcholmi v a u uz mame dodefinovanu hranu... v povodnom grafe by sme tam novy vrchol vlozit nemohli, pretoze by nemusel vzniknut cyklus... to uz ale teraz zarucene mamebanejee píše:povedzme ze z v do u nevedie hrana a existuje cesta v -> z -> u (nech je najkratsia).. vytvorime hranu medzi v a u o velkosti (v,z) + (z,u)
Pitr2311
Re: Hric - Příklad na zápočet - potřebuju poradit...
aha, uz mi je to jasne
len potom este 1 otazka.. ked uz mam cyklus v takomto grafe.. ako sa to prevedie na povodny graf : P
len potom este 1 otazka.. ked uz mam cyklus v takomto grafe.. ako sa to prevedie na povodny graf : P
-
- Matfyz(ák|ačka) level II
- Příspěvky: 53
- Registrován: 3. 9. 2009 17:54
- Typ studia: Informatika Mgr.
- Login do SIS: 78761606
Re: Hric - Příklad na zápočet - potřebuju poradit...
povedal by som, ze tam, kde si vytvaral nove hrany (ako najkratsiu cestu cez nejake ine body), tak tam v povodnom grafe pojdes cez tie body na najkratsej ceste... nebude to sice cyklus podla definicie z diskretky, ale pri obchodnom cestujucom to podla mna az tak nevadi... ved ak si to predstavime ako realny problem na nejakej mape miest, tak tam nemusi existovat hamiltonovska kruznica (prechadza vsetkymi vrcholmi).. staci si predstavit nejake "zapadakovo", kam sa da dostat jednou jedinou cestou, a tam by sa potom o.c. nemal sancu dostat..
Pitr2311
Re: Hric - Příklad na zápočet - potřebuju poradit...
Asi jsem natvrdlej, ale nemohli by jste mi rict, jak se ukazuje, ze tato kruznice bude max 2x delsi nez optimalni cesta? Díky
- 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: Hric - Příklad na zápočet - potřebuju poradit...
tohle si náhodou myslím, že vím (pokud ti to ještě k něčemu je)
při hledání cesty pro obch. cestujícího vycházíme z min. kostry délky T - na začátku cestující chodí po minimální kostře - každou hranu projde nejvýše 2x a přitom tak nachodí max. 2T...my v algoritmu délku jeho cesty upravujeme tím, že cestu mezi dvěma vrcholy, které jsou spojeny "přes třetí vrchol" nahrazujeme přímou hranou...a protože platí trojúhelníková nerovnost (předpoklad pro náš algoritmus), tak se délka, co musí cestující ujít, může určitě jedině zkracovat
omezení zdola délkou T se kdyžtak ukazuje tak, že máš-li libovolnou ham. kružnici C, tak z ní po odebrání jedné hrany dostaneš nějakou kostru...a každá nějaká kostra musí mít min. délku T (délku minimální kostry), což spolu s přidáním ještě jedné hrany, aby člověk dostal zpátky ham. kružnici, spolehlivě dává spodní mez
při hledání cesty pro obch. cestujícího vycházíme z min. kostry délky T - na začátku cestující chodí po minimální kostře - každou hranu projde nejvýše 2x a přitom tak nachodí max. 2T...my v algoritmu délku jeho cesty upravujeme tím, že cestu mezi dvěma vrcholy, které jsou spojeny "přes třetí vrchol" nahrazujeme přímou hranou...a protože platí trojúhelníková nerovnost (předpoklad pro náš algoritmus), tak se délka, co musí cestující ujít, může určitě jedině zkracovat
omezení zdola délkou T se kdyžtak ukazuje tak, že máš-li libovolnou ham. kružnici C, tak z ní po odebrání jedné hrany dostaneš nějakou kostru...a každá nějaká kostra musí mít min. délku T (délku minimální kostry), což spolu s přidáním ještě jedné hrany, aby člověk dostal zpátky ham. kružnici, spolehlivě dává spodní mez