Mengapa TSP tidak membutuhkan pengulangan kota?

9

Tampaknya aneh bagi saya bahwa TSP menyangkal kemungkinan kota yang berulang. Tujuan dari penjual keliling ini adalah untuk pergi secepat mungkin dan mengunjungi semua kota, bukan? Jadi bagaimana jika lebih cepat melakukan perjalanan melalui kota yang sudah pernah Anda kunjungi?

terminology traveling-salesman danmcardle
sumber

2

Saya yakin itu sewenang-wenang. Hanya dalam kasus yang jarang terjadi, mengizinkan kota yang berulang akan membuat perbedaan (tidak pernah dalam metrik TSP). Jadi masalahnya hampir tidak berbeda. Alasannya mungkin bersejarah.

Karolis Juodelė

8

Saya mendengar penjual menjual produk yang benar-benar buruk dan tidak bijaksana untuk bertemu dengan pelanggan lamanya :)

ssch

3

Tidak masalah bagaimana Anda mendefinisikannya karena itu hanya cara memodelkan masalah dunia nyata. Di TSP, Anda hanya memiliki satu set kota dan biaya perjalanan antara masing-masing pasangan. Itu tidak mengesampingkan kemungkinan bahwa, dalam situasi dunia nyata yang Anda modelkan, rute terbaik antara B dan C mungkin melalui A. Jika demikian, maka, rute yang dimodelkan sebagai ABCA di TSP mungkin sangat baik benar-benar melibatkan mengemudi melalui waktu tambahan dalam perjalanan dari B ke C tetapi detail tersebut disarikan dalam model TSP.

David Richerby
sumber

1

Poin yang valid, tetapi saya ingin menunjukkan bahwa TSP sering digunakan dalam situasi dunia nyata. Apakah persyaratan tanpa pengulangan diampuni saat menerapkan aplikasi dunia nyata?

danmcardle

@danmcardle Tergantung pada aplikasi.

Tom van der Zanden

2

Saya setuju bahwa batasannya terlihat aneh, dan untuk banyak situasi praktis, itu tidak relevan. Seperti yang ditunjukkan oleh David dalam jawabannya, jika Anda dapat mengubah pemodelan sendiri, maka itu tidak terlalu penting. Tetapi dengan memberikan contoh yang tidak dapat dimodifikasi, itu akan membuat perbedaan, karena TSP umum dengan kendala ini tidak dapat diperkirakan dalam faktor konstan, sementara mengendurkan kendala kunjungan-tunggal tampaknya membuatnya dapat diperkirakan dalam faktor 2 (meskipun bukan metrik ). Kecuali jika saya melewatkan sesuatu, dengan argumen standar, Anda dapat membangun pohon spanning minimum (biaya katakanlah ), kemudian mengunjungi pohon ini dengan teknik tur euler. Jelas, total biaya tur Anda adalah (dua kali setiap sisi). Secara kontradiksi, jika ada tur biaya kurang dari $c$ $2 c$ $c$ , maka tur ini dapat digunakan untuk menyimpulkan MST dengan biaya kurang dari , yang merupakan kontradiksi. $c$

Arnaud Casteigts
sumber

1

Diberikan tur apa pun dengan pengulangan, Anda bisa membuat tur pendek yang tidak mengulangi kota mana pun. Misalnya, perhatikan tur formulir yang mengunjungi dua kali. Anda dapat mengambil jalan pintas pada kunjungan kedua ke , langsung dari ke :

\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,$

A

$A$

A

$A$

X

$X$

Y

$Y$

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

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

Mungkin bahwa jalan terpendek dari ke melewati , tapi yang sudah dirumuskan dalam tepi . Anda bisa memikirkan menyebutkan bukan sebagai "melewati" melainkan "berhenti di" . Anda hanya perlu berhenti di sekali, meskipun Anda mungkin melewati beberapa kali. $X$ $Y$ $A$ $X \to Y$ $A$ $A$ $A$ $A$ $A$

Algoritma aktual untuk TSP dapat memiliki langkah "mengambil jalan pintas", misalnya algoritma Christofides. Lihat misalnya deskripsi ini atau akun yang lebih pendek itu .

Yuval Filmus
sumber

4

Anda mengasumsikan TSP metrik (yaitu ketimpangan segitiga berlaku). Namun, TSP umum tidak memiliki ketimpangan segitiga. Misalnya, Anda dapat memiliki kota

, di mana

dan

untuk semua

. Tur terpendek dengan pengulangan adalah

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

$A, X_1, \dots, X_n$

d (A, X_{i}) = 1

$d(A, X_i)=1$

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

$d(x_i,x_j)=100$

i, j

$i, j$

, dengan biaya

tapi tur singkat tanpa pengulangan adalah

, dengan biaya

.

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

$AX_1AX_2A\dots AX_nA$

2 n + 1

$2n+1$

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

$AX_1\dots X_nA$

100 n - 98

$100n-98$

David Richerby

Tentu saja, tetapi (1) OP tampaknya tertarik pada aplikasi TSP dunia nyata, yang merupakan metrik, dan (2) TSP non-metrik tidak semenarik (karena terlalu sulit).

Yuval Filmus

2

@YuvalFilmus TSP dunia nyata tidak diperlukan metrik. Beberapa kali bepergian dari A ke B akan memakan waktu lebih lama dari AC + CB karena ada lalu lintas di jalan dari A ke B.

Ilya Gazman

1

@Babibu Jarak di tepi

adalah terpendek jarak dari

ke

. Dalam kasus Anda, jalan langsung dari

ke

bukan jarak terdekat.

(A, B)

$(A,B)$

A

$A$

B

$B$

A

$A$

B

$B$

Yuval Filmus

0

Tidak ada jawaban umum untuk ini, kecuali "orang tidak bodoh." Mereka akan menerapkan solusi yang sesuai dengan situasi mereka. Jarang ada orang yang peduli dengan masalah tenaga penjual keliling itu sendiri. Pada contoh klasik, tenaga penjual dunia nyata akan lebih peduli dengan masalah memaksimalkan pendapatan mereka selama periode waktu tertentu dalam serangkaian kendala tertentu. Dalam contoh masalah ini, jarak total yang ditempuh hanya satu dari sejumlah faktor berbeda yang digunakan untuk menemukan jawaban optimal.

J. Antonio Perez
sumber

0

Jika pengulangan diizinkan, maka Anda cukup memeriksa semua koneksi X -> A -> Y, dan jika itu lebih pendek dari X -> Y maka Anda mengganti panjang X -> Y dengan panjang X -> A -> Y, dan selesaikan masalah yang dihasilkan dengan algoritma standar. Saya pikir Anda harus mengulangi proses penggantian sampai tidak ada perubahan, karena jika Anda menemukan koneksi yang lebih pendek X -> Y ini mungkin berarti bahwa sekarang X -> Y -> Z lebih pendek dari X -> Y.

Pantau koneksi mana yang Anda ubah, periksa koneksi dalam solusi, dan jika solusi tersebut berisi X -> Y, maka Anda ganti ini dengan X -> A -> Y.

PS. Saya pikir ide saya bagus, tetapi saya tidak begitu yakin saat ini bahwa itu benar. Karena X -> A -> Y bukan X -> Y bukan hanya jalan pintas, itu juga mencakup kota A.

gnasher729
sumber

Mengapa TSP tidak membutuhkan pengulangan kota?

Jawaban: