Gezgin Satıcı Problemi

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.

GSP, çizge kuramı dilinde, şehirlerin noktalarla, şehirlerarası 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:

  1.  Çizgenin tüm Hamilton turlarını bul.
  2.  Her turun uzunluğunu hesapla.
  3.  Turlar arasından en kısasını seç.

Bu çözüm yöntemi ile, 10 şehir içeren bir GSP için bulunması 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 GSP problemini bu yolla  çözmek isteyen bir satıcının, yaklaşık 3,1 × 1023 turu 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. Eğer problemin çözümü için önerilen algoritmada işlem sayısı verilerin üssel kuvveti şeklinde bir polinom ile ifade ediliyorsa bu algoritma kötü algoritmadır. Polinom zamanlı çözümü bulunamamış problemler bizim için “Zor Problem” sınıfındadı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.

Gezgin Satıcı Problemi de zor problemlerden biridir. 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 (optimum) çözümü veren algoritmalardır. GSP için iki farklı sezgisel algoritma inceleyebiliriz.

  1. 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.
  2. 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.

Yazımız da öncelikle problemi tanıyıp daha sonra el yordamı ile en iyi sonucu bulmanın ne kadar zor olacağını örnekleyerek gösterdik. Bu nokta da sezgisel algoritmalara olan ihtiyacımıza değindikten sonra iki farklı sezgisel algoritma örneği verdik. Bu yazı ile genel bir fikir sahibi olabileceğiniz problemin detaylarını incelemek isterseniz referanslarımıza göz atabilirsiniz.

Metin Turgay

Referanslar:

  1. Gezgin Satıcı Problemi, Haldun Sural, Matematik Dünyası, 2003 Güz
  2. Seyyar Tüccar Problemi, Sadi Evren Şeker, BilgisayarKavramlari, 2008
  3. Vikipedi

Matematiksel

Paylaşmak İsterseniz

Yazıyı Hazırlayan: Metin Turgay

Dokuz Eylül Üniversitesi matematik bölümü 4. sınıf öğrencisiyim. Bilgisayar Bilimleri bölümünde yandal yapmaktayım. Hobi olarak başlayan bu heves gün geçerek artmaya devam etti. Matematik ile bilgisayarın kavuştuğu alanları öğrenmekten elimden geldiği kadar da öğretmekten zevk alıyorum.

Bunlara da Göz Atın

Matematik Henüz Sormadığımız Sorulara Nasıl Cevap Verebilir?

Matematik, evrene ilişkin sorularımıza doğru cevaplar sağlayan bir enstrüman olarak görülebilir. Örneğin, 2 elmamız olduğunu …

Bir Yorum

  1. Mehmet Babacan

    Bu konuyla ilgili excelde nasıl yapılır anlatan güzel örnek bir video
    https://www.youtube.com/watch?v=-E3rSoClgMI

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

This site uses Akismet to reduce spam. Learn how your comment data is processed.

ga('send', 'pageview');