Žebříček ATP

• Data: Aktualizovaná data
• Orientační výsledky Kubalíkova algoritmu pro 30 běhů na každých datech: vysledky.zip

Kdybychom měli k úloze přistupovat jako k černé skříňce, neměli byste informace o vzájemných zápasech využívat nikde jinde než v ohodnocovací funkci. V této úloze ale je povoleno využívat či analyzovat vzájemné zápasy i jinde, např. v rekombinačních operátorech.

Máme bilanci výsledků vzájemných zápasů tenistů na okruhu ATP. Data jsou uložena v matici B, kde hodnota na pozici [i, j] vyjadřuje vzájemnou bilanci mezi hráči i a j, a to:

1. absolutně:
   • <latex>b_{ij} = n</latex>: hráč i v sezoně n-krát zvítězil nad hráčem j
2. relativně:
   • <latex>b_{ij} = 1</latex>: hráč i má pozitivní bilanci s hráčem j
   • <latex>b_{ij} = 0</latex>: hráč i má negativní bilanci s hráčem j

Cílem je sestavit žebříček (pořadí hráčů) tak, aby co nejlépe odpovídal vzájemným bilancím hráčů.

• Lineární sekvence (permutace) hráčů
• …

Kvalita daného žebříčku hráčů (permutace hráčů, <latex>\pi</latex>) se počítá pomocí následující funkce:

<latex> f(\pi) = \sum_{i=1}^{N-1} \sum_{j=i+1}^N B_{\pi(i)\pi(j)} </latex>

Tato funkce má být maximalizována.