bartekltg <b...@g...com> wrote:
> Hehe, spryciarz;> A dla 39x39?

No, tak 2^32 rozwiązań nie przejrzę :O

? matrank(matker(m))
time = 84 ms.
%16 = 32

Ale przypadkowe poniżej 1s

? m=Mod(M(39,39),2); l=m;l=l[,1]+l[,39]+l[,7]; s=matinverseimage(m,l);m*s==l
time = 889 ms.
%15 = 1

Z czego większość zajmuje kiepska procedura budowy m:

? m=Mod(M(39,39),2);
time = 616 ms.

Bo samo rozwiązanie to nic:

? s=matinverseimage(m,l);
time = 84 ms.

do góry

W dniu 2013-05-13 22:03, Miroslaw Kwasniak pisze:
> bartekltg <b...@g...com> wrote:
>> Hehe, spryciarz;> A dla 39x39?
>
> No, tak 2^32 rozwiązań nie przejrzę :O
>
> ? matrank(matker(m))
> time = 84 ms.
> %16 = 32

To wspomniane pari-gp?

Ile wychodzi dla większych? powiedzmy 55 czy 64.


> Ale przypadkowe poniżej 1s
>
> ? m=Mod(M(39,39),2); l=m;l=l[,1]+l[,39]+l[,7]; s=matinverseimage(m,l);m*s==l
> time = 889 ms.
> %15 = 1
>
> Z czego większość zajmuje kiepska procedura budowy m:

Spróbuj może tak:
N = macierz pasmowa n x n o paśmie [1,0.5,1]
(na diagonali 0.5. Nad i pod diagonalą 1).
M = to samo, ale rozmiaru m x m

Teraz poszukiwana macierz to

A = M (*) Id[n] + Id[m] (*) N

gdzie (*) to iloczyn kroneckera, pewnie jest zaimplementowany.

Mathematice zajmuje to 1.2s, ale matlabowi (w bebechach pewnie
bliższe pari) wyszło 0.007236s:)

pzdr
bartekltg

do góry

bartekltg <b...@g...com> wrote:
> W dniu 2013-05-13 22:03, Miroslaw Kwasniak pisze:
>> bartekltg <b...@g...com> wrote:
>>> Hehe, spryciarz;> A dla 39x39?
>>
>> No, tak 2^32 rozwiązań nie przejrzę :O
>>
>> ? matrank(matker(m))
>> time = 84 ms.
>> %16 = 32
>
> To wspomniane pari-gp?

Tak

> Ile wychodzi dla większych? powiedzmy 55 czy 64.

? n=55;m=Mod(M(n,n),2);
time = 1,837 ms.
? matrank(matker(m))
time = 292 ms.
%5 = 0

? n=64;m=[];m=Mod(M(n,n),2);
time = 3,112 ms.
? matrank(matker(m))
time = 561 ms.


> A = M (*) Id[n] + Id[m] (*) N
>
> gdzie (*) to iloczyn kroneckera, pewnie jest zaimplementowany.

Chyba nie ma (w tym sensie co myślimy), ale pari jest dziwne, jak wszystko
co francuskie ;)

do góry

W dniu poniedziałek, 13 maja 2013 14:04:26 UTC+2 użytkownik bartekltg napisał:

> Bo to było w poprzednich postach (ten jest już o nieco czym innym:)),
Coś jest nie tak, chyba nie mam połowy postów.
Pozdrawiam

do góry

bartekltg <b...@g...com> wrote:
> 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 ?

To wygląda ciekawie:

http://online.redwoods.edu/instruct/darnold/laproj/F
all2001/Emilia/emilia_paper.pdf

https://ida.mtholyoke.edu/xmlui/bitstream/handle/101
66/693/375.pdf?sequence=1
http://www.unf.edu/~wkloster/fibonacci/switch.ps
www.unf.edu/~wkloster/fibonacci/lama.pswww.unf.edu/~
wkloster/fibonacci/lama.ps

www.m-hikari.com/ijcms-2010/29-32-2010/leeIJCMS29-32
-2010.pdf

