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.

http://en.wikipedia.org/wiki/Hamiltonian_path_proble
m

A.L.