Grafový algoritmus: ideální párování soupeřů rubrika: Programování: JavaScript

3 domo.fiala
položil/-a 14.11. 21:49

Otázka spíše na matematiky, než programátory, snad se tu najde někdo s průnikem těchto znalostí.

Vyrábím aplikaci v JavaScriptu pro řízení sportovního turnaje. Turnaj se skládá ze vzájemných zápasů dvou hráčů. V jednom kole hrají všichni hráči (po párech). Za výhru získává hráč dva body, za remízu jeden, za prohru žádný. V prvním kole hráče napáruji náhodně, v dalších kolech už potřebuji hráče párovat tak, aby spolu hráli hráči se stejným, nebo aspoň podobným bodovým hodnocením. V turnaji proti sobě můžou dva konkrétní hráči sehrát pouze jeden zápas.

Již jsem prošel několik slepých uliček, nastudoval spoustu řešení, ale jediné ideální řešení je grafový algoritmus Maximum Weight Perfect Matching (obecný popis pro smrtelníky, Wiki). Může mě někdo navést, jak toto řešit ve světě JavaScriptu?

Příklad: Mám rozehraný turnaj 16 hráčů, odehráno šest kol. První řádek a sloupec grafu jsou ID hráčů (0-15), na osách pak buď -1 (hráč nemůže hrát sám se sebou), -2 (tito dva hráči už spolu hráli) nebo kladné číslo (bodový rozdíl hráčů). Úkolem je najít ze všech možných vzájemných zápasů (71 možných) kombinaci osmi zápasů do dalšího kola tak, aby hráli všichni hráči a zároveň aby to byly zápasy hráčů s co nejnižšími bodovými rozdíly.

PS: Vypočítání všech kombinací nepřipadá v úvahu, jedná se o číslo 71 nad 8 (10639125640).

