Heuristics and approximation algorithms in asymmetric traveling salesman problem.

Asymmetric traveling salesman problem is about finding minimum weighted Hamiltonian Cycle in full directed graph.Problem is NP-complete so probably there is not polynomial algorithm solving it. In my work I will show and compare heuristics and approximation algorithms for this problem.

Asymetryczny problem komiwojażera polega na znalezieniu minimalnego cy-klu Hamiltona w pełnym skierowanym grafie ważonym. Problem jest NP-zupełny, więc najprawdopodobniej nie istnieje algorytm znajdujący opty-malne rozwiązanie w czasie wielomianowym. Praca ma na celu pokazaniei porównanie podstawowych heurystyk i algorytmów apoksymacyjnych roz-wiązujących wyżej sformułowany problem.