Hmm, dopiero co była poprzednia edycja, albo obsuwa,
albo robią co pół roku;-)

http://potyczki.mimuw.edu.pl/

21-28 maja.

pzdr
bartekltg

do góry

W dniu 2013-05-09 14:15, bartekltg pisze:
> Hmm, dopiero co była poprzednia edycja, albo obsuwa,
> albo robią co pół roku;-)

to może ktoś się podejmie oszacować złożoność obliczeniową takiego problemu:

Mamy prostokątną tablicę M x N z dwustanowymi komórkami. Przełączenie
wskazanej komórki powoduje automatyczne przełączenie komórek
sąsiadujących od góry, dołu, z lewej i prawej (o ile takie występują).
Modelem może być szachownica zapełniona bierkami z reversi, ruch posiada
dwie fazy - odwracasz wybraną bierkę, a następnie jej najbliższych
sąsiadów (poza tymi po przekątnych).

Należy dla zastanego stanu (w szczególnym przypadku wszystkie komórki w
stanie "0") odnaleźć sekwencję ruchów, która wszystkie komórki
doprowadzi do stanu "1" lub stwierdzić, że taka sekwencja nie istnieje.

Chyba nie za trudne? ;)

do góry

W dniu piątek, 10 maja 2013 20:15:52 UTC+2 użytkownik Vax napisał:

> to może ktoś się podejmie oszacować złożoność obliczeniową takiego problemu:
> [...]
> Chyba nie za trudne? ;)

Ogolnie dla tego typu problmow to przeszukiwanie drzewa gry ze
spamietywaniem. Czyli ilosc obliczen x^(NxM) i ilosc pamieci tez x^(NxM),
gdzie x to ilosc stanow pola. Podales szczegolny przypadek tego
problemu, byc moze dla niego jest szybszy sposob.

Pozdrawiam

do góry

W dniu 2013-05-11 09:14, M.M. pisze:
> W dniu piątek, 10 maja 2013 20:15:52 UTC+2 użytkownik Vax napisał:
>
>> to może ktoś się podejmie oszacować złożoność obliczeniową takiego problemu:
>> [...]
>> Chyba nie za trudne? ;)

Na atman nie widać tego posta:(


pzdr
bartekltg

do góry

W dniu 2013-05-11 09:14, M.M. pisze:
> W dniu piątek, 10 maja 2013 20:15:52 UTC+2 użytkownik Vax napisał:
>
>> to może ktoś się podejmie oszacować złożoność obliczeniową takiego
>> problemu: [...] Chyba nie za trudne? ;)

Z innego serwera:

> to może ktoś się podejmie oszacować złożoność obliczeniową takiego
> problemu:
>
> Mamy prostokątną tablicę M x N z dwustanowymi komórkami. Przełączenie
> wskazanej komórki powoduje automatyczne przełączenie komórek
> sąsiadujących od góry, dołu, z lewej i prawej (o ile takie
> występują). Modelem może być szachownica zapełniona bierkami z
> reversi, ruch posiada dwie fazy - odwracasz wybraną bierkę, a
> następnie jej najbliższych sąsiadów (poza tymi po przekątnych).
>
> Należy dla zastanego stanu (w szczególnym przypadku wszystkie komórki
> w stanie "0") odnaleźć sekwencję ruchów, która wszystkie komórki
> doprowadzi do stanu "1" lub stwierdzić, że taka sekwencja nie
> istnieje.
>
> Chyba nie za trudne?

Było niedawno na pl.sci.matematyka
From: "J.F" <j...@p...onet.pl>
Newsgroups: pl.sci.matematyka
Subject: szachownica xor
Date: Tue, 5 Mar 2013 19:09:02 +0100
Message-ID: <513634bf$0$1218$65785112@news.neostrada.pl>


W skrócie, parzysta liczba 'kliknięć' w pole jest redukowana
do zera. Kolejność klikania też nie ma znaczenie.
Możesz więc klikną raz lub w ogole. Stąd też wiadomo,
że kliknięć nie będzie więcej niż pol szachownicy.


Zapisz kliknięcia jako wektor v. Wtedy stan danego pola możesz
opisać jakio w = A*v
gdzie A to niezbyt gęsta macierz (mniej niż 5*n*m elementów).
Oba wektory mają długość m*n, maciesrz siłą rzeczy (m*n)x(m*n).
Wszytko dzieje się modulo 2.

