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 ]