navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m33pal:zkouska2014_5 [2014/01/30 21:13] sioca |
courses:a4m33pal:zkouska2014_5 [2025/01/03 18:29] (aktuální) |
||
|---|---|---|---|
| Řádek 16: | Řádek 16: | ||
| Pro každou augmentaci: | Pro každou augmentaci: | ||
| - | * vyberu nejdražší hranu mimo kostru | + | * vyberu nejdražší hranu mimo kostru |
| - | * označím jí k přidání do kostry | + | * označím jí k přidání do kostry |
| - | * spustím BFS z obou jejích koncových uzlů a ukládám si předchůdce každého uzlu | + | * spustím BFS z obou jejích koncových uzlů a ukládám si předchůdce každého uzlu |
| - | * jakmile narazím na uzel, ve kterém už jsem byl, našel jsem vytvořený cyklus | + | * jakmile narazím na uzel, ve kterém už jsem byl, našel jsem vytvořený cyklus |
| - | * procházím z nalezeného uzlu zpět k uzlům přidané hrany a aktualizuju si nejlevnější hranu cylku | + | * procházím z nalezeného uzlu zpět k uzlům přidané hrany a aktualizuju si nejlevnější hranu cylku |
| - | * nejlevnější hranu označím k odebrání z kostry | + | * nejlevnější hranu označím k odebrání z kostry |
| - | * počítám váhu takto vzniklé kostry a označím jako možné následující maximum | + | * počítám váhu takto vzniklé kostry a označím jako možné následující maximum |
| - | * spustím tento cylkus znovu pro druhou největší hranu mimo graf ... | + | * spustím tento cylkus znovu pro druhou největší hranu mimo graf ... |
| Cyklus končí, jakmile by váha možné přidané hrany už nemohla v součtu s aktuální váhou kostry-1 (musím nějakou hranu odebrat tak budu předpokládat, že tu nejlevnější) převýšit nebo alespoň vyrovnat momentálně uložené následující maximum. | Cyklus končí, jakmile by váha možné přidané hrany už nemohla v součtu s aktuální váhou kostry-1 (musím nějakou hranu odebrat tak budu předpokládat, že tu nejlevnější) převýšit nebo alespoň vyrovnat momentálně uložené následující maximum. | ||
| Řádek 31: | Řádek 31: | ||
| Opakujte až do D-té augmentace (minimální kostra se počítá jako první augmentace) | Opakujte až do D-té augmentace (minimální kostra se počítá jako první augmentace) | ||
| - | Zdroják a data (12/12 - o kousek rychlejší než referenční): | + | Zdroják a data (12/12 - o kousek rychlejší než referenční): {{:courses:a4m33pal:src.zip|}} |