Konfiguracja zapalająca czy konfiguracja gasząca to to samo,
więc szykamy v, takiego, że w to nasz stan początkowy i
w = A*v

Po pierwsze, da się rozwiązać, kiedy w siedzi w przestrzeni rozpiętej
przez kolumny A (jest a obrazie A, dość trywialny wniosek).
Ponieważ obraz A będzie duży, łatwiej do algorytmu wyznaczyć kojądro*)
i sprawdzać, czy aby nasza oczekiwana konfiguracja sie z nim nie
przecina (iloczynem skalarnym).

Wiecej szczegółow.
http://www.math.ksu.edu/~dmaldona/math551/lights_out
.pdf

*) tutaj macierz A budujemy tsak, by była symetryczna A^T=A,
więc kojądro i jądro (null space) to to samo.

Ok, rozwiążemy równanie macierzowe w Z^2 (n*m)^3 ?
Ale nie musi być to rozwiązanie optymalne, do rozwiązania
możemy zawsze dorzucić wektor z jądra, i to może dać
mniej jedynek w rozwiązaniu.
Np dla tablicy 19x19 wymiar jądra to 16, więc trzeba by
sprawdzić 65 tysiecy przypadków:/
Czy istnieje jakiś lepszy sposób na przeszukanie takiego zestawu?

Jeszcze mniej formalny link z wątku z matematyki:

http://www.jaapsch.net/puzzles/lights.htm


pzdr
bartekltg

do góry

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.
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" ;)

do góry

W dniu 2013-05-11 09:14, M.M. pisze:
> W dniu piątek, 10 maja 2013 20:15:52 UTC+2 użytkownik Vax napisał:
>
>> to może ktoś się podejmie oszacować złożoność obliczeniową takiego problemu:
>> [...]
>> Chyba nie za trudne? ;)
>
> Ogolnie dla tego typu problmow to przeszukiwanie drzewa gry ze
> spamietywaniem. Czyli ilosc obliczen x^(NxM) i ilosc pamieci tez x^(NxM),
> gdzie x to ilosc stanow pola. Podales szczegolny przypadek tego
> problemu, byc moze dla niego jest szybszy sposob.

No wiesz... dla tablicy np. 1xN wystarczy sprawdzić raptem 2 możliwości
by znaleźć wszystkie rozwiązania, o ile takie istnieją :)

do góry

W dniu 2013-05-11 12:28, bartekltg pisze:
> W dniu 2013-05-11 09:14, M.M. pisze:

> Zapisz kliknięcia jako wektor v. Wtedy stan danego pola możesz
> opisać jakio w = A*v
> gdzie A to niezbyt gęsta macierz (mniej niż 5*n*m elementów).

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 :)

do góry

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

do góry

W dniu sobota, 11 maja 2013 18:12:55 UTC+2 użytkownik Vax napisał:
> 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
Dobre spostrzezenie.

Ciekawe jak to mozna wykorzystac do zwyklego algorytmu ze spamietywaniem,
a moze nawet bez spamietywania.

Mozna troche przerobic Twoje spostrzezenie. Kazdy klik pewne pola zapala a
inne gasi. Niech to bedzie klik x. Wiec klik x determinuje kliki ktore
musza zgasic to co on zapalil. Jesli kolejnosc jest niewazna, to klik x
moze determinowac je jako kliki w nastepnej kolejnosci. Wiec kazde pole moze
miec zapamietany numer+1 rekurencyjnego wywolania w ktorym zostalo zapalone
lub jeden jesli bylo dane w ukladzie poczatkowym. Algorytm w kazdym
kroku musi zgasic dowolne pole o najmniejszym numrze. To na pewno zmniejszy
breanch-faktor.

Pozostaje kwestia czy mozna jakos uniknac spamietywania?

Algorytm z spamietywaniem jest prosty Jesli docieramy do ukladu ktory byl
wczesniej, to wnioskujemy ze zaczyna sie petlic. Ale takie podejscie
wymagaloby sporo pamieci.

Moze wystarczy zapamietac z kazdym polem, ze juz bylo raz zapalone i potem
zgaszone? Intuicja podpowiada, ze nie ma sensu zapalac danego pola dwa razy.
Nie wiem czy moja intuicja sie nie myli, ale jesli to prawda, to algortym
moze przerwac przeszukiwanie danej galezi, jesli nie da sie zgasic jakiegos
pola bez zapalania tych pol, ktore juz wczesniej byly zgaszone.

Pozdrawiam

do góry