AlegsaOnline.com

Gezgin satıcı problemi

Yazar: Leandro Alegsa

18-05-2022

Gezgin Satıcı Problemi (genellikle TSP olarak adlandırılır), bilgisayar bilimleri ve yöneylem araştırması alanında klasik bir algoritmik problemdir. Optimizasyon üzerine odaklanmıştır. Bu bağlamda, daha iyi çözüm genellikle daha ucuz, daha kısa veya daha hızlı bir çözüm anlamına gelir. TSP matematiksel bir problemdir. En kolay şekilde bir dizi düğümün konumlarını tanımlayan bir grafik olarak ifade edilir.

Gezgin satıcı problemi 1800'lü yıllarda İrlandalı matematikçi W. R. Hamilton ve İngiliz matematikçi Thomas Kirkman tarafından tanımlanmıştır. Hamilton'un Icosian Oyunu, bir Hamilton döngüsü bulmaya dayanan eğlence amaçlı bir bulmacaydı. TSP'nin genel formunun ilk olarak 1930'larda Viyana'da ve Harvard'da matematikçiler tarafından, özellikle de Karl Menger tarafından çalışıldığı görülmektedir. Menger problemi tanımlamış, kaba kuvvet algoritmasını ele almış ve en yakın komşu sezgisel yönteminin optimal olmadığını gözlemlemiştir:

Postacı problemi (pratikte bu sorunun her postacı tarafından çözülmesi gerektiğinden, yine de birçok gezgin tarafından çözülmesi gerektiğinden), ikili mesafeleri bilinen sonsuz sayıda nokta için, noktaları birbirine bağlayan en kısa rotayı bulma görevini ifade ediyoruz. Elbette bu problem sonlu sayıda deneme ile çözülebilir. Deneme sayısını, verilen noktaların permütasyon sayısının altına düşürecek kurallar bilinmemektedir. Önce başlangıç noktasından en yakın noktaya, sonra buna en yakın noktaya vb. gidilmesi kuralı genel olarak en kısa rotayı vermez.

Princeton Üniversitesi'nden Hassler Whitney kısa bir süre sonra gezgin satıcı problemini ortaya atmıştır.

Bir satıcı A, B, C ve D şehirlerini ziyaret etmek istiyor. Bunu yapmanın en iyi yolu nedir (en ucuz uçak biletleri ve en az seyahat süresi)?

Almanya'nın en büyük 15 şehrini ziyaret eden bir satıcının optimum rotası. Gösterilen rota 43,589,145,600 olası rota arasından en kısa olanıdır.

Sorunun belirtilmesi

Gezgin Satıcı Problemi, N şehir arasında seyahat etmesi gereken bir satıcıyı tanımlar. Bunu hangi sırayla yaptığı, yolculuğu sırasında her birini bir kez ziyaret ettiği ve ilk bulunduğu yerde bitirdiği sürece umurunda olmayan bir şeydir. Her şehir diğer yakın şehirlere veya düğümlere uçaklarla veya karayolu ya da demiryolu ile bağlıdır. Şehirler arasındaki bu bağlantıların her birine bir veya daha fazla ağırlık (veya maliyet) eklenmiştir. Maliyet, grafikteki bu kenarı geçmenin ne kadar "zor" olduğunu tanımlar ve örneğin bir uçak biletinin veya tren biletinin maliyeti veya belki de kenarın uzunluğu veya geçişi tamamlamak için gereken süre ile verilebilir. Satıcı hem seyahat maliyetlerini hem de kat ettiği mesafeyi mümkün olduğunca düşük tutmak ister.

Gezgin Satıcı Problemi, matematikçilerin ve bilgisayar bilimcilerinin yıllardır ilgisini çeken geniş bir "zor" optimizasyon problemleri sınıfının tipik bir örneğidir. En önemlisi, bilim ve mühendislikte uygulamaları vardır. Örneğin, bir devre kartının üretiminde, bir lazerin binlerce delik açacağı en iyi sırayı belirlemek önemlidir. Bu soruna bulunacak etkili bir çözüm, üreticinin üretim maliyetlerini düşürür.

