Çevrimiçi algoritma - Online algorithm
Gelen bilgisayar bilimleri , bir çevrimiçi algoritma giriş beslenir sırayla, yani seri şekilde onun giriş parçası bazında parça işleyebilir biridir algoritma baştan mevcut tüm giriş kalmadan.
Tersine, çevrimdışı bir algoritmaya başından itibaren tüm sorun verileri verilir ve eldeki sorunu çözen bir yanıt vermesi gerekir. Gelen yöneylem araştırması , çevrimiçi algoritmalar geliştirdi edildiği bölge denir online optimizasyon .
Örnek olarak, sıralama algoritmalarını seçme sıralama ve ekleme sıralamayı düşünün : seçim sıralaması, sıralanmamış kalandan minimum öğeyi tekrar tekrar seçer ve tüm girdiye erişim gerektiren öne yerleştirir; bu nedenle çevrimdışı bir algoritmadır. Öte yandan, ekleme sıralaması, yineleme başına bir giriş öğesini dikkate alır ve gelecekteki öğeleri dikkate almadan kısmi bir çözüm üretir. Dolayısıyla, ekleme sıralaması çevrimiçi bir algoritmadır.
Bir ekleme sıralamasının nihai sonucunun optimum olduğuna, yani doğru sıralanmış bir liste olduğuna dikkat edin. Çoğu sorun için çevrimiçi algoritmalar, çevrimdışı algoritmaların performansıyla eşleşemez. Çevrimiçi bir algoritmanın performansı ile optimum çevrimdışı algoritma arasındaki oran sınırlandırılmışsa, çevrimiçi algoritmaya rekabetçi denir .
Her çevrimdışı algoritmanın verimli bir çevrimiçi karşılığı yoktur.
Tanım
Tüm girdiyi bilmediği için, çevrimiçi bir algoritma, daha sonra optimal olmayabilecek kararlar almaya zorlanır ve çevrimiçi algoritmaların incelenmesi, bu ortamda mümkün olan karar verme kalitesine odaklanır. Rekabet analizi , aynı sorun örneği için çevrimiçi ve çevrimdışı bir algoritmanın göreceli performansını karşılaştırarak bu fikri resmileştirir. Spesifik olarak, bir algoritmanın rekabetçi oranı, tüm olası girdiler üzerinden maliyetinin en kötü durum oranının optimum maliyete bölümü olarak tanımlanır. Çevrimiçi bir sorunun rekabetçi oranı, çevrimiçi bir algoritma tarafından elde edilen en iyi rekabet oranıdır. Sezgisel olarak, bir algoritmanın rekabetçi oranı, bu algoritma tarafından üretilen çözümlerin kalitesi hakkında bir ölçü verirken, bir problemin rekabetçi oranı, bu problem için geleceği bilmenin önemini gösterir.
Diğer yorumlar
Algoritmalara çevrimiçi girdilerle ilgili diğer bakış açıları için bkz.
- akış algoritması : geçmiş girdileri doğru şekilde temsil etmek için gereken bellek miktarına odaklanma;
- dinamik algoritma : çevrimiçi girdilerle ilgili sorunlara çözüm getirmenin zaman karmaşıklığına odaklanma.
Örnekler
Bazı çevrimiçi algoritmalar :
- Ekleme sıralaması
- Algılayıcı
- Rezervuar örneklemesi
- Açgözlü algoritma
- Düşman modeli
- Metrik görev sistemleri
- Oran algoritması
- Sayfa değiştirme algoritması
- Varyansı hesaplamak için algoritmalar
- Ukkonen'in algoritması
Çevrimiçi sorunlar
Çevrimiçi algoritmaların kavramlarını örnekleyen bir sorun, Kanada Yolcu Sorunu'dur . Bu sorunun amacı, bazı kenarların güvenilmez olduğu ve grafikten çıkarılmış olabileceği ağırlıklı grafikte bir hedefe ulaşma maliyetini en aza indirmektir. Ancak, bir kenarın kaldırıldığı ( başarısız olduğu ), gezgin için yalnızca kenarın uç noktalarından birine ulaştığında görünür. Bu problem için en kötü durum, güvenilmez tüm kenarların başarısız olması ve sorunun olağan En Kısa Yol Problemine indirgenmesidir . Rekabetçi analiz yardımıyla problemin alternatif bir analizi yapılabilir. Bu analiz yöntemi için, çevrimdışı algoritma önceden hangi kenarların başarısız olacağını bilir ve amaç, çevrimiçi ve çevrimdışı algoritmaların performansı arasındaki oranı en aza indirmektir. Bu sorun, PSPACE tamamlandı .
Çözüm olarak birden fazla çevrimiçi algoritma sunan birçok resmi sorun vardır :
- k -server problemi
- İş atölyesi planlama sorunu
- Liste güncelleme sorunu
- Haydut sorunu
- Sekreter sorunu
- Oyun ara
- Kayak kiralama sorunu
- Doğrusal arama sorunu
- Portföy seçim sorunu
Ayrıca bakınız
- Dinamik algoritma
- Akış algoritması
- XML için basit API
- Gerçek zamanlı bilgi işlem
- Sıralı algoritma
- Çevrimiçi makine öğrenimi / Çevrimdışı öğrenme
Referanslar
- Borodin, A .; El-Yaniv, R. (1998). Çevrimiçi Hesaplama ve Rekabet Analizi . Cambridge University Press. ISBN 0-521-56392-5 .