On 8/25/20 5:33 PM, Borneq wrote:
> to będzie szybsze dla rozmiaru 1000, zwłaszcza dla trudniejszego
> problemu - unikania dowlnych linii?

N-queens to dość łatwe zadanie, bo jest dużo rozwiązań i są
poumieszczane względnie gęsto. O wiele trudniejsze jest n-szpiegów,
gdzie każda trójka nie może być na tej samej linii. Nie dość że jeden
krok jest znacznie dłuższy, bo trzeba sprawdzać nie pary a trójki, to
jeszczze rezulaty występują bardzo rzadko w całej przestrzeni
permutacji. Moje pomiary dla N od 10 do 100 dla median czasów pozwala
przypuszczać że złożoność jest jak N^5.
Licząc na 4 rdzeniach to może być 48 pełnych 24-godzinnych dni na
rozwiązanie dla N=999
Chyba że jest jakaś technika optymaliacji o której zapomniałem. Czy np.
algorytm genetyczny byłby szybszy niż losowy swap elementów i patrzenie
czy się nie poprawia?