Günlük hayatta en kısa ve en verimli rotayı bulma problemiyle sık sık karşılaşırız. Matematikçiler bu tür problemlere “Gezgin Satıcı Problemi” (Travelling Salesman Problem) adını verir.
İşlerinizi halletme zamanı geldi ve uğramanız gereken birkaç yer var. Evden çıktıktan sonra markete, benzin istasyonuna ve hırdavatçıya uğrayıp yeniden eve dönmeniz gerekiyor. Başlangıç ve bitiş noktanız eviniz olduğu için, izleyebileceğiniz altı farklı rota var.
- market → benzin istasyonu → hırdavatçı
- market → hırdavatçı → benzin istasyonu
- benzin istasyonu → market → hırdavatçı
- benzin istasyonu → hırdavatçı → market
- hırdavatçı → market → benzin istasyonu
- hırdavatçı → benzin istasyonu → market
Gezgin Satıcı Problemi Nedir?
Sorun, bu rotalardan hangisinin en verimli olduğunu belirlemektir. Matematik ve bilgisayar bilimlerinde bu probleme, gezgin satıcı problemi (Traveling Salesman Problem – TSP) denir. Amaç, her noktayı yalnızca bir kez ziyaret ederek başlangıç noktasına dönen en kısa rotayı bulmaktır.
Bu tür problemler, her ne kadar basit görünse de, aslında çok sayıda pratik uygulama alanına sahiptir. Örneğin, farklı adreslere gönderilecek çok sayıda paketiniz varsa, en verimli rotayı belirlemek istersiniz. Günlük işlerinizi planlarken ya da uzun bir yolculuğa çıkarken de zaman ve yakıt kaybetmek istemezsiniz.
Havayolu, üretim veya taşımacılık sektörlerinde çalışan şirketler için ise yolcuları ve yükleri mümkün olan en hızlı ve en verimli şekilde hedef noktaya ulaştırmak büyük önem taşır.
Bu tür problemleri çözmenin en basit yöntemi, “kaba kuvvet” (brute force) adı verilen yaklaşımdır. Bu yöntemde bilgisayar, verilen noktalar arasındaki tüm olası rotaları tek tek inceler, her rotanın toplam mesafesini hesaplar ve en kısa olanı belirler. Ancak olası sonuçların, yani gezgin satıcının izleyebileceği “tur” sayısının miktarı inanılmaz hızlı biçimde artar.
Durak sayısı az olduğunda bu problemi çözmek kolaydır. Ancak durak sayısı arttıkça problem çok daha karmaşık hâle gelir. Çünkü olası rota sayısı üstel olarak artar.
Toplam durak sayısına N dersek, olası tur sayısı formülüyle hesaplanır. Yalnızca 5 durak olduğunda, 12 farklı turun mesafesini hesaplamak çok uzun sürmez. Ancak durak sayısı 10’a çıktığında, tüm olasılıkları hesaplamak neredeyse bir saniye sürer.
Durak sayısı 25’e ulaştığında ise en verimli rota için bilgisayarınızı yaklaşık 10 milyar yıl çalıştırmanız gerekir. Bu süre, neredeyse evrenin yaşına eşittir.
Ancak pratikte kullanılan tek yöntem kaba kuvvet yaklaşımı değildir. Belli seçenekleri en baştan eleyen daha gelişmiş yöntemler de vardır. Bu alandaki en büyük kesin çözüm 2006 yılında elde edildi. Araştırmacılar, 85.900 şehirden geçen en kısa rotayı hesaplamayı başardı. Yine de bu hesaplama için kullanılan bilgisayarların toplam işlem süresi bir yüzyıldan fazlaydı.
Gezgin Satıcı Problemi İle İlgili Sorun Nedir?
Bir algoritmanın bir problemi çözmesi için gereken süre, gerçekleştirmesi gereken adım sayısına bağlıdır. Bazı algoritmalarda bu sayı makul hızda artar. Örneğin, n² adım gerektiren bir algoritma 10 şehir için 100, 20 şehir için ise 400 adım kullanır. Bu tür algoritmalar polinom zamanlı algoritmalar olarak adlandırılır ve verimli kabul edilir.
Ancak bazı problemlerde adım sayısı çok daha hızlı büyür. Örneğin, 2ⁿ adım gerektiren bir algoritma 10 şehir için 1.024 adım isterken, 20 şehir için bu sayı 1 milyonun üzerine çıkar. Bu üstel büyüme, büyük problemleri çözmeyi son derece zor hale getirir. Gezgin Satıcı Problemi de buna örnektir.
Bu problem, bilgisayar bilimindeki P ve NP kavramlarıyla yakından ilişkilidir. P sınıfı, bilgisayarların verimli biçimde çözebildiği problemleri kapsar. NP sınıfında ise çözümü bulmak zordur, ancak verilen bir çözümün doğruluğu hızlı şekilde kontrol edilebilir. Gezgin Satıcı Problemi, NP sınıfının en bilinen örneklerinden biridir.
Bilgisayar bilimlerindeki en büyük sorulardan biri şudur. Çözümü doğrulaması kolay olan her problem hızlı biçimde çözülebilir mi? Başka bir deyişle, P ve NP aynı şey midir? Günümüzde bu sorunun cevabı hâlâ bilinmemektedir.
Neyse ki, çalışmalar, kuantum bilgisayarlarının bazı problemleri klasik bilgisayarlardan daha hızlı çözebildiğini göstermektedir. Bunun en dikkat çekici örneklerinden biri, 2019 yılında ilk kez gösterilen kuantum üstünlüğüdür. Bu deney, kuantum bilgisayarlarının belirli görevlerde klasik bilgisayarları geride bırakabildiğini ortaya koymuştur.
Sonuç Olarak
Hesaplamalı karmaşıklık teorisi, algoritmaların ne kadar hızlı çalıştığını inceleyen matematik dalıdır. Algoritmalar, daha sonra bilgisayar programı olarak uygulanabilen soyut talimat dizileridir. Bu alan, Gezgin Satıcı Problemi ve P = NP sorusu gibi matematiğin en ünlü problemlerinden bazılarını içerir.
Bu problemler yalnızca teorik açıdan değil, pratik sonuçları bakımından da büyük önem taşır. Çünkü otomatikleştirmeyi çok istediğimiz pek çok görev vardır ve bunların gerçek dünyadaki makinelerde yeterince hızlı çalıştırılıp çalıştırılamayacağı büyük ölçüde bu problemlerin çözümüne bağlıdır.
Kaynaklar ve İleri Okumalar:
- Matai, Rajesh & Singh, Surya & Mittal, M.L.. (2010). Traveling Salesman Problem: an Overview of Applications, Formulations, and Solution Approaches. 10.5772/12909.
- This 90-year-old math problem shows why we need quantum computers. Yayınlanma tarihi: 4 haziran 2020. kaynak site: Big Think. Bağlantı:This 90-year-old math problem shows why we need quantum computers
Size Bir Mesajımız Var!
Matematiksel, matematiğe karşı duyulan önyargıyı azaltmak ve ilgiyi arttırmak amacıyla kurulmuş bir platformdur. Sitemizde, öncelikli olarak matematik ile ilgili yazılar yer almaktadır. Ancak bilimin bütünsel yapısı itibari ile diğer bilim dalları ile ilgili konular da ilerleyen yıllarda sitemize dahil edilmiştir. Bu sitenin tek kazancı sizlere göstermek zorunda kaldığımız reklamlardır. Yüksek okunurluk düzeyine sahip bir web sitesi barındırmak ne yazık ki günümüzde oldukça masraflıdır. Bu konuda bizi anlayacağınızı umuyoruz. Ayrıca yazımızı paylaşarak da büyümemize destek olabilirsiniz. Matematik ile kalalım, bilim ile kalalım.
Matematiksel
