Dlaczego TSP nie wymaga powtarzania miast?

9

Wydaje mi się dziwne, że TSP zaprzecza możliwości powtarzania się miast. Celem tego podróżującego sprzedawcy jest pójść jak najszybciej i odwiedzić wszystkie miasta, prawda? Co jeśli szybsze jest podróżowanie przez miasto, w którym już byłeś?

terminology traveling-salesman Danmcardle
źródło

2

Jestem pewien, że to arbitralne. Tylko w rzadkich przypadkach zezwolenie na powtarzanie się miast robiło różnicę (nigdy w metrycznym TSP). Więc problemy nie są prawie inne. Powód jest prawdopodobnie historyczny.

Karolis Juodelė

8

Słyszałem, że sprzedawca sprzedaje naprawdę złe produkty i niemądrze byłoby spotkać jego starych klientów :)

ssch

3

Nie ma znaczenia dokładnie, jak go zdefiniujesz, ponieważ jest to tylko sposób modelowania rzeczywistego problemu. W TSP masz po prostu zestaw miast i koszty podróży między nimi. Nie wyklucza to możliwości, że w rzeczywistej sytuacji, w której modelujesz, najlepsza trasa między B i C może przebiegać przez A. Jeśli tak, to tak, trasa modelowana jako ABCA w TSP może bardzo dobrze naprawdę wiąże się z przejechaniem dodatkowego czasu A w drodze z B do C, ale takie szczegóły są wyabstrahowane w modelu TSP.

David Richerby
źródło

1

Ważny punkt, ale chciałbym zauważyć, że TSP jest często używany w rzeczywistych sytuacjach. Czy przy wdrażaniu aplikacji w świecie rzeczywistym zapomina się o wymogu braku powtórzeń?

danmcardle,

@danmcardle To zależy od aplikacji.

Tom van der Zanden

2

Zgadzam się, że ograniczenie wygląda dziwnie i w wielu praktycznych sytuacjach nie ma znaczenia. Jak zauważył David w swojej odpowiedzi, jeśli możesz sam zmienić modelowanie, to tak naprawdę nie ma to znaczenia. Ale biorąc pod uwagę niemodyfikowalną instancję, zrobi to różnicę, ponieważ ogólny TSP z tym ograniczeniem nie jest możliwy do przybliżenia w ramach żadnego stałego czynnika, podczas gdy rozluźnienie ograniczenia pojedynczej wizyty wydaje się przybliżać w ramach współczynnika 2 (nawet jeśli nie jest metryczny ). O ile mi coś nie umknie, za pomocą standardowych argumentów możesz najpierw zbudować drzewo rozpinające o minimalnym rozmiarze (na przykład koszt $c$ ), a następnie odwiedź to drzewo za pomocą techniki euler tour. Oczywiście całkowity koszt wycieczki jest wtedy $2 c$ (dwa razy na każdej krawędzi). Przeciwnie, jeśli istniała wycieczka o koszcie mniejszym niż $c$ , to ta trasa może być wykorzystana do ustalenia MST kosztu mniejszego niż $c$ , co jest sprzecznością.

Arnaud Casteigts
źródło

1

Biorąc pod uwagę każdą trasę z powtórzeniami, możesz wymyślić krótszą trasę, która nie powtórzy żadnego miasta. Rozważmy na przykład prezentację formularza

\dots \to A \to \dots \to X \to A \to Y \to \dots,

$\cdots \to A \to \cdots \to X \to A \to Y \to \cdots,$ które wizyty

A

$A$ dwa razy. Możesz skorzystać ze skrótu podczas drugiej wizyty w

A

$A$ , jadąc prosto z

X

$X$ do

Y

$Y$ :

\dots \to A \to \dots \to X \to Y \to \dots .

$\cdots \to A \to \cdots \to X \to Y \to \cdots.$

