Seyahat eden satıcı ve Çin seyahatleri arasındaki fark nedir?

Question

traveling-salesman problem ve chinese postman problem arasındaki fark nedir? Benim için ikisi de bir hedefe gitmek istiyor ve sonra geri.

Answer 1

Gezgin, her şehre bir kez gidip en kısa rotayı almakla ilgilidir.

Çin Postacı Problemi, her bir şehirden bir şehre giden bir yol almaktır.

E.g. noktaları A, B, C ve D seyyar satıcı ABCDA gidebiliriz ama Çin postacı

seyyar satıcı rota yoktur vb AB ve AC ve AD vardı bir rota, gerek gider her nokta arasında doğrudan (yukarıdaki örnekte AC bağlantısı yoktur).

DÜZENLEME:
Her şehir bir köşe ve her şehirlerarası bağlantısı bir kenardır. Yani, ben sadece Xodarap'ın cevabını yeniden düzenliyorum.

Answer 2

• Çinli postacı: http://en.wikipedia.org/wiki/Route_inspection_problem
• Gezgin Satıcı: http://en.wikipedia.org/wiki/Travelling_salesman_problem

iki makale (ve grafik teorisi bir ders aldı asla, bu yüzden konuşarak olabilir kısa bir okuma Gönderen şapkam), "CPP" nin tüm kenarları ziyaret etmeyi içerdiği ve "TSP" nin tüm düğümleri ziyaret etmeyi içerdiği anlaşılıyor.

Answer 3

Bence bu, kompleksi kolej kurslarında sunulan yol probleminin bir başka varyasyondur.

Çin Seyahat Eden Satıcı Problemi (C-TSP) tipik bir simetrik TSP sorunudur. Basit açıklaması: 31 Çin başkentinin ve onların ikili mesafelerinin bir listesi göz önüne alındığında, görev her bir şehri bir kez ziyaret eden en kısa turu bulmaktır. C-TSP, orta ölçekli bir TSP sorunudur, (31−1)!/2 = 1.326 * 1032 olası yolları vardır.

Answer 4

Grafikler kenarlardan ve köşelerden yapılmıştır. CPP tüm kenarlara ziyaret gerektirir. TSP tüm köşelere ziyareti gerektirir.

Answer 5

ikisi arasındaki temel fark şudur:

Gezgin Satıcı Problemi kereden bir düğüm daha ziyaret edemez. Üretilen yol tüm farklı düğümlerden/şehirlerden oluşacaktır.

Çin Postacı/Rota Denetimi problemi, üretilen yoldaki iki kopya düğümüne sahip olabilir (ancak yinelenen kenarlar değil). Yani düğümler bir kez sürece aldı daha dışarı farklı bir yoldan olarak daha ziyaret edilebilir

Answer 6

Gezgin Satıcı Problemi:. Verilen şehirler ve mesafe şehirler arası, her şehri ziyaret şekilde en kısa mesafe turu bulmak tam olarak bir tane. Bunu her bir kenarla ilişkili bir grafik ve maliyet veya ağırlık olarak görselleştirerek, her köşe veya düğümün tam olarak bir kez ziyaret edileceği şekilde en ucuz veya en az ağırlıktaki turu (Hamilton yolu) bulun. Bunu tüm olası Hamiltonian yolunu bulmak ve sonra aralarında en iyisini bulmak olarak düşünebiliriz. Satıcı problemi Seyahat aksine , CPP bir az maliyet veya minimum ağırlık turu bulmak gerekir: - bir optimizasyon problemi ve NP mümkün olan tüm yolları olduğunu bulma Komple araçlar hiçbir polinom zaman çözümü

Çinli Postacı Problemi bu problem bulunmaktadır grafik sayesinde her kenar en az bir kez ziyaret edilir. Problemin polinom çözümü var ve optimal çözüm, grafik Euleryalı ise grafikte bir Euler turu bulmayı gerektiriyor. Else onu euler yapan ve bir Euler turu tanımlamak için grafiği değiştir. Çin Postman Sorunu'nun özel bir örneği, grafiğin tüm kenarlarını değil, yalnızca bazılarını (Gerekli kenarlar) taşımamız gerektiğidir. Bu varyasyon Kırsal postacı sorunu olarak adlandırılır ve NP-tamamlandı. Diğer bir deyişle, bir grafik verildiğinde, gerekli tüm kenarların en az bir kez kaplanması için gerekli olmayan kenarları kullanabilecek şekilde en az maliyet/minimum ağırlık turu bulun.

Answer 7

o ultra basit tutulması: Orijinal şehre dönerken Satıcı Problemi Seyahat

hakkında pek de bir kez her şehre gidiyor (böylece bir Hamiltonian cycle yürürken) ve ayrıca olası tüm arasında en kısa yol alınarak Bu kriteri yerine getiren yollar (eğer böyle bir rota varsa). Böyle bir döngüyü bulmak, mümkün olan en kısa mesafeyle olası en uygun döngüyü bulmaktır, "zor" dur.

Çinli Postacı Problemi veya Rota Muayene Sorunu böyle bir rota eğer (orijinal şehre dönerken en az bir kez şehirler arasındaki her rotayı ziyaret edip bu criterium yerine getirmek mümkün olan tüm yolları arasında en kısa yol alınarak hakkındadır) bulunmaktadır. Her rotayı bir kez tam olarak alan bir çözüm otomatik olarak en iyi duruma getirilir ve Eulerian Cycle olarak adlandırılır. Böyle bir döngü bulmak "mümkün".