Metody Heurystyczne i Problem Komiwojażera (TSP)

Czym jest heurystyka?

Algorytm heurystyczny (heurystyka) to metoda rozwiązywania problemów, która nie gwarantuje znalezienia rozwiązania optymalnego (najlepszego z możliwych), ale pozwala w bardzo krótkim czasie wyznaczyć rozwiązanie bliskie optymalnemu i w pełni satysfakcjonujące w praktyce inżynierskiej.

Kiedy stosuje się metody heurystyczne?

Gdy dokładne rozwiązanie problemu wymaga sprawdzenia wszystkich możliwych kombinacji (złożoność wykładnicza O(2ⁿ) lub silniowa O(n!) – problemy NP-trudne) i dla dużego n komputer liczyłby wynik przez tysiące lat.

Problem Komiwojażera (TSP - Travelling Salesperson Problem):

• Treść problemu: Komiwojażer ma odwiedzić N miast, w każdym być dokładnie jeden raz i powrócić do miasta startowego, pokonując przy tym jak najkrótszą łączną drogę.
• Złożoność dokładna (Brute-Force): Wymaga sprawdzenia ((N-1)! / 2) tras (O(N!)) – dla 30 miast jest to niewykonalne obliczeniowo.
• Rozwiązanie heurystyczne (np. Algorytm Najbliższego Sąsiada - zachłanny): W każdym kroku komiwojażer wybiera najbliższe jeszcze nieodwiedzone miasto. Złożoność spada do O(N²), dając trasę nieco dłuższą od idealnej, ale wyznaczoną w ułamku sekundy.

Pułapki na egzaminie INF.04:

• Metoda heurystyczna nie daje gwarancji znalezienia rozwiązania optymalnego, lecz rozwiązanie przybliżone w rozsądnym czasie.