Matematické Fórum

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?