Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 02. 12. 2013 01:21
Nezávislé nuly? Maďarská metoda
Zdravím,
potřeboval bych pro blbce vysvětlit jak najít nezávislé nuly při maďarské metodě
Matice
Jak postupovat? Asi jsem dement, ale z
"V matici vyhledáme řadu, tj. řádek nebo sloupec ( resp. jednu z řad ), s nejmenším počtem nul a jednu z nul této řady dáme do rámečku. Ostatní nuly nacházející se v tomtéž řádku nebo sloupci jako nula v rámečku ( nezávislá nula ) přeškrtneme. Ze zbývajících řad opět vybereme řadu obsahující nejmenší počet nul a celý postup opakujeme. Takto postupujeme, dokud je možné dávat nuly do rámečku ( vybírat nezávislé nuly )."
to fakt nechápu...
Začal bych řádkem - tzn nuly na pozici S2 P3 a S5 P4
Pak sloupce - S4 P2
Vyškrtal bych vždy 0 v řádku i sloupci, bakonec mi zbyla 0 v S1 P1 = nezávislá
Potém v řádku/sloupci kde nejsou nezávislé nuly vedu krycí čáry - mám 3
ŠPATNE
Moje řešení a pod tím je správné
KDE DELAM CHYBU? Prosím jak pro blbce.. děkuji
Život je jako matematika, nikdy nevíš co ti vyjde.
Offline
#2 02. 12. 2013 12:34
- vojta_vorel
- Příspěvky: 70
- Škola: MFF UK
- Pozice: student
- Reputace: 5
Re: Nezávislé nuly? Maďarská metoda
Ahoj
Sice jsem nikdy o Maďarské metodě neslyšel, ale aspoň poznamenám, že ta část postupu, kterou jsi citoval v uvozovkách, může dávat různé správné výsledky. Jde v ní o to, najít v té matici co nejvíc nezávislých nul (takových, aby se žádné z nich netísnily ve společném sloupci ani řádku). V tomhle případě tam jdou najít maximálně čtyři, a takových čtveřic je několik, všechny jsou správně.
Takže je dost možné, že i celý ten postup včetně těch krycích čar může mít víc správných výsledků. Každopádně si pořádně zjisti, jak se ty čáry dělají, koukal jsem letmo na http://en.wikipedia.org/wiki/Hungarian_algorithm a přijde mi tvé určování krycích čar nějak podezřele jednoduché.
Vojta
Offline