PALMA junior
Úloha o Hopfieldovej sieti

Autorské riešenie
[stiahni py]                                       

• Počet riešiteľov: 22 / 22 = 100  %                       

• Úspešnosť riešenia:  4,2 / 6 = 70 %                   

Úlohou súťažiacich bolo vygenerovať mriežku veľkosti n×m so spinmi +1 a -1, ktoré môžeme interpretovať napríklad ako stavy neurónov v Hopfieldovej sieti. Základnou podmienkou úlohy bolo, aby v každom riadku aj v každom stĺpci mriežky existovala aspoň jedna bunka s hodnotou +1 a zároveň aspoň jedna bunka s hodnotou -1. Inými slovami, v žiadnom riadku ani stĺpci nesmeli byť všetky hodnoty rovnaké.

Priamy konštrukčný postup, ktorý by túto podmienku splnil pre ľubovoľné rozmery mriežky, nie je na prvý pohľad triviálny. Preto je prirodzené hľadať riešenie, ktoré kombinuje jednoduchý počiatočný nápad s postupným dolaďovaním výsledku.

Jedna z možných myšlienok riešenia je nasledujúca:

1. Rýchly štart - vytvorenie platnej mriežky: Najskôr si vytvoríme mriežku, ktorá už od začiatku spĺňa požadované podmienky. To dosiahneme tak, že do všetkých buniek nastavíme hodnotu +1 a následne po hlavnej uhlopriečke mriežky nastavíme hodnotu -1. Tým zabezpečíme, že každý riadok aj každý stĺpec obsahuje aspoň jednu hodnotu -1.

   Ak mriežka nie je štvorcová (n != m), uhlopriečka pokryje len časť riadkov alebo stĺpcov. Preto v "dlhšom" smere ešte doplníme hodnotu -1 na okraji mriežky tam, kde sa uhlopriečka skončí. Tým je zaručené, že aj zvyšné riadky alebo stĺpce budú obsahovať obe hodnoty +1 aj -1.

2. Náhodné lokálne úpravy - zlepšovanie riešenia: Po vytvorení počiatočnej mriežky už máme korektné riešenie, ktoré však má veľmi pravidelnú štruktúru. Preto ho ďalej "rozrušíme" pomocou náhodných lokálnych zmien.

   V každom kroku náhodne vyberieme jednu bunku mriežky a skúšame jej priradiť hodnotu +1 alebo -1. Takúto zmenu však povolíme iba vtedy, ak po nej zostane v príslušnom riadku aj stĺpci aspoň jedna hodnota +1 aj aspoň jedna hodnota -1.

   Aby bolo možné túto podmienku kontrolovať efektívne, počas celého algoritmu si priebežne udržiavame počty buniek s hodnotou +1 v každom riadku a v každom stĺpci. Vďaka tomu vieme v konštantnom čase rozhodnúť, či je konkrétna zmena prípustná, bez potreby opakovane prechádzať celú mriežku.

Nasleduje možný zdrojový kód v jazyku Python:

def mriezka(n, m):  
    if n < 2 or m < 2:
        print("n aj m musia byť aspoň 2")
        return

    # štart: všade +1
    A = [[1]*m for _ in range(n)]

    # -1 po uhlopriečke
    d = min(n, m)
    for i in range(d):
        A[i][i] = -1

    # koniec uhlopriečky: -1 na kraji
    if n > m:
        for i in range(d, n):
            A[i][m-1] = -1
    if m > n:
        for j in range(d, m):
            A[n-1][j] = -1

    # počty +1 v riadkoch a stĺpcoch
    r = [sum(x == 1 for x in A[i]) for i in range(n)]
    c = [sum(A[i][j] == 1 for i in range(n)) for j in range(m)]

    def moze(i, j, v):
        if A[i][j] == v:
            return False
        ri = r[i] + (v == 1) - (A[i][j] == 1)
        ci = c[j] + (v == 1) - (A[i][j] == 1)
        return 1 &lt;= ri &lt;= m-1 and 1 &lt;= ci &lt;= n-1

    # náhodné lokálne úpravy
    for _ in range(20 * n * m):
        i = random.randrange(n)
        j = random.randrange(m)
        v = random.choice([1, -1])
        if moze(i, j, v):
            if A[i][j] == 1:
                r[i] -= 1; c[j] -= 1
            if v == 1:
                r[i] += 1; c[j] += 1
            A[i][j] = v

    return A

Vaše zaujímavé riešenia a najčastejšie chyby

Medzi najzaujímavejšie riešenia patrili tie, ktoré korektne využívali parametre n a m, vracali mriežku v správnej dátovej štruktúre a systematicky kontrolovali podmienky pre riadky aj stĺpce. Objavili sa aj kreatívne prístupy, napríklad dopočítanie posledného riadku podľa stĺpcov alebo postup "vygeneruj a následne opravuj", ktoré však museli byť realizované veľmi opatrne, aby sa zachovala platnosť celej mriežky.

Najčastejšie chyby sa týkali kontroly podmienok: cykly while sa buď vôbec nespustili, alebo uviazli v nekonečnej slučke, často chýbala kontrola stĺpcov alebo bola kontrolovaná len jedna dimenzia. Veľmi častá bola aj zámena rozmerov (riadok má dĺžku m, nie n), nesprávne testovanie pomocou sum, ktoré neodhaľuje prítomnosť oboch spinov, používanie nepovolených hodnôt (0 alebo reťazce "+1", "-1") a najmä situácie, keď oprava stĺpca znehodnotila už opravený riadok. V mnohých prípadoch chýbala dodatočná validácia po opravách, takže výsledná mriežka nebola vždy garantovane správna.