Administrace komentářů

Problém je, že algoritmus spoléhající na to, že se "to jednou povede" vlastně prohledává celý stavový prostor, tedy má složitost minimálně O(N!) (při skutečně náhodných číslech není vůbec zaručeno ukončení algoritmu!). Při počtu závodníků 300 je to 300! , což je číslo... opravdu velké. Jistě, je to jen horní hranice. Ale zaručuji že zrovna když bude potřeba rychle vygenerovat pořadí, bude to generovat miliardy špatných řešení (Murphy).

Vygenerování jednoho pořadí je triviální, již zde bylo několik dobrých odkazů. Stačí jedno pole, cyklus 1 až N-1 (N=počet závodníků) a provádět swap.

Generovat další pořadí, kdy tam je navíc podmínka minimální vzdálenosti od předchozích, již vůbec triviální není. Lze prostě stejným způsobem vygenerovat pořadí a zjistit zda vyhovuje, ale to se může neúměrně protáhnout.

Je tedy nutné vzít v úvahu, že při druhém umísťování má každý závodník až o 5 možností méně (minimálně 3 pro závodníky na krajích pozicích). Obecně, 2D-1 (D je minimální požadovaná vzdálenost mezi pozicemi, D>0). V dalším umisťování je to dokonce až dvakrát tolik, tedy 10 (4D-2).

Algoritmus tedy musí brát v úvahu, že každý závodník má omezený počet pozic. Navrhoval bych tedy u každého evidovat kolik pozic mu ještě zbývá a při každém generování kromě prvního jim pozice přidělovat v pořadí podle počtu možností. Myslím že rozvinutím úvahy v předchozím odstavi půjde dokázat, že pro určitý maximální počet startů S bude vždy možné všem závodníkům přiřadit pozici. Pak nebude potřeba provádět rollback (tedy začínat znova). Možná ale že nic takového dokázat nejde. Skutečně nemám čas to příliš rozebírat...

Je zde jednodušší alternativa: vygenerovat náhodně jen první pozice, pro další starty provádět jen rotaci. V nejjednodušším případě, tedy rotace o D, musí platit podmínka že D+D*(S-1) = D*S <= N (závodník co začíná na pozici D musí po S-1 posunech skončit nejdále na poslední pozici). Toto by ale závodníci rychle prohlédli a asi by se jim to nelíbilo.

Složitější bezpečná varianta je provádět posuny o náhodnou hodnotu z intervalu <D,(N-D)/(S-1)> (oboje včetně). Opět je zajištěno, že ani v nejhorším případě nedojde k vygenerování nepřijatelné startovací listiny (cvičení: dokažte .

Problém obou rotačních řešení je, že jednotlivé startovací listiny nejsou navzájem nezávislé - tedy, zjednodušeně, nejsou "opravdu náhodné". Samozřejmě že po jejich vygenerování je nutno je navzájem zamíchat.

Nejlepší bude hybridní řešení: Nejprve zkusit startovací listiny generovat náhodnými pokusy a zavrhováním špatných výsledků. Počet pokusů však omezit nějakým empiricky zjištěným rozumným číslem (třeba 100). Pokud počet pokusů vyprší aniž by bylo vygenerování S použitelných listin, použije se výše zmíněný rotační algoritmus.

PS: Doufám že to bude užitečné... A hlavně doufam že jsem nikde neudělal botu a nepíšu ptákoviny.