Zorluk

Genel olarak, gezgin satıcı problemini çözmek zordur. Bu problemi daha küçük bileşen problemlerine ayırmanın bir yolu varsa, bileşenler en az orijinal problem kadar karmaşık olacaktır. Bilgisayar bilimcileri buna NP-zor problemler demektedir.

Birçok kişi bu sorun üzerinde çalışmıştır. En kolay (ve en pahalı çözüm) tüm olasılıkları denemektir. Bununla ilgili sorun, N şehir için (N-1) faktöriyel olasılığa sahip olmanızdır. Bu, sadece 10 şehir için denenecek 180 binden fazla kombinasyon olduğu anlamına gelir (başlangıç şehri tanımlandığından, kalan dokuz şehir üzerinde permütasyonlar olabilir). Her rotanın aynı uzunlukta veya maliyette tersine eşit bir rotası olduğu için sadece yarısını sayıyoruz. 9! / 2 = 181 440

Dal ve sınır algoritmaları kullanılarak problemin kesin çözümleri bulunabilir. Bu şu anda 85.900'e kadar şehir için mümkündür.
Sezgisel yaklaşımlar, bir sonraki düğümün seçimi için bir dizi yol gösterici kural kullanır. Ancak sezgisel yöntemler yaklaşık sonuçlar verdiğinden, her zaman en uygun çözümü vermeyecektir, ancak yüksek kaliteli kabul edilebilir sezgisel yöntemler, problemin tam bir kaba kuvvetle çözülmesi için gereken sürenin bir kısmında yararlı bir çözüm bulabilir. Bir düğüm için sezgisel yöntemlere örnek olarak, ziyaret edilmemiş kaç düğümün bağlı bir düğüme "yakın" olduğunun bir toplamı verilebilir. Bu, satıcıyı grafikteki başka bir doğal kümeye geçmeden önce birlikte kümelenmiş bir grup yakın düğümü ziyaret etmeye teşvik edebilir. Bakınız Monte Carlo algoritmaları ve Las Vegas algoritmaları

Sorular ve Yanıtlar

S: Gezgin Satıcı Problemi nedir?

C: Gezgin Satıcı Problemi (TSP), bilgisayar bilimleri ve yöneylem araştırması alanında klasik bir algoritmik problemdir. Optimizasyona odaklanır ve daha iyi çözümler genellikle daha ucuz, daha kısa veya daha hızlı çözümler anlamına gelir.

S: TSP nasıl ifade edilir?

C: TSP en kolay şekilde bir dizi düğümün konumlarını tanımlayan bir grafik olarak ifade edilir.

S: TSP'yi ilk kim tanımladı?

C: Gezgin satıcı problemi 1800'lerde İrlandalı matematikçi W. R. Hamilton ve İngiliz matematikçi Thomas Kirkman tarafından tanımlanmıştır.

S: 1930'larda bu problem üzerinde kim daha fazla çalıştı?

C: 1930'larda Viyana ve Harvard'daki matematikçiler Karl Menger bu konu üzerinde daha fazla çalışmıştır.

S: Hassler Whitney kısa bir süre sonra neyi tanıttı?

C: Princeton Üniversitesi'nden Hassler Whitney, tanımlanmasından kısa bir süre sonra "gezgin satıcı problemi" adını ortaya attı.

S: Bu bağlamda "daha iyi çözüm" ne anlama geliyor?

C: Bu bağlamda, daha iyi çözüm genellikle daha ucuz, daha kısa veya daha hızlı bir çözüm anlamına gelir.

S: TSP üzerinde çalışırken Menger tarafından hangi algoritmanın bariz olduğu düşünülmüştür?

C: Menger, TSP'yi incelerken bariz bir kaba kuvvet algoritması düşünmüş ve en yakın komşu sezgiselini kullanmanın her zaman optimal sonuçlar vermediğini gözlemlemiştir.