Hric - Příklad na zápočet - potřebuju poradit...

Pokračování přednášky TIN060 Algoritmy a datové struktury I
Pitr2311
Matfyz(ák|ačka) level II
Příspěvky: 53
Registrován: 3. 9. 2009 17:54
Typ studia: Informatika Mgr.

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od Pitr2311 »

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.. :wink:
Pitr2311
banejee

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od banejee »

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?
Pitr2311
Matfyz(ák|ačka) level II
Příspěvky: 53
Registrován: 3. 9. 2009 17:54
Typ studia: Informatika Mgr.

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od Pitr2311 »

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?
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...
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.. :D
Pitr2311
banejee

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od banejee »

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..
Pitr2311
Matfyz(ák|ačka) level II
Příspěvky: 53
Registrován: 3. 9. 2009 17:54
Typ studia: Informatika Mgr.

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od Pitr2311 »

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.
banejee 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)
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 mame
Pitr2311
banejee

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od banejee »

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
Pitr2311
Matfyz(ák|ačka) level II
Příspěvky: 53
Registrován: 3. 9. 2009 17:54
Typ studia: Informatika Mgr.

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od Pitr2311 »

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.. :wink:
Pitr2311
Seldon

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od Seldon »

Asi jsem natvrdlej, ale nemohli by jste mi rict, jak se ukazuje, ze tato kruznice bude max 2x delsi nez optimalni cesta? Díky
Uživatelský avatar
Ellrohir
Matfyz(ák|ačka) level III
Příspěvky: 140
Registrován: 21. 12. 2007 13:29
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: Hric - Příklad na zápočet - potřebuju poradit...

Příspěvek od Ellrohir »

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
Odpovědět

Zpět na „TIN061 Algoritmy a datové struktury II“