W dniu 2013-05-11 18:12, Vax pisze:
> W dniu 2013-05-11 12:28, bartekltg pisze: [...]
>
> Zgoda w miejscach w których mowa o kolejności i parzystości, bo tak
> naprawdę wykonujemy serię XOR, które są naprzemienne i odwracalne.
>
> Haczyk polega na tym, że już wstępnie maksymalna liczbę iteracji
> możemy ograniczyć do 2^(min(M,N)) gdzie min() zwraca mniejszy z
> argumentów.

> Dlaczego? Ano dlatego, że aby zadanie w ogóle zostało spełnione to
> obraz zapalonych/zgaszonych komórek po wykonaniu "klików" na
> pierwszym rzędzie determinuje wymagane "kliki" rzędu 2, ten zaś
> narzuca kolejny rząd i tak dalej. A w ostatnim rzędzie przekonujemy
> się o ewentualnym sukcesie lub jego braku.

Opisany ponizej algorytm dla n*m>64 jest jednak O((2^n)*m) (dla m>=n)
na współczesnych maszynach.

Dla samego znalezienia rozwiązania moj algorytm
jest znacznie lepszy, działa wialomianowo.

Dla znalezienia rozwiązania optymalnego jest ciut gorzej,
trzeba dołożyć do tego xorowanie z jądrem (każdą kombinacją),
które może być duże. Ale jak duże?

Łatwo pokazać, że wymiar jądra jest mniejszy niż min(n,m).
Na dzień dobry mamy więc taką samą złożoność.

Ale to górne ograniczenie, może być znacznie lepiej.
Pierwsza tabelka z ostatniej strony pokazuje, że
w co drugim przypadku w ogole nie ma jądra, całą
wykładnicza zabawa odpada! W pozostałych przypadkach <22
tylko raz dobijamy do granicy (dla n=4).

Co więcej, stwierdzenie niemożności rozwiązania danej konfiguracji
jest wialomianowe. Jeśli rozwiązania nie ma, wiemy to przed
uruchomieniem wykładniczej części.

Twoj algorytm będzie szybszy w przypadku, gdy jedna z liczb
jest bardzo małą.
Algorytm zmatematyzowany może się z nim ścigać, jeśli macierze
i ich rozkład zostaną wyznaczone w czasie kompilacji.
Dla m,n rzedu kilkanaście, mniejsze kilkadziesiąt, nie jest
to problem techniczny ani pamięciowy.


> Następnie możemy się bawić w pomijanie układów symetrycznych, np.
> 11000 został już przetworzony jako 00011 itd. itp. - to póki co bez
> zaprzęgania "aparatu matematycznego" ;)

Jednak aparat dał nam nieco;>
Sztuczkę z "xor" == "+" (w Z_2) da się stosować w obu wersjach.


> do zapisania każdej serii "kliknięć" to mi zazwyczaj wystarczy INT o
> długości tylu bitów, ile pól liczy krótszy z boków, i nawet nie muszę
> mieć w pamięci miejsca na całą kopię tablicy wejściowej

Oczywista oczywistość. Tylko pamiętaj, żę jeden 64 bitowy int starcza
na m=n <=8. Mało.



pzdr
bartekltg