Olasılık ve İstatistik

Gezgin Satıcı Problemi Nedir ve Neden Önemlidir?

Bir kargo siparişi verdiğinizde matematiğin ödediğiniz para dışında hiçbir yerde işinize karışmadığını düşünebilirsiniz. İşte bu nokta da yanılıyorsunuz. Matematik paketlerinizin teslimi esnasında da çok önemli bir rol oynar. Gezgin satıcı problemini bilenler ne demek istediğimizi daha iyi anlar.

Büyük kargo firmalarının operasyonlarının merkezinde, herhangi bir sürücünün gidebileceği en kısa rotayı belirleme süreci vardır. Bir teslimat rotasında gereğinden bir kilometre daha fazla giden bir sürücü, şirkete yılda milyonlarca liralık zarara mal olur. Her rotayı olabildiğince kısa ve verimli hale getirme işi bu nedenle çok önemlidir. Mümkün olan en iyi rotayı bulma problemi matematikçiler tarafından Gezgin Satıcı problemi olarak bilinir. İsim, kapıdan kapıya satışların daha yaygın olduğu günlerde icat edilmiştir. Bir günde belirli sayıda haneyi ziyaret etmek zorunda kalan bir satıcı, onu her haneye en kısa sürede götüren rotayı bulmak zorundadır ve olasılıklar çok fazladır.

Gezgin Satıcı Problemi İle İlgili Bir Örnek

Diyelim ki çok sayıda şehre uçmanız gerekiyor. En düşük uçuş maliyetini sağlayacak biçimde bu şehirleri hangi sırayla ziyaret etmelisiniz?

Yolculuğunuz İstanbul’dan başlayacak ve yine İstanbul’da bitecek. İzmir, Ankara, Bodrum, Trabzon, Erzurum, Mardin, Bilecek, Zonguldak, Muğla ve Kayseri ziyaret etmek istediğiniz yerler arasında. Güzergahın toplam uzunluğu konusunda bir sıkıntınız yok ama endişe etmeyebilirsiniz lakin bu seyahatin maddi tutarını minimize etmek zorundasınız. Burada dikkat edilmesi gereken ilk şey 10 tane şehrin kulağa çok gelmemesine karşın bu şehirlerden oluşturulabilecek seyahat planının 10 faktöriyel olmasıdır: 3 ,5 milyondan daha fazla. Diğer bir deyişle, her permütasyonu kontrol ederek en düşük fiyatlı olanı seçmeniz pratik bir metot değildir. Daha akıllıca hareket etmek zorundasınız.

Şehirler arası gidişi kuş bakışı olarak kabul edersek aşağıdaki örnek harita ile problem tam olarak anlaşılacaktır. Çizgiler alternatif bir rotayı temsil etmektedir.

Aslında bir çok programcı bu kentler arasındaki uçuş için en ucuz maliyeti gerektirecek programı yazabilir. Buradaki sorun şudur: Bu programın görevini sonuçlandırması için milyonlarca yıl çalışması gerekebilir. Uygulama da bu durum kabul edilebilir değildir. Bir problemin karar verilebilir olması onu pratikte çözebileceğimiz anlamına gelmez.

Bilgisayarla polinomsal zamanda çözülebilen problem sınıfı P ile gösterilir. Gezgin satıcı probleminin bunlar arasında olup olmadığını bilmiyoruz. NP olarak gösterilen daha geniş bir problem sınıfı ise bulduğu çözüm polinomsal zamanda doğrulanabilir problemleri içerir. Gezgin satıcı problemi bu sınıfa kesin­likle girer, çünkü verilen bir rotanın herhangi bir başka rotadan daha kısa olup olmadığı polinomsal zamanda kontrol edilebilir.

P=NP midir sorusu günümüzde bilgisayar bilimcilerin en büyük sorularından biridir. Bu o kadar önemli bir soru ki Clay Matematik Enstitüsü P ve NP’nin eşit olduğunu ya da olmadığını ispatlayabilen kişilere 1.000.000 dolar ödül vaat ediyor. Daha fazlası için bu yazımıza göz atmak isteyebilirsiniz: https://www.matematiksel.org/nedir-pnp-problemi/

