On Mon, 13 May 2013 02:20:56 +0200, bartekltg <b...@g...com>
wrote:

>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_ou
t.pdf
>
>pzdr
>bartekltg
>
>PS. je?li post pojawi si? dwa razy, wszytko wina aioe:)
>

OK, zastanawial sie nad CLP (constraint logic programming) czy jakis
algorytmem heurystycznym typu A*. Jak sie zastanowie, to dam znac :)

Ale troche jestem zajety, wiec priorytet ma to-to niski

A.L.