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ę?