| |
|
31 Mart 2012, 19:24
| #1 | |
| Çevrimdışı  IF Ticaret Sayısı: (0) | Seyyar Satıcı Problemi Seyyar satıcı problemi yöneylem araştırması ve teorik kompüter bilimi alanlarında incelenen bir "kombinatorik optimizasyon" problemidir. Seyyar satıcı problemi şu şekilde tanımlamabilir: * Bir seyyar satıcı var; * Bu satıcı, mallarını Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. * ş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 şehire maksimum bir kere ugrayarak turlamak istiyor. Problemin amacı, satıcıya bu en kısa yolu sunabilmektir. Bu problem bir matematiksel problem olarak 1930lu yillarda formule edilmistir. Optimazisyon konusunda en derin inceleme konusu olan problem oldugu hic suphesizdir. "Hesaplamanin karmsikligi" teorisenie gore cozumu NP-Tam olan en önemli algoritma problemlerinden biridir. Bundan dolayi seyyar satici problemelrini etkin olrak cozebilecek bir algoritma olmadigi kabul edilmektedir. Diger bir deyimle en fena hallde algoritma kullanilirken yapilan hesaplarin sayisinin (yani komputer kullanma zamaninin) sehri sayilari arttikca ussel olarak artmasi cok olasidir. Bazi hallerde sadece yuz kadar sehirlik liste olmasina ragmen cozum yapilirken bir komputer ana bellek kullanimi yillar alabilecegi iddia edilmektedir. Diger optimizasyon problemlerine bir nirengi noktasi ve bir mihenk tasi gibi yol gosterici ve degerleyici problem olarak kullanilmaktadir. Problem sonucunu hesaplama cok zor olmakla beraber hem tam sonuc verebilecek ve hem de "sezgisel (heuristic)" sonuclar verebilecek bircok cozum yontemi bilinmektedir ve pratikte bazan onbinlerce sehri ihtiva eden listelerden olusan problemlerin cozulebilcegi bilinmektedir. Basit bir şekilde: * Başlangıç için seçebileceği Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. # değişik şehir vardır # İlk şehirde, satıcının Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. # değişik şehir arasında seçim hakkı vardır # İkinci şehirde, satıcının Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. * değişik şehir arasında seçim hakkı vardır * vs. Dolayısıyla, sonuç olarak satıcının Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. değişik tur arasından seçim hakkı olacaktır. Bu, 100 şehirlik bir tur için bile Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. değişik tur etmektedir! Su an itibariyle bulunabilmiş en güçlü kesin çözüm sunan algoritma (Dinamik Programlama)ile Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. zamanda çözulebilmektedir. Mesela, 100 şehirlik bir tur için bu Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. 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. | |
| |  |
| IRCForumlari.NET Reklamlar |
   |
 |
| Etiketler |
| problemi, satıcı, seyyar |
| Konuyu Toplam 1 Üye okuyor. (0 Kayıtlı üye ve 1 Misafir) | |
| |
Benzer Konular | ||||
| Konu | Konuyu Başlatan | Forum | Cevaplar | Son Mesaj |
| 'Dilenci, satıcı ve aile hekimi giremez' | System | Sağlık Köşesi | 0 | 05 Kasım 2011 08:19 |
| Seyyar Jilet'ci. | viruS | Komik Loglar | 3 | 05 Eylül 2006 01:11 |
Normal