Może to być najkrótsza droga $X$ do $Y$ przechodzi przez $A$ , ale jest to już zamknięte w krawędzi $X \to Y$ . Możesz wymyślić wzmiankę o $A$ nie jako „przechodzenie” $A$ ale raczej „zatrzymanie się” $A$ . Musisz tylko zatrzymać się na $A$ raz, choć możesz przejść $A$ kilka razy.

Rzeczywiste algorytmy dla TSP mogłyby mieć ten etap „przyjmowania skrótów”, na przykład algorytm Christofidesa. Zobacz na przykład ten opis lub to krótsze konto .

Yuval Filmus
źródło

4

Zakładasz metryczny TSP (tzn. Że utrzymuje się nierówność trójkąta). Jednak ogólny TSP nie ma nierówności trójkąta. Na przykład możesz mieć miasta

A, X_{1}, \dots, X_{n}

$A, X_1, \dots, X_n$ , gdzie

d (A, X_{i}) = 1

$d(A, X_i)=1$ i

d (x_{i}, x_{j}) = 100

$d(x_i,x_j)=100$ dla wszystkich

i, j

$i, j$ . Najkrótsza trasa z powtórzeniami to

A X_{1} A X_{2} A \dots A X_{n} A

$AX_1AX_2A\dots AX_nA$ , z kosztami

2 n + 1

$2n+1$ ale najkrótsza trasa bez powtórzeń to

A X_{1} \dots X_{n} A

$AX_1\dots X_nA$ , z kosztami

100 n - 98

$100n-98$ .

David Richerby,

Oczywiście, ale (1) OP wydaje się zainteresowany rzeczywistymi zastosowaniami TSP, które są metryczne, i (2) niemetryczny TSP nie jest tak interesujący (ponieważ jest zbyt trudny).

Yuval Filmus,

2

@ YuvalFilmus świat rzeczywisty TSP nie jest konieczny. Czasami podróż z A do B potrwa dłużej niż AC + CB, ponieważ na drodze z A do B. jest ruch

Ilya Gazman

1

@Babibu Odległość na krawędzi

(A, B)

$(A,B)$ to najkrótsza odległość od

A

$A$ do

B

$B$ . W twoim przypadku bezpośrednia droga z

A

$A$ do

B

$B$ nie jest najkrótszą odległością.

Yuval Filmus,

0

Nie ma na to ogólnej odpowiedzi, z wyjątkiem „ludzie nie są głupi”. Zastosują rozwiązanie odpowiednie do ich sytuacji. Rzadko ludzie są zainteresowani samym problemem sprzedawcy w podróży. W klasycznym przypadku, sprzedawca z prawdziwego świata byłby bardziej zainteresowany problemem maksymalizacji dochodów w danym okresie w ramach określonego zestawu ograniczeń. W tym przypadku problemu całkowity przebyty dystans jest tylko jednym z wielu różnych czynników, które wpływają na znalezienie optymalnej odpowiedzi.

J. Antonio Perez
źródło

0

Jeśli dozwolone są powtórzenia, po prostu przejrzyj wszystkie połączenia X -> A -> Y, a jeśli jest on krótszy niż X -> Y, to zamień długość X -> Y na długość X -> A -> Y i rozwiązuj powstały problem za pomocą standardowego algorytmu. Myślę, że musisz powtarzać proces wymiany, dopóki nie zostaną wprowadzone żadne zmiany, ponieważ jeśli znajdziesz krótsze połączenie X -> Y, może to oznaczać, że teraz X -> Y -> Z jest krótszy niż X -> Y.

Śledź, które połączenia zostały zmienione, przejrzyj połączenia w rozwiązaniu, a jeśli rozwiązanie zawiera X -> Y, zamień to na X -> A -> Y.

PS. Myślę, że mój pomysł jest świetny, ale w tej chwili nie jestem pewien, czy jest poprawny. Ponieważ X -> A -> Y zamiast X -> Y to nie tylko skrót, obejmuje także miasto A.

gnasher729
źródło

Dlaczego TSP nie wymaga powtarzania miast?

Odpowiedzi: