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
Stránky: 1
Nemůžu nikde najít algoritmus pro nalezení nejlevnějšího maximálního párování v grafu. Máme za úkol naprogramovat Čínského pošťáka, kde se využívá párování, přičemž se má nalézt párování, jehož součet ohodnocených hran je nejmenší. Je někde popsaný ten algoritmus? Prošel jsem knížku od Demela, několik PDF a nikde jsem na přesný postup algoritmu nenarazil.
Offline
A nemas nahodou potuchu, jak se ten algoritmus jmenuje? Ja jsem se ted kdysi ucil algoritms na nalezeni maximalniho parovani, no, neni to zadna legrace....
Offline
↑ Lishaak:
Nevím :-(. Hledal jsem pod tím nejlevnější maximální párování. Algoritmus pro maximální párování mám naprogramovaný (pomocí střídavých cest), ale pro toho čínského pošťáka bych potřeboval párování, která má nejmenší součet ohodnocených hran. Tedy používám algoritmus, kdy si vytáhnu liché vrcholy z grafu G, udělám jen z nich úplný graf G', pak v původním grafu G najdu nejkratší cesty mezi těmito vrcholy a tuto délku pak dosadím jako ohodnocení hrany mezi dvěma vrcholy v grafu G'. A pak bych potřeboval najít maximální párování s nejmenším součtem ohodnocení v G' a tyto hrany musí pošťák v původním grafu G projít dvakrát. Všechno zvládám naprogramovat, ale nikde jsem nenašel algoritmus, jak najít to nejlevnější maximální párování.
Offline
Nestačilo by rozšířit definici vylepšující střídavé cesty tak, že buď se pomocí ní zvětší počet hran v párování nebo se sníží jeho cena? (jen nápad, ale takhle z hlavy nevidím protipříklad :) ). To by asi šlo ukázat, že když máme dvě maximální párování který se liší v nějakých hranách, tak jde z jednoho ke druhýmu přejít pomocí nějakých střídavých cest a každou má cenu použít, jen když to zlevní ...
Offline
A jak se tedy normálně řeší problém čínského pošťáka? Já jsem snad ani o tomhle nenašel žádný pořádný materiál... Vidím to na konzultaci, jestli ji ještě stihnu :-).
Offline
↑ Lukee:
Zdravím :-)
Zde kniha v rustine http://books.prometey.org/read.php/djvu=14696 od str. 114 (dvoustrana) nebo 215 originálu pojednává o činskem pošťákovi.
Autorem knihy je N. Christophides nebo Christofides? (snad jsem to moz nezkomolila) - třeba pohledat v jine reci http://en.wikipedia.org/wiki/Christofides_algorithm
http://www.itl.nist.gov/div897/sqg/dads … stman.html - zde se mi to zda čitelné.
zde můj horor - překlad popisu algoritmu (pořadné označení je v original textu),
vaha je asi "ohodnocení", řetězec asi "cesta" a ještě jsou odkazy na jine kapitoly:
čast 5.2.1
Krok 1. Necht matice c_ij vah hran grafu G. S použitím algoritmu nejkratšeho řetezce (viz kapitola 8) vytvoříme |X| x |X| matici D = d_ij, kde d_ij váha řetezce minimalní vahy, jdoucí z některého vrcholu x_i na další vrchol x_j
Krok 2. Najdeme takove řetezové parování M pro množinu X, které dává minimální vahu (v souladu s matici vah D). Efektivně toto jde udělát dle algoritmu minimálního parování dle kapitoly 12.
Krok 3. Pokud vrchol x_a se kombinuje (shoduje??) s dalším vrcholem x_b, pak určeny řetez je minimální vahy, odpovídající váze v kroku 1. Doplnimě uměle hranu v G odpovídající hrany z a provedeme to pro každý další řetez z množiny M, vysledkem je s-graf G (M)
Krok 4. Součet vah všech hran grafu G nalezeny pomoci matice M (za vahu umělé hrany se povazuje vaha ji rovnoběžné reální hrany) se rovna minimalni vaze cyklu, který prochází po G. Zároveň počet obchodu cyklu po hraně se rovna celkovému poctu rovnoběžných hran mezi x_i, x_j v G M.
Po tomto výkonu prohlásit, že mám složenou zkoušku z "Úvodu do teorie grafu" - to mohu rovnou podat prihlasku o titul ing. Kacanovou.
Ale pokud budu nejak napomocna (jen z prekladem) - staci dat vedet.
Ať se daří :-)
Offline
↑ jelena:
Díky moc :-). Ale to nejzásadnější to nerozluštilo --
"Krok 2. Najdeme takove řetezové parování M pro množinu X, které dává minimální vahu (v souladu s matici vah D). Efektivně toto jde udělát dle algoritmu minimálního parování dle kapitoly 12."
Tohle je ten problém, který neumím vyřešit :-(. Koukal jsem i do anglických materiálů, ale ani tam jsem nenalezl odpověď. Třeba tato stránka je hezká, ale omezují se tam jen na grafy s žádnými lichými uzly (pak je to standardní eulerovský tah) anebo s dvěma lichými uzly (pak najdou nejkratší cestu mezi těmito uzly a tyto hrany musí pošťák projít dvakrát). Já bych to potřeboval obecně pro jakýkoliv graf.
Offline
↑ Lukee:
v Kapitole 12 ruské knihy je toho velmi moc - to se nevyznám, to by muselo být řečeno, od kterého řádku se to má překládat: - myslím, že to je odstavec 3.1 v kapitole 12 na str. 391 originalu
Zde v kapitole 13 na zaver str. 80. http://www.uai.fme.vutbr.cz/~mseda/TG03_MS.pdf vypráví, jak se dá změnit maximální na minimální.
http://www.cs.vsb.cz/ochodkova/courses/gra/gal5.pdf - také mluví o maďarských cestách, jako v ruske variante.
Asi víc nebudu nápomocna, maximálně s nějakým překladem, pokud bude konkrétně řečeno - ale dnes už ne.
Zdravím :-)
Offline
Tak jsem ještě našla toto:
http://books.google.cz/books?id=pCcHSjz … lt#PPA2,M1 (kapitoly 7, 8)
http://ru.dleex.com/read/5221 - stejná kniha, ale zřejmě v jiném vydání - zde kapitoly 5, 6)
Ale nemám čas pohledat něco ke stažení :-(
Offline
↑ jelena:
Teď nevím, jestli tobě došel ten email ode mě :-). Doufám, že ano. Kdyby ne, tak tvůj email mi přišel (Díky!), ale koukal jsem se na něj až dnes -- měl jsem na plánu programování až dneska. Nakonec jsem se na to vykašlal a použil jsem obyčejné maximální párování, stejně jsem asi jediný člověk, co to alespoň nějak má :-). Ty ostatní algoritmy byly příliš složité :-(.
Offline
Stránky: 1