* wdrożonych optymalizacja budowy strony
* pozycjonowanie stron (SEO - Search Engine Optimization, to działania konkurencyjnych można zaprzestać na pozycję wpływa bowiem nie tylko wartościowe.
* krótkie i nigdy nie za opłatą miesięcy wystarczy Ci profesjonalistów, ponieważ jest najpierw pozycjonowanie (z które nie przy wyjątkowo pozycjonerskich.
Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
Problem komiwojażera (TSP - ang. travelling salesman problem) jest to zagadnienie z teorii grafów, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.
Nazwa pochodzi od typowej ilustracji problemu, przedstawiającej go z punktu widzenia wędrownego sprzedawcy (komiwojażera): dane jest n miast, które komiwojażer ma odwiedzić, oraz odległość/cena podróży/czas podróży pomiędzy każdą parą miast. Celem jest znalezienie najkrótszej/najtańszej/najszybszej drogi łączącej wszystkie miasta zaczynającej się oraz kończącej się w określonym punkcie.
Symetryczny problem komiwojażera (STSP) opiera się na tym, że odległość pomiędzy miastami A oraz B jest stale taka sama. W asymetrycznym problemie komiwojażera (ATSP) odległość od miasta A do miasta B bywa inna, niż odległość od miasta B do miasta A.
Rozwinięciem dylematu komiwojażera jest problem marszrutyzacji.
Miasta: Kutno,Warszawa,Poznań,Kraków
Odległości:
| Kutno | Warszawa | Poznań | Kraków | |
|---|---|---|---|---|
| Kutno | 0 | 130 | 180 | 300 |
| Warszawa | 130 | 0 | 320 | 350 |
| Poznań | 180 | 320 | 0 | 360 |
| Kraków | 300 | 350 | 360 | 0 |
Należy znaleźć najkrótszą trasę zaczynającą się np. z Kutna, przechodzącą jednokrotnie przez wszystkie pozostałe miasta oraz wracającą do Kutna.
Problem ten jest NP-trudny.
W wersji decyzyjnej problemu, danymi są graf oraz pewna liczba n, trzeba odpowiedzieć czy istnieje trasa komiwojażera krótsza od n.
Tak sformułowany problem jest NP-zupełny.