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. 04. 2022 17:21

daniel.dostal
Zelenáč
Příspěvky: 2
Škola: UPOL
Pozice: učitel
Reputace:   
 

Obdoba latinského čtverce - hledání vyváženého uspořádání prvků

Narazil jsem v praxi na problém z diskrétní matematiky a tuším, že nějaká zasvěcená dobrá duše zná lepší řešení než brute force.

Představme si, že organizujeme soutěž, do které každý z [mathjax]n[/mathjax] soutěžících přihlásí své dílo. Soutěž ale nemá porotce, tak se soutěžící domluví na postupu, kdy si každý "vylosuje" [mathjax]k[/mathjax] soutěžních děl a ta bude hodnotit. Takže každé dílo hodnotí [mathjax]k[/mathjax] hodnotitelů. Jak hodnocení probíhá a jak se s hodnoceními naloží, teď není podstatné, chceme však jednotlivá díla místo obyčejného losování rozdělit tak, aby platilo následující:

- Žádný hodnotitel nehodnotí své vlastní dílo.
- V sadě [mathjax]k[/mathjax] děl, která hodnotitel dostane k hodnocení, není žádná duplicita.
- Vezmeme-li si libovolné dva hodnotitele, pak v [mathjax]k[/mathjax]-ticích děl, která dostali k hodnocení, bude překryv v nejmenším možném počtu prvků (tzn. ideálně v jediném nebo žádném). Konkrétní příklad: pokud hodnotitel A hodnotí například díla X, Y a Z, a hodnotitel B hodnotí taky dílo X, pak (pokud možno) hodnotitel B již nehodnotí dílo Y ani Z.
- Takto vzniklá síť hodnotitelů a jejich děl je maximálně provázaná. Myslím tím toto: rozdělme hodnotitele na dvě skupiny a jako číslo [mathjax]m[/mathjax] označme počet takových hodnotitelů z první skupiny, kteří hodnotí alespoň jedno dílo někoho z druhé skupiny. Chceme najít takové řešení, kdy neexistuje takové rozdělení do dvou skupin, kdy je číslo [mathjax]m[/mathjax] rovno nule. Ideálně pak požadujeme, aby toto číslo bylo co nejdál od nuly, bez ohledu na to, jak dvě skupiny vytvoříme. (Tato podmínka je napsaná asi trošku neobratně, ale chci tím říct to, že kdyby [mathjax]m[/mathjax] mohlo dosáhnout čísla 0, tak to znamená, že se celý problém může rozpadnout na dva úplně nezávislé systémy. A to nechceme. Chceme co nejvyšší provázání.)

Pár praktických poznámek:
- Počítejme, že [mathjax]n[/mathjax] je několikanásobně věší než [mathjax]k[/mathjax]. Např. [mathjax]k = 5[/mathjax] a [mathjax]n = 100[/mathjax]. Pro nějaké krajní případy, kdy třeba [mathjax]n \approx k[/mathjax], je problém velmi snadno řešitelný třeba projitím všech kombinací.
- Doteď jsem to řešil tak, že jsem nastavil nějaké minimalizační kritérium a pustil na to třeba genetický algoritmus. Ale věřím, že existuje postup, který vhodné uspořádání nalezne v okamžiku.

Moje otázka zní: neznáte algoritmus, který nalezne řešení, které se co nejvíc blíží mým požadavkům?

Offline

 

#2 03. 04. 2022 00:23 — Editoval osman (03. 04. 2022 20:28)

osman
Příspěvky: 118
Pozice: v.v.
Reputace:   
 

Re: Obdoba latinského čtverce - hledání vyváženého uspořádání prvků

↑ daniel.dostal:
Zdravím,
možná by stálo za to zkoumat orientovaný graf G, kde uzly  [mathjax]1 .. n[/mathjax] představují účastníky soutěže a orientované hrany  [mathjax] (i,j)[/mathjax]  představují vztah hodnotitel - hodnocený.
Další podmínky:
===============
- Žádný hodnotitel nehodnotí své vlastní dílo. => graf neobsahuje smyčky, tj. hrany [mathjax] (i,i)[/mathjax]

- V sadě děl, která hodnotitel dostane k hodnocení, není žádná duplicita  => jestliže [mathjax] (i,j)[/mathjax]  [mathjax] (i,l)[/mathjax] jsou hrany, pak [mathjax] j<>l[/mathjax]

- každý "vylosuje" [mathjax]k[/mathjax] soutěžních děl a ta bude hodnotit. => z každého uzlu vychází  [mathjax]k[/mathjax] hran

- každé dílo hodnotí [mathjax]k[/mathjax] hodnotitelů => do každého uzlu vchází  [mathjax]k[/mathjax] hran

- rozdělme hodnotitele na dvě skupiny a jako číslo m označme počet takových hodnotitelů z první skupiny, kteří hodnotí alespoň jedno dílo někoho z druhé skupiny. Chceme najít takové řešení, kdy neexistuje takové rozdělení do dvou skupin, kdy je číslo m rovno nule. => Pokud graf není souvislý, nelze splnit.
===============

(Např. pro  [mathjax] k=1 [/mathjax] resp.  [mathjax] k=2 [/mathjax] je hned vidět např. řešení  [mathjax](1,2), (2,3)...(n,1)[/mathjax] resp.  [mathjax](1,2), (2,1), (2,3), (3,2)...(n,1),(1,n)[/mathjax], ale třeba z teorie grafů vypadne něco obecného)


Hlavní je zápal, talent se dostaví!

Offline

 

#3 03. 04. 2022 15:36

daniel.dostal
Zelenáč
Příspěvky: 2
Škola: UPOL
Pozice: učitel
Reputace:   
 

Re: Obdoba latinského čtverce - hledání vyváženého uspořádání prvků

↑ osman: Díky - reprezentovat to jako graf je docela slibný přístup. Zkusím to trochu prozkoumat.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson