Lin-Kernighan buluşsal yöntemi - Lin–Kernighan heuristic

Bu makale, seyyar satıcı sorunu için buluşsal yöntem hakkındadır. Grafik bölümleme problemine yönelik sezgisel bir algoritma için bkz. Kernighan – Lin algoritması.

İçinde kombinatoryal optimizasyon, Lin-Kernighan en iyilerden biri Sezgisel simetrik olanı çözmek için seyyar satıcı sorunu. Kısaca, yeni bir tur yapmak için alt tur çiftlerini değiştirmeyi içerir. Bu bir genellemedir 2 seçenekli ve 3 seçenekli. Turu kısaltmak için iki veya üç kenarı değiştirerek 2 seçenekli ve 3 seçenekli çalışma. Lin – Kernighan uyarlanabilirdir ve her adımda daha kısa bir tur bulmak için şehirler arasında kaç yolun değiştirilmesi gerektiğine karar verir.

Ayrıca bakınız

Referanslar

  • Lin, Shen; Kernighan, B.W. (1973). "Seyahat Eden-Satıcı Problemi İçin Etkili Sezgisel Algoritma". Yöneylem Araştırması. 21 (2): 498–516. doi:10.1287 / opre.21.2.498.
  • K. Helsgaun (2000). "Lin-Kernighan Seyahat Satıcısı Sezgisel Yönteminin Etkili Bir Uygulaması". Avrupa Yöneylem Araştırması Dergisi. 126 (1): 106–130. CiteSeerX  10.1.1.180.1798. doi:10.1016 / S0377-2217 (99) 00284-2.
  • Johnson, David S .; McGeoch, Lyle A. (1997). "Seyahat Eden Satıcı Sorunu: Yerel Optimizasyonda Bir Örnek Olay" (PDF). E. H. L. Aarts'ta; J. K. Lenstra (eds.). Kombinatoryal Optimizasyonda Yerel Arama. Londra: John Wiley and Sons. s. 215–310.

Dış bağlantılar