Cykl Hamiltona: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
poprawione linki na przekierowania: Wierzchołek grafu na Graf (matematyka) |
przesunięcie |
||
Linia 1:
'''Cykl Hamiltona''' to taki [[cykl]] w [[graf (matematyka)|graf]]ie, w którym każdy [[Graf (matematyka)|wierzchołek grafu]] występuje dokładnie jeden raz. Znalezienie cyklu Hamiltona o minimalnej sumie wag krawędzi jest równoważne rozwiązaniu [[problem komiwojażera|problemu komiwojażera]]. Grafy zawierające cykl Hamiltona nazywamy [[graf Hamiltonowski|hamiltonowskimi]].
Nie są znane algorytmy dające dokładne rozwiązanie problemu znajdowania cyklu Hamiltona w czasie wielomianowym. W praktyce najefektywniejszymi sposobami jego rozwiązania są [[algorytm genetyczny|algorytmy genetyczne]], często wykorzystywane w połączeniu z [[heurystyka|heurystycznymi]] (np. heurystyka najbliższego sąsiada). Są to jednak metody dające w większości jedynie rozwiązania bliskie optymalnemu. Niekiedy tylko zdarza się, że otrzymane rozwiązanie jest optymalne. Zależy to głównie od ilości punktów oraz czasem ''szczęścia'' (generacja populacji początkowej, krzyżowanie oraz mutacja w algorytmach genetycznych zawierają element losowy).
Zobacz też: [[cykl Eulera]], [[problem komiwojażera]], [[algorytm najbliższego sąsiada]]
| |||