Gezgin Satıcı Problemi veya yabancı kaynaklarda bulabileceğiniz ismi ile “Traveling Salesman Problem” Bilgisayar Bilimleri’nin gelişmesine büyük katkı sağlayan problemlerden bir tanesidir.
Çözmesi anlaması kadar kolay olmayan problemi bu yazımız da inceleyip genel bir bilgi sahibi olmaya çalışalım.
Problem de amaç, bir satıcının bulunduğu şehirden başlayarak her şehre sadece bir kez uğradıktan sonra başladığı şehre dönen en kısa turu bulmaktır.
Şehirler arası gidişi kuş bakışı olarak kabul edersek aşağıdaki örnek harita ile problem tam olarak anlaşılacaktır. Verilen resimde çizilen alternatif bir yolu temsil etmektedir.
Problem, çizge kuramı dilinde, şehirlerin noktalarla, şehirler arası yolların kenarlarla temsil edildiği (yalın) bir çizge üzerinde, en kısa Hamilton turunun bulunmasıdır.
Hamilton turu, bir çizge üzerindeki her noktadan sadece bir kez geçen ve başladığı noktada biten, 19. yüzyılda yaşamış matematikçi William Hamilton’ın adıyla anılan turdur.
Örneğin n noktadan oluşan bir tam çizge, yani Kn tamçizgesi (n−1)!/2 Hamilton turu içerir.
Bu noktada problemimizi anladığımızı kabul ediyor ve bulmamız gereken turun en iyi (kısa) Hamilton turu olduğunu belirterek problemin zorluğunun anlaşılması için küçük bir hesap yapmak istiyorum.
Yöntemde izleyeceğimiz yollar şöyle:
- Çizgenin tüm Hamilton turlarını bul.
- Her turun uzunluğunu hesapla.
- Turlar arasından en kısasını seç.
Bu çözüm yöntemi ile, 10 şehir için gereken tur sayısı 9!/2 = 181.440’tır.
Şehir sayısı 20’ye çıktığında ise bulunması gereken tur sayısı 19!/2 ≈ 6,08 × 1016’yı bulur.
25 şehir için ise yaklaşık 3,1 × 1023 turun incelemesi gerekir.
Eğer satıcı, 25 şehirli bir GSP problemini, her Hamilton turunu 10-9 saniyede inceleme kapasitesine sahip bir bilgisayarla çözmeye kalkarsa, ancak 10 milyon yıl sonra en kısa turu bulabilir…
Bulunan çözüm çözüm olmasına çözüm de, çözüm yolunun uygulanması olanaksız.
Bilgisayar bilimlerinde problemleri Zor ve Kolay olarak iki gruba ayırırız.
Eğer çözüme ulaşmak için algoritmanın yapacağı işlem sayısı, problemin boyutunu belirleyen verilerin bir polinomu olarak ifade edilebilinirse bu algoritmalar iyi, çabuk algoritmalardır. Bu yöntemle çözülebilen problemler ise “Kolay problemler” sınıfındadır.
Polinom zamanlı çözümü bulunamamış problemler ise bizim için “Zor Problem” sınıfındadır.
Bilgisayarla polinomsal zamanda çözülebilen problem sınıfı P ile gösterilir. Gezgin satıcı probleminin bunlar arasında olup olmadığını bilmiyoruz. Ne biri çıkıp böyle bir algoritma bulabildi ne de kimse böyle bir algoritmanın olamayacağını ispatlayabildi.
NP olarak gösterilen daha geniş bir problem sınıfı ise bulduğu çözüm polinomsal zamanda doğrulanabilen problemleri içerir. Gezgin satıcı problemi bu sınıfa girer, çünkü verilen bir rotanın herhangi bir başka rotadan daha kısa olup olmadığı polinomsal zamanda kontrol edilebilir. Tek yapmanız gereken rotadaki mesafeleri toplayıp verilen sayıyla karşılaştırmaktır.
Daha önce incelediğimiz Sırt Çantası Problemi de zor problemlere örnek olarak gösterilebilir, eğer o yazımızı okumadıysanız buradan ulaşabilirsiniz.
Peki polinomsal zamanda doğrulanabilen her soru polinomsal zamanda çözülebilir mi?
Eğer bu doğruysa P ve NP sınıfları aynı demektir ve o zaman P=NP yazabiliriz.
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/
***
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.
İki farklı sezgisel algoritma inceleyebiliriz.
Açgözlü yaklaşımı (Greedy approach):
Bu yaklaşıma göre başlangıç olarak seçilen herhangi bir şehre en yakın mesafedeki diğer şehir seçilir ve gezi listesine eklenir. Bu şekilde bütün şehirler gezi listesine eklenene kadar hep en son eklenen şehre en yakın şehir seçilir.
Bu yaklaşım klasik açgözlü yaklaşımının hata yapma ihtimalini barındırmakla birlikte uygulanması en kolay yöntemlerden birisidir.
Tüm rotalar arasındaki en iyi rotayı belirlemediğindecn dolayı stratejik değildir.
En küçük artış yöntemi (Smallest increase):
Bu yöntemde ise toplam gezilecek mesafe her seferinde yeniden hesaplanmakta ve alternatiflerden hangisi eklenirse toplam gezi mesafesi en az olur diye sorgulanarak yeni şehirler eklenmektedir.
Örneğin başlangıçtan alınan 3 şehir gezi listesinde bulunurken 4. şehri seçecek olalım. Bu durumda bütün ihtimaller teker teker listeye eklenerek en az mesafe hangisinde bulunuyorsa bu şehir seçilir.
***
Bu yazı ile genel bir fikir sahibi olabileceğiniz problemin detaylarını incelemek isterseniz referanslarımıza göz atabilirsiniz.
Metin Turgay
Referanslar:
- Gezgin Satıcı Problemi, Haldun Sural, Matematik Dünyası, 2003 Güz
- Seyyar Tüccar Problemi, Sadi Evren Şeker, BilgisayarKavramlari, 2008
- Vikipedi
Matematiksel