A.L. wrote:
> 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?...

Tu:
http://groups.google.pl/group/pl.comp.programming/ms
g/154593d9ef569106

"Droki Kolego, problemy NO-completne maja to do siebie ze petelkami sie
ich nei rozwiaze." (pisownia oryginalna)

--
Paweł Kierski
n...@p...net