Thread View: pl.comp.programming
5 messages
5 total messages
Started by Borneq
Sat, 22 Aug 2020 21:15
N-Queens Problem - lokalne optimum
Author: Borneq
Date: Sat, 22 Aug 2020 21:15
Date: Sat, 22 Aug 2020 21:15
14 lines
1741 bytes
1741 bytes
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ć?
Re: N-Queens Problem - lokalne optimum
Author: Borneq
Date: Sat, 22 Aug 2020 21:28
Date: Sat, 22 Aug 2020 21:28
16 lines
2023 bytes
2023 bytes
On 8/22/20 11:15 PM, Borneq wrote: > 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?
Re: N-Queens Problem - lokalne optimum
Author: Borneq
Date: Sat, 22 Aug 2020 22:52
Date: Sat, 22 Aug 2020 22:52
7 lines
1571 bytes
1571 bytes
On 8/22/20 11:28 PM, Borneq wrote: > 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 co jakiś czas popycham rotacją, wtedy gdy nie zmniejsza się ilość kolizji przez 10*N (doświadczalnie) gdzie N ilość hetmanów
Re: N-Queens Problem - lokalne optimum
Author: Borneq
Date: Tue, 25 Aug 2020 15:33
Date: Tue, 25 Aug 2020 15:33
10 lines
1733 bytes
1733 bytes
On 8/23/20 12:52 AM, Borneq wrote: > 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?
Re: N-Queens Problem - lokalne optimum
Author: Borneq
Date: Thu, 27 Aug 2020 12:05
Date: Thu, 27 Aug 2020 12:05
16 lines
2173 bytes
2173 bytes
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?
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads