Ako používať maďarský algoritmus?
Aký je algoritmus na pokrytie nulových prvkov minimálnym počtom riadkov?
Maďarský algoritmus umožňuje nájsť „minimálnu zhodu“. Toto je možné použiť v prípadoch, keď pre skupinu aktivít existuje viacero úvodzoviek a každú aktivitu musí vykonať iná osoba, aby sa zistili minimálne náklady na dokončenie všetkých činností.
- 1Zoraďte svoje informácie do matice s „ľuďmi“ vľavo a „aktivitou“ hore, s „nákladmi“ pre každý pár v strede.
- 2V prípade potreby zaistite, aby bola matica štvorcová, a to tak, že pridáte fiktívne riadky/stĺpce. Obvykle je každý prvok v fiktívnom riadku/stĺpci rovnaký ako najväčšie číslo v matici.
- 3Zmenšite riadky odčítaním minimálnej hodnoty každého riadka z tohto riadka.
- 4Ak existujú stĺpce bez nuly, zmenšite stĺpce odčítaním minimálnej hodnoty každého stĺpca od tohto stĺpca.
- 5Pokryte nulové prvky minimálnym počtom riadkov, ktorými je možné ich pokryť. (Ak je počet riadkov rovný počtu riadkov, pokračujte krokom 9)
Algoritmus Floyd-Warshall môžete použiť na výpočet najkratšej cesty z akéhokoľvek uzla do akéhokoľvek uzla. - 6Pridajte minimálny nekrytý prvok ku každému zakrytému prvku. Ak je prvok zakrytý dvakrát, pridajte k nemu minimálny prvok dvakrát.
- 7Od každého prvku v matici odpočítajte minimálny prvok.
- 8Znovu zakryte nulové prvky. Ak sa počet riadkov pokrývajúcich nulové prvky nerovná počtu riadkov, vráťte sa na krok 6.
- 9Vyberte zhodu výberom sady núl, aby bol v každom riadku alebo stĺpci vybratý iba jeden.
- 10Aplikujte zhodu na pôvodnú maticu, bez ohľadu na fiktívne riadky. Toto ukazuje, kto by mal vykonávať akú činnosť, a pripočítaním nákladov sa dosiahnu celkové minimálne náklady.
- Ak chcete nájsť skôr maximálnu než minimálnu zhodu, v kroku 1 každé číslo vynásobte -1 a potom postupujte podľa uvedených pokynov.
- Kľúčovým poznatkom je, že pridaním rovnakého čísla ku všetkým položkám v jednom riadku alebo stĺpci matice vznikne nová matica s rovnakým optimálnym riešením. To je to, čo nám umožňuje uniknúť redukcii matice v kroku 6.
- Papier
- Pero/ceruzka
Prečítajte si tiež: Ako počítať v binárnom čísle?
Otázky a odpovede
- Ako sa líšia algoritmy Dijkstra a Floyd?Algoritmus Dijkstra môžete použiť na výpočet najkratšej cesty zo zdrojového uzla do akéhokoľvek iného uzla. Algoritmus Floyd-Warshall môžete použiť na výpočet najkratšej cesty z akéhokoľvek uzla do akéhokoľvek uzla. Nepoužívajte Dijkstra, ak existujú oblúky so zápornou hmotnosťou. Ak je v grafe negatívny cyklus, nemôžete použiť polynómový algoritmus.
- Je možné vykonať redukciu stĺpcov ako prvú a zníženie radu ako druhé?Nie, pretože hodnoty sa dramaticky menia, čím sa mení rovnica a riešenie.
- Ako sa používa maďarská metóda na získanie riešenia, ak je maticou obdĺžnik?Najprv by ste pridali „atrapy“ riadkov alebo stĺpcov, aby boli štvorcové, pričom hodnota „dummy“ je najvyššia hodnota z tohto stĺpca alebo riadka.
Nezodpovedané otázky
- Čo mám robiť, ak niektoré zdroje pri použití maďarského algoritmu nemajú žiadnu hodnotu pre konkrétne miesto určenia?
- Aký je algoritmus na pokrytie nulových prvkov minimálnym počtom riadkov?