Gezgin Satıcı Problemi Olası Çözümleri

Polinom zamanda çözümünü bulamadığımız problemler için sezgisel algoritmalar geliştirilmiştir. Sezgisel algoritmalar kesin sonuç vermemekle birlikte çözüme en yakın çözümü veren algoritmalardır. Bu problem için iki farklı sezgisel algoritma inceleyebiliriz.

Açgözlü yaklaşımı (Greedy approach)

Yukarıdaki gezginimizin durumunu ele alalım. İlk önce İstanbul çıkışlı en ucuz bilete bakabilir diyelim ki bu İzmir olsun. İzmir’e gidip oradan diğer şehirlere olan en ucuz uçuşu seçerek devam eder, bu da Muğla olsun. Muğla’ya varıp en ucuz biletle ulaşabileceği üçüncü şehrini seçerek yola devam eder ve en sonunda onuncu şehre gidene kadar bu durum devam eder. Onuncu şehirden ise İstanbul’a geri döner. Sürecin her adımında sadece yakınındakileri görerek mevcutlar içinden en iyi seçeneği tercih eden bir algoritma olan bu yaklaşım hata yapma ihtimalini barındırmakla birlikte uygulanması en kolay yöntemlerden birisidir. Tüm rotalar arasındaki en iyi rotayı belirlemediğinden dolayı stratejik değildir.

Tepe Tırmanma Algoritması (Hill Climbing Algorithm)

Temel bir seyahat planını oluşturduğunuzda, şehirlerin sıralamasında karıştırmalar yaparak bazı alternatifleri test edebilirsiniz. Örneğin eğer ilk olarak İzmir, daha sonra da Kayseri’ye gidiyorsak bu şehirlerin yerlerini değiştirerek bir deneme yapabiliriz. Herhangi bir seyahat planı için 11 tane bunun gibi iki şehrin karşılıklı yer değiştirdiği düzenleme yapabiliriz; bunların hepsini dener ve bize en fazla tasarruf ettiren planı seçebiliriz.

En sonunda diğer tüm permütasyonlardan daha iyi olan bir çözüm elinize geçecektir. Yan yana hangi iki şehri değiştirirseniz değiştirin hiçbir alternatif ondan iyi olmayacaktır. Tepe tırmanmanın durduğu nokta işte burasıdır. Peki bu, en iyi seyahat planını bulduğunuz anlamına geliyor? Maalesef hayır. Tüm olasılıkların içinde yer alan global en iyiyi değil, “yerel” en iyiyi bulmuş olabilirsiniz. Konu hakkında daha fazla bilgi edinmek isterseniz kaynaklardaki bağlantıları incelemenizi öneririz.

Beyazperdede Gezgin Satıcı Problemi

Gezici Satıcı sorunu 2012 yılında beyaz perdeye taşıdı. Traveling Salesman adlı bir film, ABD ordusuna P = NP problemine bir çözüm verip vermemeye karar vermesi gereken dört matematikçinin hikayesi. Matematikçiler bu noktada işin ahlaki boyutuna odaklanıyorlar. Çünkü, ordu çözüme sahip olduğunda dünyadaki herhangi bir kod kırılır hale gelecektir. Filmin fragmanına göz atabilirsiniz.

İleri Okumalar:

Matematiksel

Sibel Çağlar

7 yıl Kadıköy Anadolu Lisesinin devamında lisans eğitimimi Marmara Üniversitesi İng. Matematik öğretmenliği üzerine tamamladım. Devamında 20 yıl çeşitli özel eğitim kurumlarında matematik öğretmenliği ve eğitim koordinatörlüğü yaptım. 2015 yılında matematiksel.org web sitesini kurdum. Amacım bilime ilgiyi arttırmak, bilimin özellikle matematiğin zihin açıcı yönünü açığa koymaktı. Yolumuz daha uzun ve zorlu ancak en azından deniyoruz.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak.