On Mon, 06 Apr 2009 23:29:01 +0200, Michoo <m...@v...pl> wrote:

>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.

Czy ja gdzies pisalem ze nie?...

A.L.