Seyyar satıcı problemi

'Güncel Bilgiler' forumunda aykuta tarafından 14 Haziran 2009 tarihinde açılan konu


  1. Seyyar satıcı problemi, en önemli algoritma problemlerinden biridir. NP-Tam olan problem şu şekildedir:

    * Bir seyyar satıcı var
    * Bu satıcı, mallarını n \, şehirde satmak istiyor
    * Öte yandan, mantıklı bir şekilde, bu satıcı bu şehirleri mümkün olan en kısa şekilde ve her bir sehire maksimum bir kere ugrayarak turlamak istiyor

    Problemin amacı, satıcıya bu en kısa yolu sunabilmektir. Basit bir sekilde:

    * İlk şehirde, satıcının n \, değişik şehir arasında seçim hakkı vardır
    * İkinci şehirde, satıcının n - 1 \, değişik şehir arasında seçim hakkı vardır
    * vs.

    Dolayısıyla, sonuç olarak satıcının (n-1)!/2 \, değişik tur arasından seçim hakkı olacaktır. Bu, 100 şehirlik bir tur için bile 9,33 * 10 ^ { 157 } \, değişik tur etmektedir!

    Su an itibariyle, bulunabilmiş en güçlü kesin cozum sunan algoritma (Dinamik Programlama)ile O (n ^ { 2 } * 2 ^ { n }) \, zamanda çözulebilmektedir. Mesela, 100 şehirlik bir tur için bu 1,26 * 10 ^ {30} \, adım etmektedir.

    Bugüne kadar çözülen en büyük seyyar satıcı problemi 24,978 noktalıdır ve İsveç'te yerleşimi olan her nokta için çözülmüştür. Bu çözüm, Intel Xeon 2.8 ghz bir işlemcinin 92 yılına denk bir sürede yapılmıştır (öte yandan, 96 bilgisayarlı bir ağ üzerinde çözüldüğünden çözülmesi 3 yıl sürmüştür). Şu anda çözülmeye çalışılan en büyük problem Dünya üzerinde kayıtlı yerleşim olan her nokta için en kısa yolun ne olduğudur. Bu problem 1,904,711 şehir içermektedir.

    Bu problem, seyyar satıcılardan öte internet üzerinde paketlerin yönlendirilmesi gibi konuların çözümünde de faydalı olacağından önemli bir problemdir.