Odp: Problem NP na przykladzie komiwojazera

No, chyba tak.

|   Drugie pytanie -- jak na razie nie istnieje algorytm znajdujacy
| najkrotsza droge w jakims normalnym czasie.
                            ^^^^^^^^^
Chyba nie do konca tak.
Teoretycznie nalezy rozwazyc wszystkie mozliwe permutacje, a ich ilosc
rosnie baaaardzo szybko rwaz ze wzrostem liczby miast i dlatego dla
np. 100 miast nie ma to sensu.

| Powiedzmy ze mialbym 100
| miast. Jaki wynik musialbym wykrecic /znajdujac _najkrotsza_ droge/
i
| to wynik czasowo powtarzalny, aby stwierdzic, ze rozwalilem problem?

Sa inne sposoby. Np. losujesz na poczatek jakas przypadkowa kolejnosc
miast i liczysz dlugosc drogi. Potem losujesz dwa (cztery) miasta i
poddajesz operacji inwersji, wymiany lub translacji.

np.

1-2-3-4-5-6-7-8-9-10-11-12
          +-----+
inwersja (jeden odcinek odwracamy)

1-2-3-4-5-9-8-7-6-10-11-12
        +-+ +-+
translacja (dwa odcinki zamieniamy miejscami)

1-2-3-4-8-7-5-9-6-10-11-12
    +                +
wymiana (dwa miasta zamieniamy miejscami)

1-2-11-4-8-7-5-9-6-10-3-12

Operacja tez jest oczywiscie losowana w kazdym kroku (tzn. najpierw
losujesz operacje, a potem dwa lub wiecej miast).

Po kazdym kroku sprawdzasz, czy jest lepiej. Jesli nie, to cofasz
zmiane. Jesli jest poprawa, to OK.
Jezeli np. przez 100 kroków nie uzyskasz zadnej poprawy, to mozna
skonczyc.

Calosc mozna powtórzyc n razy, dla róznych ukladów poczatkowych, aby
zwiekszyc szanse dotarcia do najlepszego wyniku (lub prawie
najlepszego).

Taki algorytm jest calkiem szybki i daje zadowalajace rezultaty.

Sa inne sposoby. Np. losujesz na poczatek jakas przypadkowa kolejnosc
miast i liczysz dlugosc drogi. Potem losujesz dwa (cztery) miasta i
poddajesz operacji inwersji, wymiany lub translacji.

np.

1-2-3-4-5-6-7-8-9-10-11-12
          +-----+
inwersja (jeden odcinek odwracamy)

1-2-3-4-5-9-8-7-6-10-11-12
        +-+ +-+
translacja (dwa odcinki zamieniamy miejscami)

1-2-3-4-8-7-5-9-6-10-11-12
    +                +
wymiana (dwa miasta zamieniamy miejscami)

1-2-11-4-8-7-5-9-6-10-3-12

Operacja tez jest oczywiscie losowana w kazdym kroku (tzn. najpierw
losujesz operacje, a potem dwa lub wiecej miast).

Po kazdym kroku sprawdzasz, czy jest lepiej. Jesli nie, to cofasz
zmiane. Jesli jest poprawa, to OK.
Jezeli np. przez 100 kroków nie uzyskasz zadnej poprawy, to mozna
skonczyc.

Calosc mozna powtórzyc n razy, dla róznych ukladów poczatkowych, aby
zwiekszyc szanse dotarcia do najlepszego wyniku (lub prawie
najlepszego).

Taki algorytm jest calkiem szybki i daje zadowalajace rezultaty.

| O ile dobrze widze to jest to algorytm zachlanny i (chyba) w dodatku
| niestabilny. Nie mozesz zalozyc, ze jesli przez 100 krokow nie
uzyskasz
| poprawy, to nigdy juz jej nie uzyskasz, np. za 101 krokiem. Dziala
to
| wprawdzie dla pewnych przypadkow, ale nie mozna tego uznac za
poprawny
| algorytm. A rezultaty sa zwykle dobre albo zle. "zadowalajace"
rezultaty
| czasami moga prowadzic do katastrofy, np. jakby program do
obliczania
| trajektori pocisku kontunentalnego jako "zadowalajacy" wynik
trafienia w
| Moskwe(zalozsmy ze jest zimna wojna i USA rywalizyje z ZSRR, a
Polska jest po
| stronie czerwonych; nie bierzcie tego przykladu na serio) podal
namiary
| Warszawy, to wynik bylby "zadowalajacy" dla USA, bo w koncu to tez
panstwo
| Ukladu Warszawskiego, ale nie bardzo dla mieszkancow
Warszawy........Troche
| moze drastyczny ten przyklad, ale nic innego przez 1 min. nie moglem
| wymyslec;))).

Racja, racja. Jeśli wolisz, to licz sobie długość drogi dla wszystkich
permutacji.
Po drugie, możesz zwiększyć margines "bezpieczeństwa" i ustalić, że
dopiero po 10000 kroków bez poprawy przerywasz.
Algorytm zaiste nie daje 100% gwarancji osiągnięcia minimum, ale na
pewno jest to lepsze niż szacowanie "na oko" lub liczenie wszystkich
wariantów. Myslę, że mozna podać wiele przykładów, gdzie
"zadowalajacy" rezultat jest rzeczywiście zadowalający. Ot, choćby
prawdziwy komiwojażer. Jak to mówią: lepszy rydz niż nic.

A rezultaty sa zwykle dobre albo zle. "zadowalajace" rezultaty
czasami moga prowadzic do katastrofy,

Czasem lepiej podać zadowalający wynik w 10 minut niż czekać na
dokładny przez kilka miesięcy :-)

pozdrawiam!

obliczanie wyrazow ciagu Fibonacciego met. rekurencyjna, algorytm
ten ma podobna zlozonosc (wykladnicza)...

Jeśli we wzorze F(n) = F(n-2)+F(n-1) wywołuje funkcję dwa razy, to
owszem (i ten sam wyraz jest obliczany wiele razy), ale wystarczy
liczyć
na parze sąsiednich wyrazów: (F(n-1), F(n)) |-(F(n), F(n-1)+F(n))
(złożoność liniowa).

p.s.: dowolny wyraz ciagu Fibonacciego to i mozna w paru instrukcjach
policzyc :)

pozdrawiam!

Sa inne sposoby. Np. losujesz na poczatek jakas przypadkowa kolejnosc

milego dnia zycze
hej