On a greedy heuristic for the Steiner forest problem
Steiner ormanı problemi için açgözlü bir sezgisel
- Tez No: 374424
- Danışmanlar: YRD. DOÇ. DR. ALİ ÇİVRİL
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2014
- Dil: İngilizce
- Üniversite: Melikşah Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Steiner ormanı problemi onlarca yıldır yaklaştırma algoritmaları ve kombinatoryel optimizasyon alanındaki önemli NP-Tam problemlerden biridir. Bu çalışmada, Steiner ormanı problemi için minimum bir tarayan ağaç bulma problemini çözen açgözlü algoritmalardan esinlenen üç adet sezgisel algoritma geliştiriyoruz. Rastgele geometrik çizgeler ve gerçek dünya geometrik çizgeleri üzerindeki deneysel sonuçlara göre algoritmalarımız Agrawal, Klein ve Ravi'nin ünlü 2 yaklaşık algoritması ve geniş bir şekilde kullanılan açgözlü sezgisel algoritma ile karşılaştırılabilir kalitede çözümler veriyor. Özellikle, gerçek dünya geometrik çizgeleri için algoritmalarımız benzer maliyetlerle çok daha iyi çalışma zamanı veriyor.
Özet (Çeviri)
The Steiner forest problem is one of the important NP-Complete problems in the field of approximation algorithms and combinatorial optimization through decades. In this work, we devolop three heuristics for Steiner forest problem inspired by the greedy algorithms for the problem of finding a minimum spanning tree. According to the experimental results on random geometric graphs and real-world geometric graphs, our algorithms yield solutions of comparable quality to that of the famous 2-approximate algorithm of Agrawal, Klein and Ravi, and a widely used greedy heuristic. Especially, for real-world geometric graphs they yield much better running time with similar costs.
Benzer Tezler
- On a greedy heuristic for the multicommodity rent-or-buy problem
Çoklu eşya satın al ya da kirala problemine aç gözlü bir sezgisel
OSMAN MELİH KÜRTÜNCÜ
Yüksek Lisans
İngilizce
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMelikşah ÜniversitesiElektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ALİ ÇİVRİL
- Ovulasyon indüksiyonu tedavisinde folliküler gelişimin ultrasonografik takibi
Başlık çevirisi yok
MERİH BAYRAM
Tıpta Uzmanlık
Türkçe
1987
Kadın Hastalıkları ve DoğumGazi ÜniversitesiKadın Hastalıkları ve Doğum Ana Bilim Dalı
DOÇ. DR. MÜLAZIM YILDIRIM
- Çimentonun sertleşmesi üzerinde kimyasal komponentlerin etkisi
Başlık çevirisi yok
NACİYE TÜRKEL
Yüksek Lisans
Türkçe
1986
Kimya MühendisliğiUludağ ÜniversitesiKimya Ana Bilim Dalı
PROF. DR. MUSTAFA CEBE
- İzmir'de bazı yolların kapatılarak yaya bölgeleri oluşturma da kent peyzajını geliştirme açısından yeniden planlanması üzerinde araştırmalar
Başlık çevirisi yok
BAHAR TÜRKYILMAZ
Yüksek Lisans
Türkçe
1985
Şehircilik ve Bölge PlanlamaEge ÜniversitesiŞehir ve Bölge Planlama Ana Bilim Dalı
- Atherosklerotik kalp hastalıklarında risk faktörleri
Risk factors in the coronary artery disease
MURAT SUHER