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
- A lagrangean heuristic for the two-stage modular capacitated facility location problem
İki seviyeli modüler kapasiteli tesis yerleşimi problemi için bir lagrange sezgiseli
SELİM SEVİNÇ
Yüksek Lisans
İngilizce
2008
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. SEDEF MERAL
- Solving a modified TSP problem by a greedy heuristic for cost minimization
Modifiye bir gezgin satıcı problemi için açgözlü bir sezgisel ile maliyet minimizasyonu
MURAT ÇAL
Yüksek Lisans
İngilizce
2017
Endüstri ve Endüstri MühendisliğiÖzyeğin ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ALİ EKİCİ
- Montaj oran kısıtları ve renk kısıtlarını içeren araç sıralama problemi için sezgisel bir yaklaşım ve uygulama
A heuristic for car sequencing problem including assembly ratio constraints and color constraints and application
EMEK GAMZE KÖKSOY
Yüksek Lisans
Türkçe
2014
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. EMRE ÇEVİKCAN
- Determining the best settings for the operators and parameters of genetic algorithms: A methodology and its application to traveling salesperson problem
Genetik algoritmaların operatörleri ve parametreleri için en iyi ayarları belirleme: Bir metodoloji ve gezgin satıcı probleminde uygulaması
YAVUZHAN AKDURAN
Yüksek Lisans
İngilizce
2020
Endüstri ve Endüstri MühendisliğiHacettepe ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. MURAT CANER TESTİK