W dniu 2013-05-12 19:24, bartekltg pisze:
> W dniu 2013-05-12 17:14, Vax pisze:

> No nie wiem, uwaga o przeszukiwaniu kazdej kombinacji na całej
> tablicy kliknięć sugeruje, że nawet nie przeczytałeś dokładnie:/

ten ustęp tyczył rozwiązania "kombinacje wszystkich kliknięć w tablicę"
vs "kombinacje wszystkich kliknięć w krótszy bok". Jeżeli złożoność
drugiego określamy jako 2^(N*M) to także nie uwzględniając złożoności
"testu".

do góry

W dniu 2013-05-12 21:21, Vax pisze:
> W dniu 2013-05-12 19:24, bartekltg pisze:
>> W dniu 2013-05-12 17:14, Vax pisze:
>
>> No nie wiem, uwaga o przeszukiwaniu kazdej kombinacji na całej
>> tablicy kliknięć sugeruje, że nawet nie przeczytałeś dokładnie:/
>
> ten ustęp tyczył rozwiązania "kombinacje wszystkich kliknięć w tablicę"
> vs "kombinacje wszystkich kliknięć w krótszy bok". Jeżeli złożoność
> drugiego określamy jako 2^(N*M) to także nie uwzględniając złożoności
> "testu".

No to wypadałoby to dorzucić do złożoności:) Ok, da sie to poprawić

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. Jeśli przeszukujemy wszystkie kombinacje włączony/
wyłączony jak liczby naturalne, zamortyzowany koszt jest również stały.
Można użyć też kodów Graya, wtedy następna kombinacja na pewno będzie
się różniła tylko o jeden bit (a wygenerowanie graya z kolejnych liczb
to jeden shift i jeden xor:)).

Rzeczywiście da się więc zrobić każdą iterację z 2^(m*n) testów
w czasie stałym. Tylko po co;)

pzdr
bartekltg

do góry

W dniu 2013-05-12 22:49, bartekltg pisze:
> W dniu 2013-05-12 21:21, Vax pisze:
>> W dniu 2013-05-12 19:24, bartekltg pisze:
>>> W dniu 2013-05-12 17:14, Vax pisze:
>>
>>> No nie wiem, uwaga o przeszukiwaniu kazdej kombinacji na całej
>>> tablicy kliknięć sugeruje, że nawet nie przeczytałeś dokładnie:/
>>
>> ten ustęp tyczył rozwiązania "kombinacje wszystkich kliknięć w tablicę"
>> vs "kombinacje wszystkich kliknięć w krótszy bok". Jeżeli złożoność
>> drugiego określamy jako 2^(N*M) to także nie uwzględniając złożoności
>> "testu".
>
> No to wypadałoby to dorzucić do złożoności:) Ok, da sie to poprawić
>
> 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. Jeśli przeszukujemy wszystkie kombinacje włączony/
> wyłączony jak liczby naturalne, zamortyzowany koszt jest również stały.

Urwało mi komentarz: każdy w 'szkole' miał analizę "licznika binarnego"
http://www.im.pwr.wroc.pl/~kik/AiSD/wyklady/aisd7.pd
f
to dokładnie to samo.

> Można użyć też kodów Graya, wtedy następna kombinacja na pewno będzie
> się różniła tylko o jeden bit (a wygenerowanie graya z kolejnych liczb
> to jeden shift i jeden xor:)).
>
> Rzeczywiście da się więc zrobić każdą iterację z 2^(m*n) testów
> w czasie stałym. Tylko po co;)


pzdr
bartekltg

do góry

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...
Nadto można brać pod uwagę symetrię, obroty itp. tylko czy w pewnym
momencie ów "narzut optymalizacyjny" nie zacznie być droższy niż
uzyskane efekty?

do góry

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.

Opisany prze zemnie algorytm ma cześć 'wygładniczą'
2^l, gdzie l jest co najwyżej 5.

pzdr
bartyekltg

do góry

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

do góry

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...

A.L.

do góry

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

do góry

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

PS. jeśli post pojawi się dwa razy, wszytko wina aioe:)

do góry

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.

do góry