80266 IMG968 (5)

•    po wyborze 1 krawędzi pozostaje 8,...7,...6,....

•    w efekcie otrzymujemy LH=9*8*7*6*5*4*3*2*1=9I 'Złożoność obliczeniowa równa O(nl)

•    dla każdego znalezionego cyklu Hammiltona liczymy sumę wag krawędzi i zapamiętujemy cykl o najmniejszej sumie wag

Przykład 2.

Gaf ma 100 wierzchołków

•    każdy wierzchołek łączy się z czterem innymi wierzchołkami grafu zatem ilość stopni. Z jednego wierzchołka możemy Iść na cztery różne sposoby, z drugiego na 3 a 98 na 3. Z czego wynika LH=4*3^A99

Zatem graf LH w przybliżeniu (S-l)^An

Podsumowanie:

•    liczba cykli lub ścieżek do przechodzenia rośnie wykładniczo

•    duże wartości mogą być rozwiązywane przez stulecia

•    istnieją algorytmy o zbliżonych rozwiązaniach ale są trudne w implementacji

ALGORYTMY GENETYCZNE :

ALGORYTMY GENETYCZNE SŁUŻĄ do optymalizacji zadań.

Optymalizacja jest to wyznaczanie sposobów dopuszczalnych rozwiązań najlepszego ze względu na przyjęte kryterium.

- Metoda ukierunkowanego przeszukiwanie optymaInegojżródłem problemeu głównie są ekstrema lokalne)

- Metoda przypadkowego przeszukiwania

Funkcja Rastragina obrazuje trudności jakie można napotkać przy poszukiwaniu optimum.

Od problemu minimów lokalnych wolne są propabilistycznie metody optymalizacji.

Stochastyczne przeszukiwanie rozwiązań nie gwarantuje sukcesu.

Metody wyspecjalizowane są dobre przy specyficznych cechach zadania.

Na bazie tych obserwacji, powstała koncepcja żeby przeszukiwaniami optymalnego rozwiązania uzyskanego za pomocą komputera kierował proces ewolucji.

Obliczenia ewolucyjne - algorytmy genetyczne, programowanie ewolucyjne, strategie ewolucyjne.