Article View: pl.comp.programming
Article #217127Re: N-Queens Problem - lokalne optimum
From: 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?
Technical Details
Message-ID:
<5f47a18f$0$552$65785112@news.neostrada.pl>Path:
mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!3.eu.feeder.erje.net!feeder.erje.net!weretis.net!feeder8.news.weretis.net!news.mixmin.net!aioe.org!peer03.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!newsfeed.neostrada.pl!unt-exc-01.news.neostrada.pl!unt-spo-a-01.news.neostrada.pl!news.neostrada.pl.POSTED!not-for-mailReferences:
<5f418b03$0$17346$65785112@news.neostrada.pl> <5f418e00$0$554$65785112@news.neostrada.pl> <5f41a1be$0$511$65785112@news.neostrada.pl> <5f452f3d$0$543$65785112@news.neostrada.pl>Show Full Headers
Complete Article Headers
Path: mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!3.eu.feeder.erje.net!feeder.erje.net!weretis.net!feeder8.news.weretis.net!news.mixmin.net!aioe.org!peer03.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!newsfeed.neostrada.pl!unt-exc-01.news.neostrada.pl!unt-spo-a-01.news.neostrada.pl!news.neostrada.pl.POSTED!not-for-mail Subject: Re: N-Queens Problem - lokalne optimum Newsgroups: pl.comp.programming References: <5f418b03$0$17346$65785112@news.neostrada.pl> <5f418e00$0$554$65785112@news.neostrada.pl> <5f41a1be$0$511$65785112@news.neostrada.pl> <5f452f3d$0$543$65785112@news.neostrada.pl> From: Borneq <borneq@antyspam.hidden.pl> Date: Thu, 27 Aug 2020 14:05:35 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.10.0 MIME-Version: 1.0 In-Reply-To: <5f452f3d$0$543$65785112@news.neostrada.pl> Lines: 16 Message-ID: <5f47a18f$0$552$65785112@news.neostrada.pl> Organization: Telekomunikacja Polska NNTP-Posting-Host: 37.225.14.151 X-Trace: 1598529935 unt-rea-a-02.news.neostrada.pl 552 37.225.14.151:19201 X-Complaints-To: abuse@news.neostrada.pl X-Received-Bytes: 1938 X-Received-Body-CRC: 3018454988 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit