eGospodarka.pl

eGospodarka.plGrupypl.comp.programming › N-Queens Problem - lokalne optimum
Ilość wypowiedzi w tym wątku: 5

  • 1. Data: 2020-08-22 23:15:47
    Temat: N-Queens Problem - lokalne optimum
    Od: Borneq <b...@a...hidden.pl>

    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ó(C)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ć?


  • 2. Data: 2020-08-22 23:28:32
    Temat: Re: N-Queens Problem - lokalne optimum
    Od: Borneq <b...@a...hidden.pl>

    On 8/22/20 11:15 PM, Borneq wrote:
    > ALE...jest to niestabilne.
    > to znaczy: czasami działa, z co któ(C)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?


  • 3. Data: 2020-08-23 00:52:46
    Temat: Re: N-Queens Problem - lokalne optimum
    Od: Borneq <b...@a...hidden.pl>

    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


  • 4. Data: 2020-08-25 17:33:17
    Temat: Re: N-Queens Problem - lokalne optimum
    Od: Borneq <b...@a...hidden.pl>

    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?


  • 5. Data: 2020-08-27 14:05:35
    Temat: Re: N-Queens Problem - lokalne optimum
    Od: Borneq <b...@a...hidden.pl>

    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?

strony : [ 1 ]



Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: