Geri Dön

On a greedy heuristic for the Steiner forest problem

Steiner ormanı problemi için açgözlü bir sezgisel

PDF İndir

  1. Tez No: 374424
  2. Yazar: BİLGE KAĞAN DEDETÜRK
  3. Danışmanlar: YRD. DOÇ. DR. ALİ ÇİVRİL
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2014
  8. Dil: İngilizce
  9. Üniversite: Melikşah Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Elektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 87

Ö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

  1. Tez No

    374437

    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

    İngilizce

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMelikşah Üniversitesi

    Elektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. ALİ ÇİVRİL

  2. Tez No

    129158

    Facility location decisions under vehicle routing considerations

    Dağıtım araçları rotası düşünülerek tesis yerleri belirlenmesi

    BARIŞ SELÇUK

    Yüksek Lisans

    İngilizce

    İngilizce

    2002

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. OSMAN OĞUZ

  3. Tez No

    176880

    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

    İngilizce

    2008

    Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. SEDEF MERAL

  4. Tez No

    478625

    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

    İngilizce

    2017

    Endüstri ve Endüstri MühendisliğiÖzyeğin Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ALİ EKİCİ

  5. Tez No

    406540

    Planning of train movements in single track railways

    Tek hatlı demiryollarında tren hareketlerinin planlanması

    GÖKÇE AYDIN

    Doktora

    İngilizce

    İngilizce

    2015

    UlaşımYıldız Teknik Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    DOÇ. DR. İSMAİL ŞAHİN

Geri Dön