Yazan : Şadi Evren ŞEKER Bu problemin amacı pekçok farklı yer gezen bir tüccarın en az yol katederek bütün gezeceği yerleri nasıl tamamlayacağının hesaplanmasıdır. (gezgin satıcı problemi) Örneğin aşağıda verilen türkiye haritasında farklı iller ve bu illerin coğrafi konumları işaretlenmiştir. Kolaylık olsun diye iller arasındaki mesafeleri kuş uçuşu gitmek istersek bu durumda bütün illeri dolaşan en kısa yol aşağıdaki şekilde olur.

Dikkat edilirse bu haritada bütün noktaları dolaşan en kısa yol bulunmuştur. Bu işlemi yaparken kullanılabilecek bir iki yol aşağıda açıklanmıştır:

Açgözülü yaklaşımı (greedy approach): Bu yaklaşıma göre başlangıç olarak seçilen herhangi bir şehire 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.

Enküçük artış yöntemi (Smallest increase): By yöntemde ise toplam gezilecek mesafe her seferinde yeniden hesaplanmakta ve alternatiflerden hangisi eklenirse toplam gezi mesafesi en az olur diye sorglunarak 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.

Bir cevap yazın

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