Nejlépe to počítá program MacMahon (http://www.cgerlach.de/go/macmahon.html), v sekci "Pairing algorhitm" lehce vysvětleno, ale ten je v Javě.

Současný graf:

-1      0       8       1       6       11      15      13      4       3       5       14      10      12      9       7       2
 
0       -1      -2      -2      2       -2      3       -2      4       -2      4       4       -2      6       6       8       10
 
8       -2      -1      2       -2      -2      3       -2      4       4       -2      4       5       6       6       -2      10
 
1       -2      2       -1      0       1       1       1       2       -2      -2      2       3       -2      -2      -2      8
 
6       2       -2      0       -1      1       1       1       2       2       2       -2      -2      4       -2      6       -2
 
11      -2      -2      1       1       -1      0       -2      1       1       -2      -2      2       3       3       -2      7
 
15      3       3       1       1       0       -1      0       -2      1       1       -2      2       3       -2      5       -2
 
13      -2      -2      1       1       -2      0       -1      -2      1       -2      1       -2      3       -2      5       7
 
4       4       4       2       2       1       -2      -2      -1      0       0       -2      1       -2      -2      4       -2
 
3       -2      4       -2      2       1       1       1       0       -1      0       0       1       2       2       4       -2
 
5       4       -2      -2      2       -2      1       -2      0       0       -1      0       -2      2       2       -2      -2
 
14      4       4       2       -2      -2      -2      1       -2      0       0       -1      1       2       -2      4       6
 
10      -2      5       3       -2      2       2       -2      1       1       -2      1       -1      -2      1       3       5
 
12      6       6       -2      4       3       3       3       -2      2       2       2       -2      -1      0       -2      -2
 
9       6       6       -2      -2      3       -2      -2      -2      2       2       -2      1       0       -1      2       4
 
7       8       -2      -2      6       -2      5       5       4       4       -2      4       3       -2      2       -1      2
 
2       10      10      8       -2      7       -2      7       -2      -2      -2      6       5       -2      4       2       -1
odkaz Vyřešeno
3 domo.fiala
odpověděl/-a 20.11. 18:37

Na Stack Overflow mi poradili tzv Maďarský algoritmus en.wikipedia.org/wiki/Hungarian_algorithm, implememtace v Javascriptu github.com/addaleax/munkres-js a ten při prvotních testech funguje OK.

Díky všem za přičinění! Kdyby toto četl někdo v budoucnu a řešil podobný problém, tak vstupem je matice vzájemné bodového rozdílu dvou hráčů s tím, že pro nepoužitelné páry (již odehraná dvojice, nebo hráč sám proti sobě) jsem zvolil hodnotu, které nelze dosáhnout (v mém příkladu 6 odehraných zápasů, za výhru á 2 body = max bodový rozdíl mezi hráči je 12, pro neplatné kombinace dávám 18.

Vstup:

[ [ 18, 18, 11, 18, 5, 5, 3, 9, 18, 7, 18, 18, 7, 18, 5, 4 ],
  [ 18, 18, 9, 3, 3, 18, 18, 18, 3, 5, 4, 18, 5, 18, 3, 2 ],
  [ 11, 9, 18, 18, 7, 18, 9, 18, 18, 18, 6, 8, 18, 8, 7, 8 ],
  [ 18, 3, 18, 18, 1, 1, 3, 5, 18, 18, 18, 2, 3, 2, 18, 2 ],
  [ 5, 3, 7, 1, 18, 18, 18, 18, 5, 3, 2, 18, 3, 18, 18, 2 ],
  [ 5, 18, 18, 1, 18, 18, 18, 5, 5, 18, 2, 2, 3, 2, 18, 2 ],
  [ 3, 18, 9, 3, 18, 18, 18, 7, 18, 18, 18, 2, 5, 2, 3, 2 ],
  [ 9, 18, 18, 5, 18, 5, 7, 18, 9, 18, 4, 6, 18, 6, 18, 6 ],
  [ 18, 3, 18, 18, 5, 5, 18, 9, 18, 7, 6, 4, 7, 18, 5, 18 ],
  [ 7, 5, 18, 18, 3, 18, 18, 18, 7, 18, 18, 4, 1, 4, 3, 4 ],
  [ 18, 4, 6, 18, 2, 2, 18, 4, 6, 18, 18, 18, 2, 3, 2, 18 ],
  [ 18, 18, 8, 2, 18, 2, 2, 6, 4, 4, 18, 18, 18, 1, 2, 18 ],
  [ 7, 5, 18, 3, 3, 3, 5, 18, 7, 1, 2, 18, 18, 18, 18, 18 ],
  [ 18, 18, 8, 2, 18, 2, 2, 6, 18, 4, 3, 1, 18, 18, 2, 18 ],
  [ 5, 3, 7, 18, 18, 18, 3, 18, 5, 3, 2, 2, 18, 2, 18, 18 ],
  [ 4, 2, 8, 2, 2, 2, 2, 6, 18, 4, 18, 18, 18, 18, 18, 18 ] ]

Výstup:

[ [ 0, 6 ],
  [ 1, 8 ],
  [ 2, 14 ],
  [ 3, 5 ],
  [ 4, 15 ],
  [ 5, 3 ],
  [ 6, 0 ],
  [ 7, 10 ],
  [ 8, 1 ],
  [ 9, 12 ],
  [ 10, 7 ],
  [ 11, 13 ],
  [ 12, 9 ],
  [ 13, 11 ],
  [ 14, 2 ],
  [ 15, 4 ] ]

Čili první utkání hráč index 0 vs 6, druhé hráč index 1 vs 8 atd. Výsledek zahrnuje obě varianty vzájemného utkání (0 vs 6 i 6 vs 0), které stačí odfiltrovat (např. brát v potaz pouze prvky výstupu, kde a < b).

Komentáře

  • Michal Illich : Je u toho garantované, že u takovéhle symetrické matice neudělá neplechu v tom, že zatímco hráč A je přiřazen k B, tak naopak B bude přiřazen k někomu jinému? 21.11. 11:55
  • Michal Illich : Tady https://cs.stackexchange.com/questions/65694/assignment-algorithm-for-sy... a tady https://math.stackexchange.com/questions/972936/hungarian-algorithm-on-s... píšou, že to za určitých okolností nebude fungovat. Posuďte sám, jestli se vás to týká. Jinak v obou případech doporučují Blossom algoritmus. 21.11. 12:00
  • domo.fiala : Díky za zprávu, o chybovosti maďarského algoritmu slyším až teď od vás, určitě důležitá informace. Zatím jsem testoval pouze na malých sadách kde bylo OK. Ještě tedy zkouším Blossom, našel jsem tuto JS implementaci npmjs.com/package/edmonds-blossom, kde pokud správně čtu příklad zadávám vzdálenost dvou bodů (v příkladu je 0 od 1 = 6, 0 od 2 = 10 a 1 od 2 = 5) ale už nerozumím výsledku funkce. 2, -1, 0 znamená že vyberu ze vstupu nultý a druhý index, tedy cestu (zápas) 0 1 a 1 2? Takto jsem zkusil implementovat na zjednodušeném příkladu, viz runkit.com/dominikfiala/5a140b812903220011551414 kde jsou prvně v komentáři hráči, jejich body a protivníci, se kterými již hráli. Následně nadefinuji šest možných zápasů s bodovým rozdílem soupeřů, pustím do Blossom algoritmu a ten mi vrátí výsledek 1, 0, 3, 2, 5, 4. Toto ale není ideální párování, to je pro tento příklad [ [0, 5], [1, 3], [2, 4] ], viz stackoverflow.com/questions/47393042/tournament-pairing-algorhitm Nebo má být vstupem do Blossom všechny možné kombinace hráčů s tím, že ty které nechcu, aby algoritmus vybral, označím nějakou rapidně vysokou hodnotou vzdálenosti? 21.11. 12:49
  • Michal Illich : jo, zakázané páry si člověk může označit extrémně vysokou vzdáleností, pak by je to nemělo vybrat. jinak koukněte ještě na odkaz, co jsem posílal o kus níž, jako samostatnou odpověď. 21.11. 14:14

Pro zobrazení všech 7 odpovědí se prosím přihlaste:

Rychlé přihlášení přes sociální sítě:

Nebo se přihlaste jménem a heslem:

Zadejte prosím svou e-mailovou adresu.
Zadejte své heslo.