Tur uzunluğu
Bulunan en kısa
Adım sayısı
Olası turlar
  • Tur
  • Bulunan en kısa
  • Başlangıç

Yöntem Uzunluk En kısadan fark Adım sayısı
- - -
- - -
- - -
- - -
- - -

Gezgin satıcı problemi hakkında daha fazla

Gezgin satıcı problemi

Bir satıcı her şehri bir kez ziyaret edip evine dönmek zorunda. Hangi sıra yolculuğu en kısa yapar? Soruyu sormak kolaydır, ama şehir sayısı arttıkça her sırayı deneyerek yanıtlamak umutsuzdur: 30 şehir bile yaklaşık 4,4 × 10³⁰ farklı tura izin verir. Şehirleri haritaya dağıtın ya da kendiniz tıklayarak yerleştirin; ardından hızlı pratik kuralların, akıllı iyileştirmelerin ve tek bir kesin yöntemin turlarını adım adım nasıl kurduğunu izleyin ve hızlı olanların ne kadar yaklaştığını görün. Şehirlerin nasıl yerleşeceğini ve kaç tane olacağını seçin, bir yöntem belirleyin ve turu adım adım nasıl kurduğunu izlemek için Çöz'e, her seferinde tek bir hamle ilerlemek için Adım'a basın. Şehir eklemek için haritaya, bir şehri kaldırmak için şehrin üzerine tıklayın. Tümünü karşılaştır, her yöntemi aynı şehirler üzerinde çalıştırır ve her birinin bulunan en kısa turdan ne kadar uzak olduğunu gösterir. Kırmızı şehir, yolculuğun başladığı yerdir.

Nasıl çalışır

  1. Bir yerleşim ve şehir sayısı seçin ya da kendi şehirlerinizi yerleştirmek için haritaya, bir şehri kaldırmak için şehrin üzerine tıklayın.
  2. Bir yöntem seçin ve adım adım izlemek için Çöz'e, her seferinde tek bir hamle ilerlemek için Adım'a basın.
  3. Her yöntemi aynı şehirler üzerinde çalıştırmak için Tümünü karşılaştır'a basın ve her turun bulunan en kısa turdan ne kadar uzun olduğunu okuyun.

Neden zor

n şehir için (n − 1)! / 2 farklı tur vardır, çünkü nereden başladığınızın ya da hangi yönde dolaştığınızın önemi yoktur. Bu, 5 şehir için 12, 10 şehir için 181.440, 20 şehir için ise yaklaşık 6 × 10¹⁶ eder. Her harita için en kısa turu, süresi n'nin yalnızca bir kuvveti gibi artan bir zamanda bulan bilinen bir yöntem yoktur; problem NP-zordur. Bu uygulamadaki en iyi kesin yöntem olan 1962 tarihli Held–Karp dinamik programlaması bile yaklaşık n² · 2ⁿ adım gerektirir; bu yüzden burada 12 şehirle sınırlıdır.

Hızlıca iyi turlar

Pratikte en kısaya çok yakın turlar hızla bulunur. En yakın komşu her zaman henüz ziyaret edilmemiş en yakın şehre gider ve genellikle en iyi turdan yaklaşık %25 daha uzun bir turla biter. En ucuz ekleme bir döngüyü büyütür ve onu en az uzatan şehri ekler. 2-opt herhangi bir turu alır ve iki kenarı sürekli olarak daha kısa iki kenarla değiştirir; bu, bütün kesişmeleri ortadan kaldırır ve genellikle yaklaşık %5'lik farka kadar yaklaşır. Benzetimli tavlama rastgele 2-opt hamleleri yapar ve henüz “sıcak” iken turu uzatan bazı hamleleri de kabul eder; böylece yerleşmeden önce çıkmazlardan kurtulabilir.

Sık sorulan sorular

En kısa rota için bir formül var mı?

Hayır. En kısa tur bütün şehirlerin tam konumlarına bağlıdır ve onu her harita için, en kötü durumda üstel olarak büyüyen bir iş miktarı gerektirmeden bulan bilinen bir yöntem yoktur. Birkaç yüz ya da birkaç bin şehir için Concorde gibi özel kesin çözücüler, doğrusal programlamayı akıllı budamayla birleştirerek en iyi turları yine de kanıtlar; şimdiye kadar kesin olarak çözülmüş en büyük örnek 85.900 noktadan oluşur.

2-opt neden bütün kesişmeleri ortadan kaldırır?

Bir turun iki kenarı kesişiyorsa, bu kenarların birleştirdiği dört şehir, köşegenleri bu iki kenar olan bir dörtgen oluşturur. Onları dörtgenin karşılıklı iki kenarıyla değiştirmek, üçgen eşitsizliği nedeniyle her zaman daha kısadır ve aradaki tur parçasını ters çevirir. 2-opt, hiçbiri işe yaramayana kadar bu tür değişiklikler yapmayı sürdürür; bu yüzden son turu hiçbir zaman kendini kesmez.

Benzetimli tavlamada sıcaklık nedir?

Yöntemin turu uzatan bir hamleyi kabul etmeye ne kadar istekli olduğunu belirler. Uzunluğa d ekleyen bir hamle e^(−d/T) olasılıkla kabul edilir. Yüksek bir T sıcaklığında neredeyse her şey kabul edilir; bu da turun kötü bir düzenden kurtulmasını sağlar. T düştükçe yöntem açgözlü hâle gelir ve yerleşir. Ad, atomlarının düşük enerjili bir düzen bulması için metalin yavaşça soğutulmasından gelir.

Kesin yöntem neden 12 şehirle sınırlı?

Held–Karp, her şehir alt kümesi ve olası her son şehir için en kısa yolu saklar; bu yaklaşık n · 2ⁿ sayı eder ve her birini n karşılaştırmayla doldurur. 12 şehir için bu birkaç yüz bin adımdır; 25 şehir için milyarlarca adım olurdu. Yine de (n − 1)! / 2 turun tümünü denemekten çok daha hızlıdır: 12 şehir için bu neredeyse 20 milyon tur olurdu.

Bir sunucuya herhangi bir şey gönderiliyor mu?

Hayır. Şehirler ve beş yöntemin tümü tarayıcınızda çalışır. Tıklayarak eklediğiniz şehirler bu tarayıcının yerel depolamasında kalır.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Editöre Git