A.L. pisze:
> On Sun, 05 Apr 2009 20:35:22 +0200, Jacek Czerwinski <...@...z.pl> wrote:
>
>> Sprowadźmy to do komiwojażera: nie chodzi o najlepsza ścieżkę lecz o
>> jakąkolwiek ścieżkę. To O(n) jest chyba wykładnicze, a może już kwadratowe
>>
>
> 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.

--
Pozdrawiam
Michoo