N-Queens Problem - lokalne optimum

[Borneq]

Na Rosetta-code jest w c++ wersja wyszukująca rekurencyjnie
wiele(wszystkie?) rozwiązania dla N=12.
Jednak czas wzrasta bardzo szybko dla większych N.
Zrobilem inaczej:
hetmany muszą być w każdym wierszu w innej kolumnie, więc
robię wektor 0,1,2,3,4,5..199, tasuję go przez shuffle
zliczam ilośc kolizji, najpierw jest ponad setka
i losowo biorę wiersz A i wiersz B, zamieniam je gdy ilość kolizji maleje.
Bardzo szybko działa dla N=200
ALE...jest to niestabilne.
to znaczy: czasami działa, z co któ©yś raz, (chyba w więcej niż 20%
przypadków) wpada w lopkalne optimum, gdzie bardzo szybko osiąga 1
kolizję i nie chce odtąd się zmniejszyć do zera przy żadnym swapie.
Jak sobie z tym poradzić?

[Borneq]

Post by Borneq
ALE...jest to niestabilne.
to znaczy: czasami działa, z co któ©yś raz, (chyba w więcej niż 20%
przypadków) wpada w lopkalne optimum, gdzie bardzo szybko osiąga 1
kolizję i nie chce odtąd się zmniejszyć do zera przy żadnym swapie.
Jak sobie z tym poradzić?

problem jest ze swapem, Podobnie jak w układance, gdzie przesuwało się
klocki, z 15 polami i jednym pustym.Mogło być jakies ustawienie
poczatkowe niemożliwe.
Jakie operacje można wykonać jeszcze oprócz swap? rotację trzech
wierszy? a może odwrócić wszystkie - w odwrotną kolejność? a może nie :
zamiast tego 0->1, 1->2. 2->3...
tylko wtedy wzrośnie ilość kolizji, trzeba by zrobić tak, gdy bardzo
długo utknie na małej liczbie kolizji - czy zawsze może utknąć na 1 czy
czasem na więksej ilości?

[Borneq]

Post by Borneq
zamiast tego 0->1, 1->2. 2->3...
tylko wtedy wzrośnie ilość kolizji, trzeba by zrobić tak, gdy bardzo

co jakiś czas popycham rotacją, wtedy gdy nie zmniejsza się ilość
kolizji przez 10*N (doświadczalnie) gdzie N ilość hetmanów

[Borneq]

Post by Borneq
co jakiś czas popycham rotacją, wtedy gdy nie zmniejsza się ilość
kolizji przez 10*N (doświadczalnie) gdzie N ilość hetmanów

A czy coś takiego miałoby szansę powodzenia:
zmaiast szukać np. 100 hetmanów od razu
wkładam 50 hetmanów na pole 100x100, bardzo łatwo unikać kolizji, dodaję
jeden, wstawiam losowo, potem unikam kolizji , wstawiam drugi, itd. czy
to będzie szybsze dla rozmiaru 1000, zwłaszcza dla trudniejszego
problemu - unikania dowlnych linii?

[Borneq]

Post by Borneq
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?