-
Path: news-archive.icm.edu.pl!news.gazeta.pl!newsfeed.pionier.net.pl!news.glorb.com!p
ostnews.google.com!g37g2000yqn.googlegroups.com!not-for-mail
From: Wit Jakuczun <w...@g...com>
Newsgroups: pl.comp.programming
Subject: Re: algorytm generowania grafikow pracy
Date: Tue, 7 Apr 2009 05:55:52 -0700 (PDT)
Organization: http://groups.google.com
Lines: 41
Message-ID: <5...@g...googlegroups.com>
References: <gr5k0f$im7$1@atlantis.news.neostrada.pl> <gr5pj8$4eg$1@news.onet.pl>
<m...@4...com> <gr8ion$639$1@news.onet.pl>
<j...@4...com> <gr9k9o$rr7$1@news.onet.pl>
<q...@4...com> <gratmj$tqo$1@news.onet.pl>
<f...@4...com> <grds81$4mb$1@news.onet.pl>
NNTP-Posting-Host: 217.197.165.239
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-2
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1239108952 3735 127.0.0.1 (7 Apr 2009 12:55:52 GMT)
X-Complaints-To: g...@g...com
NNTP-Posting-Date: Tue, 7 Apr 2009 12:55:52 +0000 (UTC)
Complaints-To: g...@g...com
Injection-Info: g37g2000yqn.googlegroups.com; posting-host=217.197.165.239;
posting-account=YbmA9woAAADL-VHIckvA_tQOj4QN1bDS
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/5.0 (Windows; U; Windows NT 6.0; pl; rv:1.9.0.8)
Gecko/2009032609 Firefox/3.0.8 (.NET CLR
3.5.30729),gzip(gfe),gzip(gfe)
Xref: news-archive.icm.edu.pl pl.comp.programming:181583
[ ukryj nagłówki ]On 6 Kwi, 23:29, Michoo <m...@v...pl> wrote:
> > Tak zupelnie to nie. Jezeli mamy miasta polaczone drogami
> > niekoniecznei kazde z kazdym, to problemy poszukiwania JAKIEJKOWIEK
> > drogi przechodzacej przez wszystkie miasta, czy tez stwierdzenia czy
> > taka droga w ogole istnieje znana sa jako "problem poszukiwania
> > sciezki Hamiltonowskiej" i oba sa NP-zupelne.
>
> I mimo tego dla małych n są rozwiązywalne metodą brute-force (pytający
> pisał o *3* pracownikach). Dla większych n dostaje się całkiem
> przyzwoite wyniki w ciągu kilku minut za pomocą choćby local-search czy
> symulowanego wyżarzania.
>
Rozwiązywalność metodą brute-force jest bardzo względne.
Właśnie skończyłem projekt, gdzie algorytm brute-force (pętelki ;) )
działał około 11 wolniej niż rozwiązanie oparte na dość zaawansowanej
matematyce.
Problem nie był tak trudny obliczeniowo (chociaż złożoność reguł
była duża ) jak problem komiwojażera i wydawało się, że nic lepszego
od
brute-force'a (z prostymi optymalizacjami kodu) nie da się
zaproponować.
Chodziło o przyspiesznie obliczeń z 1 minuty do 5 sekund :). Takiej
redukcji
nie dało się zrobić zwykłymi trikami programistycznymi, także local-
search
czy symulowane wyżarzanie odpadały (nie mówiąc o innych cudach typu
algorytmy genetyczne).
Podsumowując. Wszystko jest względne i nie tylko wielkość zadania
jest ważna. Także to jakie są oczekiwania zlecającego w stosunku do
dostarczonego rozwiązania.
Pozdrawiam,
Wit [ http://wlogsolutions.pl ]
Następne wpisy z tego wątku
- 08.04.09 05:46 Jacek Czerwinski
- 08.04.09 12:54 A.L.
- 25.04.09 16:44 matmis
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-05-24 Chiński bestseller w Europie. Ford "martwi się nową konkurencją"
- 2024-05-24 Wiewiórki, szczury i myszy...
- 2024-05-24 Warszawa => QA Manager <=
- 2024-05-24 Warszawa => AI Specialist <=
- 2024-05-24 Zabrze => Analityk biznesowo-systemowy <=
- 2024-05-24 Ulm => Technischer Rollouter (d/m/w) <=
- 2024-05-24 Warszawa => Senior Rust Software Engineer <=
- 2024-05-24 Warszawa => Spedytor międzynarodowy <=
- 2024-05-24 Kraków => Head of International Freight Forwarding Department <=
- 2024-05-24 Warszawa => Senior Software Engineer PHP (BillPro) Contractor <=
- 2024-05-24 Warszawa => Senior Software Engineer PHP (BillPro) Kontraktor <=
- 2024-05-24 Warszawa => Cybersecurity Consultant <=
- 2024-05-24 Warszawa => Full Stack web developer (obszar .Net Core, Angular6+) <=
- 2024-05-24 Warszawa => React Native Developer <=
- 2024-05-24 Re: Ambasador USA zdradza: TVN Style nie jest firmą Unii Europejskiej :-)