:::: MENU ::::

TSPLIB verisini MATLAB ile işlenebilecek hale nasıl getirebiliriz?

Sayın Mustafa Servet KIRAN hocamın aşağıdaki yorumu sonucu yazı içeriği değişmiştir.

EDGE_WEIGHT_TYPE: GEO
alanı oldukça önemli, GEO ise farkı denklem ile, EUC ise öklit denklemi ile uzaklık hesaplanmalıdır. GEO’yu EUC şeklinde hesaplarsanız “optimumdan daha optimum” (!) sonuç elde edebilirsiniz.
Cevahir her zamanki gibi detaylara önem vermeden ana mantık faydalı olmaktır prensibiyle yukarıdaki paylaşımı yaptığı için böyle bir hatanın oluşması kaçınılmazdı.

Bu arada pdist fonksiyonu matlabda çiftler arasındaki öklit mesafesini hesaplar, yukarıdaki hesaplama dolayısıyla yanlıştır.

Gezgin satıcı problemine çözüm ararken, literatürde bulunan bir çok kıyas problemi üzerinde test yapılmaktadır. TSPLIB tarafından sağlanan formatın kendi çözümlerimde kullanmak üzere aşağıdaki şekilde hazırlıyorum.

Öncelikle verilen koordinatların hangi tipte olduğuna dikkat etmemiz gerekiyor. Ben genelde öklid uzayında verilmiş verilerle çalıştığımdan, yukarıdaki uyarı yorumunu o yüzden aldım. Şimdi hem öklid hem de geo nasıl hesaplanır birlikte inceleyelim.

Aşağıdaki problem (ulysses22.tsp), EDGE_WEIGHT_TYPE: GEO olduğu için, verilen koordinatlar enlem ve boylam bilgisini içermektedir.

TSPLIB kendi sayfasında bu problem için optimum değeri 7013 olarak vermiş, yani bizim hesaplamamız optimum tur değerini aldığı zaman bu değeri vermelidir.

kodunu çalıştırdığımız zaman 6971 değerini vermektedir.

Öncelikle yukarıdaki hesaplamayı TSPLIB’ın kendi sayfasından aldım.

Farklı olan derecenin radyana dönüşümü. O dönüşümden dolayı bir fark olabilir mi diye ilgili sayfadaki derece radyan dönüşümünü yaptım.

Bu dönüşüm ile yaptığım hesaplamada ise 7132 buldum.

Dikkat ederseniz RRR = 6378.388 şeklinde bir sabit, farklı kaynaklarda bu sayının farklı alındığını gördüm. O yüzden bir hesaplama farklılığı olabilir.

Şimdi gelelim öklid uzayında verilmiş bir problemin dönüştürülmesine:

eil51 problemi aşağıdaki gibidir:

Yukarıdaki koordinat bilgilerini Matlab içerisine aktarıyoruz.
a=[51×2 boyutunda koordinatların bulunduğu matris];
b=pdist(a); / Koordinatların birbirine göre uzaklıkları hesaplanıyor.
c=squareform(b); / Uzaklıkları 51×51’lik kare matris haline çeviriyoruz.

optimum 426 iken benim hesabımda 429.9833 bulunuyor. Sebebi ondalıklı sayılardan kaynaklı hassasiyettir.

Bu arada pdist fonksiyonu matlabda çiftler arasındaki öklit mesafesini hesaplar, yukarıdaki hesaplama dolayısıyla yanlıştır.

pdist komutu 2 sütun şeklinde verilen verileri de hesaplıyor.


4 Yorum

  • Cevapla Mustafa Servet Kıran |

    EDGE_WEIGHT_TYPE: GEO
    alanı oldukça önemli, GEO ise farkı denklem ile, EUC ise öklit denklemi ile uzaklık hesaplanmalıdır. GEO’yu EUC şeklinde hesaplarsanız “optimumdan daha optimum” (!) sonuç elde edebilirsiniz.
    Cevahir her zamanki gibi detaylara önem vermeden ana mantık faydalı olmaktır prensibiyle yukarıdaki paylaşımı yaptığı için böyle bir hatanın oluşması kaçınılmazdı.

    Bu arada pdist fonksiyonu matlabda çiftler arasındaki öklit mesafesini hesaplar, yukarıdaki hesaplama dolayısıyla yanlıştır.

    • Cevapla Ahmet Cevahir ÇINAR |

      Değerli yorumunuz için teşekkür ederim. Öklid uzayında yaptığım dönüşümü buraya yazayım, unuttuğumda bakarım amacıyla yazdığım yazı sayesinde ve sizin uyarınız sonucunda sadece öklid ve geo tipinde değil başka tiplerde de formatların olduğunu gördüm. İşin ilginç yanı literatürde bu durumu bilmeyen ve indeksli dergilerde yayın yapan kişiler var. Allah herkese sizin gibi bir hoca nasip etsin. Amin.

Görüşlerinizi önemsiyorum...