Jaka jest różnica między traveling-salesman problem i chinese postman problem? Dla mnie oboje chcą iść do miejsca docelowego, a następnie z powrotem.Jaka jest różnica między podróżującym sprzedawcą a chińskim podróżowaniem?
Podróżujący sprzedawca ma zamiar udać się do każdego miasta raz i wybrać najkrótszą trasę.
Problem listonosza chińskiego polega na uzyskaniu ścieżki z każdego miasta do drugiego miasta.
E.g. z punktów A, B, C i D komiwojażera może pójść ABCDA ale chiński listonosz pójdzie trzeba trasę, która miała AB i AC i AD itd
przebycie trasy sprzedawca nie posiada bezpośredni pomiędzy każdym punktem (w powyższym przykładzie nie ma połączenia AC).
Edycja:
Każdy miasta wierzchołkiem i każde połączenie między miastami jest krawędzią. Tak, myślę, że właśnie powtarzam odpowiedź @odarapa.
Z krótkim odczytu z dwóch artykułów (i nigdy nie wziąłem kurs teorii grafów, więc mogę mówić przez mój kapelusz), wydaje się, że "CPP" obejmuje odwiedzanie wszystkich krawędzi, a "TSP" obejmuje odwiedzanie wszystkich węzłów.
BTW: 30 sekund od Google. Może powinieneś był tego spróbować zanim zapytałeś. –
, więc dlaczego nie chcesz mi powiedzieć, że to różnica? To trudne. – Seva
Dlaczego nie czytasz dwóch oferowanych linków i samemu nie widzisz? –
Myślę, że to po prostu kolejna odmiana problematyki ścieżki przedstawionej na kursach college'u comp sci.
Chiński problem z podróżującym sprzedawcą (C-TSP) jest typowym problemem symetrycznego TSP. Jego prosty opis to: Biorąc pod uwagę listę 31 chińskich stolic i ich odległości parami, zadaniem jest znalezienie najkrótszej możliwej trasy, która odwiedza każde miasto dokładnie raz. C-TSP jest średnim problemem o numerze TAL , który ma (31-1)!/2 = 1.326 * 1032 możliwych tras.
Wykresy są wykonane z krawędzi i wierzchołków. CPP wymaga wizyty na wszystkich krawędziach. TSP wymaga wizyty we wszystkich wierzchołkach.
czekaj, myślę, że to jest opozycyjny o.O Wiem, że chiński = hamilton i listonosz = Euler. – Seva
@Alan: Ścieżka hamiltonowska to taka, która odwiedza wszystkie * wierzchołki *. Eulerian odwiedza wszystkie krawędzie. Nie jestem pewien, jaka jest twoja równowaga (ponieważ wydajesz się podawać dwie definicje dla CPP), ale jest to poprawna różnica między CPP i TSP. – Xodarap
Dowiedziałem się, że najłatwiejszym sposobem na rozwiązanie chińskiego jest hamilton, a drugi eulerem. – Seva
Kluczową różnicą między nimi jest:
komiwojażera problem nie może odwiedzić węzeł więcej niż jeden raz. Wytworzona ścieżka składa się ze wszystkich różnych węzłów/miast.
Problemy z chińską listonoszem/inspekcją trasy mogą mieć zduplikowane węzły w utworzonej ścieżce (ale nie duplikaty krawędzi). To znaczy. węzły mogą być odwiedzane częściej niż raz tak długo, jak podjąć inną drogę na zewnątrz niż wziąłeś w
problem komiwojażera. Biorąc pod uwagę miasta i odległość między miastami, znalezienie najkrótszej trasy odległości tak, że odwiedza każde miasto dokładnie jeden. Wizualizując to jako wykres i koszt lub wagę związaną z każdą krawędzią, znajdź najtańszą lub najmniej ważoną trasę (ścieżkę Hamiltona), tak aby każdy wierzchołek lub węzeł był odwiedzany dokładnie raz. Możemy myśleć o tym jako o znalezieniu wszystkich możliwych ścieżek Hamiltona, a następnie znaleźć najlepsze z nich.Znalezienie wszystkich możliwych tras jest problem optymalizacji i w NP - Cała oznacza brak wielomian rozwiązanie czas istnieje dla tego problemu
chiński listonosz Problem: Wbrew problem komiwojażera, CPP wymaga, aby znaleźć jak najmniejszym koszcie lub minimalną wycieczkę wagi przez wykres tak, że każda krawędź jest odwiedzana co najmniej raz. Problem polega na rozwiązaniu wielomianu, a optymalne rozwiązanie wymaga znalezienia trasy Eulera przez wykres, jeśli wykres jest Eulerianem. W przeciwnym razie zmodyfikuj wykres, aby był bardziej euleryński i zdefiniuj trasę Eulera. Szczególną instancją problemu chińskiego listonosza jest to, że nie musimy podróżować wszystkimi krawędziami wykresu, ale tylko niektóre z nich (wymagane krawędzie). Ta odmiana nazywa się Problem wiejski listonosz i jest NP-zupełny. Innymi słowy, biorąc pod uwagę wykres, znajdź trasę o najmniejszym koszcie/minimalnym ciężarze tak, aby wszystkie wymagane krawędzie były co najmniej raz pokryte, mogą wykorzystywać niezbędne krawędzie.
Mając to bardzo prosta:
problem komiwojażera jest o pójściu do każdego miasta dokładnie raz wracając do pierwotnego miasta (a więc szedł Hamiltonian cycle), a także biorąc najkrótszą trasą między ogóle możliwe trasy spełniające to kryterium (jeżeli taka trasa istnieje). Znalezienie takiego cyklu, z konieczności znalezienia możliwie unikalnego optymalnego cyklu z najkrótszą odległością, jest "trudne".
chiński listonosz Problem lub Route Inspekcja Problem jest o odwiedzenie każdą trasę między miastami przynajmniej raz podczas powrotu do pierwotnego miasta i wybrał najkrótszą trasę spośród wszystkich możliwych tras, które spełniają tę criterium (jeśli taka trasa istnieje). Rozwiązanie, które automatycznie wykonuje każdą trasę, jest automatycznie optymalne i nazywa się Eulerian Cycle. Znalezienie takiego cyklu jest "wykonalne".
http://wiki.answers.com/Q/What_are_the_differences_between_chinese_postman_problem_and_travelling_salesman_problem –
to dobry artykuł: http://faculty.bracu.ac.bd/~rouf/course/summer06/cse426/TSP_CPP.pdf –