W dniu 2013-05-13 01:13, A.L. pisze:
> On Mon, 13 May 2013 00:12:09 +0200, bartekltg <b...@g...com>
> wrote:
>
>> W dniu 2013-05-12 23:01, Vax pisze:
>>> W dniu 2013-05-12 22:51, bartekltg pisze:
>>>
>>>>> Rozpatrywanie tego algorytmu jest ma?o sensowne, ale skoro chcesz:
>>>>> mamy 2^(m*n) prób. W ka?dej musimy wygenerowa? tablic? opisuj?c?
>>>>> stan lampek. Je?li rzeczywi?cie b?dziemy budowa? j? od pocz?tku,
>>>>> wykonamy O(m*n) operacji. Ale nie musimy tego robi?, wystarczy, ?e
>>>>> naniesiemy poprawki. Je?li ró?ni? si? jeden bit, poprawka jest w 5
>>>>> miejscach. Super.
>>>
>>> tablica 5 x 100 - z dowolnej kombinacji masz 500 innych "ró?nych o jeden
>>> bit", ale czym?e to jest wobec 2^500...
>>
>> Jeste? jedyn? osob?, która w ogole wspomina o czym? takim!
>> Czy?by? sugerowa?, ?e "mój" alg tyle dzia?a? Czyli jednak nie
>> za?apa?e?;>
>>
>> Opisany prze zemnie algorytm ma cze?? 'wyk?adnicz?'
>> 2^l, gdzie l jest co najwy?ej 5.
>>
>> pzdr
>> bartekltg
>>
>
> A co z teoria algebraiczan tej gry? Rozwiazanie sprowadza sie do
> odwrocenai macierzy nad Z(2), mniej wiecej...

Daje poprawną serie kliknięć, ale skupiliśmy się na pytaniu
o serię optymalną (najmniejsza liczba kliknięć).

Przejrzyj moje dwa pierwsze posty w podwątku o grze, pisałem o tym.

Rozwiązanie układu

zapalenia = A*kliknięcia

daje nam _pewne_ rozwiązanie. Ale nie musi być to rozwiązanie optymalne
pod względem liczby kliknieć.
Do rozwiązania możemy dodać(mod 2) dowolny element z ker(A) i nadal
będzie poprawne rozwiązanie. Jeśli baza jądra jest k wymiarowa,
zawiera wektory w_j, to
klikniecia + b_j w_j (mod 2 po wspolrzednych)
dla każdej kombinacji b_j \in {0,1} jest rozwiązaniem.

Ale nie jest oczywiste, które jest optymalne, ani czy da się
je odszukać szybciej niż sprawdzając wszystkie kombinacje
(stąd było moje pytanie do Ciebie w tym wątku).

Co ciekawe, dim(ker(A)) <= min(m,n) :)

W linkowanej w pierwszym poście pracy jest tabelka dla
tablic kwadratowych, najczęśceij jest to znacznie mniej.
http://www.math.ksu.edu/~dmaldona/math551/lights_out
.pdf

pzdr
bartekltg