28 Aralık 2019 Cumartesi

GSP (Java 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.
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:
  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ç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…
Satıcı Problemi


Şehirler Arası mesafe



Şehirler arası mesafe text dosyası

000,374,200,223,108,178,252,285,240,356
374,000,255,166,433,199,135,095,136,017
200,255,000,128,277,128,180,160,131,247
223,166,128,000,430,047,052,084,040,155
108,433,277,430,000,453,478,344,389,423
178,199,128,047,453,000,091,110,064,181
252,135,180,052,478,091,000,114,083,117
285,095,160,084,344,110,114,000,047,078
240,136,131,040,389,064,083,047,000,118
356,017,247,155,423,181,117,078,118,000

Hiç yorum yok:

Yorum Gönderme