Traveling Salesman Problem and its variants

Poszukiwanie najkrótszej drogi to tzw. problem komiwojażera. Nazwa tegozagadnienia pochodzi z życiowej sytuacji, przedstawiającej wędrownegosprzedawce (komiwojażera), który musi odwiedzić pewna ilość miast w najkrótszymczasie. Najkrótsza trasa często jest zamieniana na najtańsza lubnajszybsza, w zależności od problemu.Poniższa praca rozpoczyna sie krótkim wstępem, wprowadzającym w teorięgrafów, zawierającym definicje i własności. Na wstępie została przedstawionadefinicja grafu, jego właściwości i rodzaje poparte przykładami. Jedenpodrozdział został poświęcony tematowi trasy, rodzajów trasy i różnicy międzynimi. Osobno została pokrótce przedstawiona teoria związana z grafamihamiltonowskimi.Po wstępie teoretycznym został przedstawiony główny punkt pracy: ProblemKomiwojażera, w postaci ogólnej i tradycyjnej. Zostało przedstawione przejście z uogólnionego problemu komiwojażerana tradycyjny, ułatwiające w ten sposób analizę problemu. Przedstawionyw artykule dowód został dokładniej rozpisany i uzupełniony. Kolejne etapyprzejścia zostały poparte obrazkami, które ułatwiają zrozumienie schematui zasady jego działania.Na koniec pracy zostały omówione dwa warianty problemu komiwojażera.Pierwszy dotyczy problemu komiwojażera z ruchomymi celami. Zostałprzedstawiony algorytm wyznaczania trasy oraz czas na jego przeprowadzenie. Drugi wariant dotyczy problemu dla n dowolnie nachylonych linii. Problem polega na wyznaczeniutrasy, która odwiedza wszystkie podane linie na płaszczyźnie. Zostałoprzedstawione zagadnienie tego problemu oraz wnioski.

The search for the shortest path is called traveling salesman problem. The name of theproblem comes from the life situation, presenting a traveling salesmen who has to visit a number of cities in the shortest time. The shortest route is often the cheapest, or converted to quickest, depending on the problem.This paper begins with a brief introduction, introducing the theorygraphs, containing definitions and properties. At the outset has been presenteddefinition of the graph, its characteristics and types supported by examples. onesection is devoted to the theme of the route, type of route, and the difference between them. Was briefly presented separately theory associated with Hamilotonowskie graphs.After a theoretical introduction was made chief operating point: ProblemSalesman, in the form of general and traditional. Was presented the transition from a generalized traveling salesman problem the traditional, thus facilitating the analysis of the problem. Presented evidence in the article was written down and completed accurately. Next Steps transitions are supported by images that make it easier to understand the scheme and principles of its operation.At the end of the work are presented two variants of the traveling salesman problem.The first relates to the traveling salesman problem with moving targets. Waspresented routing algorithm and the time of his conduct. The second option concerns the problem for n arbitrarily sloping line. The problem consists in determiningtour that visits all of the lines on the plane. Was issue of this problem and applications.