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

1 domo.fiala
položil/-a 14.11.2017

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
1 domo.fiala
odpověděl/-a 23.11.2017
 
upravil/-a 23.11.2017

Doplnění: Maďarský algoritmus zmiňovaný v mém předchozím řešení je chybový. V případě, že má příliš mnoho řešení selhvává a vrací více soupeřů jednomu hráči.

Jak zde Michal Illich několikrát zmiňuje, správné řešení je tzv Edmonds Blossom algoritmus, viz Wiki en.wikipedia.org/wiki/Blossom_algorithm a implementace v JS (pro Node) npmjs.com/package/edmonds-blossom
Ten vyžaduje na vstupu všechny možné páry, ze kterých má vybírat společně s bodovou vzdáleností soupeřů v páru. Avšak co mi dlouho unikalo: tato vzdálenost je ve smyslu čím vyšší, tím lepší.
Takže na vstupu do funkce mám mapu unikátních párů (např. pouze 0vs1 a ne 0vs1 a zároveň 1vs0) se "vzdáleností" těchto soupeřů, kde čím vyšší číslo, tím lepší (takže dávám nulu párům, které již spolu dříve hráli).

Vstup:

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

Výstup:

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

Čtený následovně: hráči index 0 přiděl soupeře hráče index 6, hráči index 1 přiděl hráče index 8, hráči index 2 přiděl hráče index 14... hráči index 6 přiděl soupeře index 0 (duplicita), ve výstupu se může nacházet i -1, v takovém případě se tento výsledek přeskakuje. Po odfiltrování výsledků od duplicit a nepoužitých (-1) mám přesně osm párů.

Celá implementace včetně přípravy párů, výpočtu vzdálenosti hráčů a filtrování výsledků viz github.com/dominikfiala/turnaj-sprtec/blob/desktop/src/app.js#L214-L251

PS: Další problém byl, že jsem NPM balíček chtěl spouštět v prohlížeči, ten je však připraven pro modulové použití v Nodejs. Chvíli jsem studoval možnosti Browserify a RequireJS, nechtělo se mi ale kvůli jediné funkci vyrábět celý build proces a pak jsem narazil na wzrd.in, který je "CDN pro Browserify". Zadáte mu balíček z NPM a on vám jej vrátí v podobě použitelné v prohlížeči, viz wzrd.in/standalone/edmonds-blossom@latest pro balíček npmjs.com/package/edmonds-blossom

Komentáře

  • Michal Illich : Super! 27.11.2017

Pro zobrazení všech 9 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.