do góry

W dniu 2013-05-14 12:10, Miroslaw Kwasniak pisze:
> bartekltg <b...@g...com> wrote:
>> 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 ?
>
> To wygląda ciekawie:
>
> http://online.redwoods.edu/instruct/darnold/laproj/F
all2001/Emilia/emilia_paper.pdf

O, to jest genialne:)

Dla tych, co nie czytali:
Gwóźdź jest w rozdziale 4. Zamiast myśleć o równaniu na m*n
wspolczynnikow patrzymy na to jak na układ m rownań na n
wspolczynnikow (to jeszcze nic ciekawego), a dzieki odpowiedniej
strukturze naszej macierzy problem rozbija się na

m-1 rownań postaci:
kawałak rozwiązania = Maceirz_i (zapalenia, pierwszy kawałek rozwiązania)

oraz równanie

Macierz*pierwszy kawalek rozwiazania = macierze_1 (zapalenia).

Wszystkie macierze są n x n .

Cała siłowa cześć siedzi w ostatnim rownaniu (mamy taką intuicję,
że tylko ostatnia linijka się liczy. W rozwiązaniu Vaxa z tego
korzystaliśmy, ale nie wiedzialem, że da się w podejściu
algebraicznym do tego dojść). Zarówno rozwiązanie zadanych zapaleń,
jak i znalezienie wektorów zerowych wymaga rozłożenia tylko tej
ostatniej macierzy.
Za darmo dostajemy też to, co wcześniej trzeba bylo (prosto) sobie
udowodnić, że dim(ker(A)) <= n (jak wszędzie n<=m)

Zwłaszcza ogromną korzyść odnosimy, gdy m>>n:)

> www.m-hikari.com/ijcms-2010/29-32-2010/leeIJCMS29-32
-2010.pdf

> https://ida.mtholyoke.edu/xmlui/bitstream/handle/101
66/693/375.pdf?sequence=1
> http://www.unf.edu/~wkloster/fibonacci/switch.ps
> www.unf.edu/~wkloster/fibonacci/lama.pswww.unf.edu/~
wkloster/fibonacci/lama.ps

Jeszcze nie poczytałem...

pzdr
bartekltg

do góry

W dniu 2013-05-14 03:29, M.M. pisze:
> W dniu poniedziałek, 13 maja 2013 14:04:26 UTC+2 użytkownik bartekltg napisał:
>
>> Bo to było w poprzednich postach (ten jest już o nieco czym innym:)),
> Coś jest nie tak, chyba nie mam połowy postów.

Na ataman, neostradzie i aoie na oko jest wszytko.

Zerknij w ten link:

http://www.math.ksu.edu/~dmaldona/math551/lights_out
.pdf

A przed chwilą Mirosław podrzucił jeszcze lepsze prace.
Message-ID: <kmt2in$9am$1@z-news.wcss.wroc.pl>

pzdr
bartekltg

do góry

W dniu 2013-05-13 13:07, Miroslaw Kwasniak pisze:
> Vax <...@i...nie.ma> wrote:

> Ale to nie musi to być rozwiązanie optymalne - gdy takiego szukasz, to musisz
przejrzeć wszystkie :(
> Chyba, że null-space jest pusta.

rozwiązanie "optymalne" to nie był mój postulat, algorytm miał podać
rozwiązanie lub zakomunikować,, że takowe nie istnieje

> Każda metoda ma swój techniczny zakres stosowalności.
> Twoja jest dobra dla wąskich macierzy, ale co zrobisz dla 40 x 40?

Czegoś nie rozumiemy chyba. Prosiłem nie o algorytm, ale o wstępne
oszacowanie. Ta metoda jest odpowiedzią na oszacowanie, które
wskazywałoby by na algorytm sprawdź wszystkie kombinacje kliknięć w
tablicy" i wskazuje, że prostym zabiegiem można znacznie liczbę iteracji
zmniejszyć (i nie sprawdzać kombinacji z góry skazanych na niepowodzenie).
Czy ja się upieram, że to najlepsze rozwiązanie dla każdego zestawu
danych (toż nawet sortowania nie ma uniwersalnego), tylko dlatego, że
nie wklejam tu linków do innych? Ktoś to już zrobił za mnie więc po co?

do góry

M.M. <m...@g...com> wrote:
>
> 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.

Jeżeli ja Ciebie rozumiem i się nie mylę - to niestety intuicja się myli ;)

Dla stanu początkowego
? a
%80 =
[1 1 1 0 0]

[1 1 1 1 1]

[1 1 1 1 1]

[0 1 0 0 0]

[0 0 0 1 1]

Wszytkie 4 nieredundantne rozwiązania zawierają pola, które nawet 4-5 razy zmieniają
stan.

nr=0 moves=13
Solution: changes:
[0 0 0 1 0] [1 1 1 2 2]

[1 1 0 1 1] [3 3 3 3 3]

[1 1 1 0 1] [3 5 3 3 3]

[0 1 1 0 1] [2 3 4 2 2]

[0 0 1 0 0] [0 2 2 1 1]

nr=1 moves=11
Solution: changes:
[0 1 1 0 0] [1 3 3 2 0]

[0 1 1 1 0] [1 3 5 3 1]

[0 0 1 1 0] [1 3 3 3 1]

[1 1 0 0 0] [2 3 2 2 0]

[0 1 0 1 0] [2 2 2 1 1]

nr=2 moves=15
Solution: changes:
[1 0 1 1 1] [1 3 3 4 2]

[0 1 1 1 0] [3 3 5 3 3]

[1 1 1 0 1] [3 5 3 3 1]

[1 1 0 0 0] [4 3 2 0 2]

[1 0 0 0 1] [2 2 0 1 1]

nr=3 moves=17
Solution: changes:
[1 1 0 0 1] [3 3 1 2 2]

[1 1 0 1 1] [3 3 3 3 3]

[0 0 1 1 0] [1 3 3 3 3]

[0 1 1 0 1] [2 3 4 4 2]

[1 1 1 1 1] [2 4 4 3 3]

do góry

Vax <...@i...nie.ma> wrote:
> W dniu 2013-05-13 13:07, Miroslaw Kwasniak pisze:
>> Vax <...@i...nie.ma> wrote:
>
>> Ale to nie musi to być rozwiązanie optymalne - gdy takiego szukasz, to musisz
przejrzeć wszystkie :(
>> Chyba, że null-space jest pusta.
>
> rozwiązanie "optymalne" to nie był mój postulat, algorytm miał podać
> rozwiązanie lub zakomunikować,, że takowe nie istnieje

OK

>> Każda metoda ma swój techniczny zakres stosowalności.
>> Twoja jest dobra dla wąskich macierzy, ale co zrobisz dla 40 x 40?
>
> Czegoś nie rozumiemy chyba. Prosiłem nie o algorytm, ale o wstępne
> oszacowanie.

Oszacowanie złożoności problemu, zależy od algorytmu ;)

> Ta metoda jest odpowiedzią na oszacowanie, które
> wskazywałoby by na algorytm sprawdź wszystkie kombinacje kliknięć w
> tablicy" i wskazuje, że prostym zabiegiem można znacznie liczbę iteracji
> zmniejszyć (i nie sprawdzać kombinacji z góry skazanych na niepowodzenie).

OK

> Czy ja się upieram, że to najlepsze rozwiązanie dla każdego zestawu
> danych (toż nawet sortowania nie ma uniwersalnego), tylko dlatego, że
> nie wklejam tu linków do innych? Ktoś to już zrobił za mnie więc po co?

Ale istnieje pojęcie złożoności O()
O ile rozumiem, to Twoja metoda wymaga sprawdzenia do 2^n kombinacji w
pierwszym wierszu. Metoda macierzowa (n*m)^3, a w świetle

http://online.redwoods.edu/instruct/darnold/laproj/F
all2001/Emilia/emilia_paper.pdf

dla n=m to chyba n^4 zamiast n^6

Widzisz różnicę?

do góry