Minimal ağırlıklı dominant alt küme problemi (madak) üzerine
Yükleniyor...
Dosyalar
Tarih
2004
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Ege Üniversitesi
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
Son yıllarda Global Optimizasyon problemleriʼnin geniş bir sınıfı için Kesen Açılar Yöntemi (Cutting Angle Method) adında yeni bir yöntem geliştirilmektedir. Bu yöntem iteratif olup her adımında kendisi de yine bir Global Optimizasyon problemi olan bir yardımcı problemʼin çözülmesi gerekir. Bu tezde yukarıda ifade edilen Altproblemʼe denk, Minimal Ağırlıklı Dominant Alt Küme (MADAK) isimli yeni bir Kombinatoryal Optimizasyon problemi tanımlanmıştır. Problemin özellikleri ortaya konmuş, bu özellikler göz önüne alınarak çözüm algoritmaları önerilmiş ve problemin ekonomik yorumu verilmiştir. Daha sonra MADAK problemiʼnin graflarla gösterimi yapılmış ve Altproblemʼin çözümü için MADAK problemi yardımıyla çözüm yaklaşımları sunulmuştur. Ayrıca, MADAK problemiʼnin Atama problemiʼnin genel bir hali olduğu gösterilip, problemin NP-Tam (NP-Complete) ve Güçlü NP-Tam (NP-Complete in the Strong Sense) sınıftan olduğu ispatlanmıştır. Geliştirilen heuristik algoritmalarla yapılan hesaplama denemeleri de yaklaşımın yararlılığını ortaya koymaktadır.
Açıklama
Anahtar Kelimeler
Kombinatoryal optimizasyon, global optimizasyon, kesen açılar yöntemi, minimal ağırlıklı dominant alt küme problemi, heuristik algoritma, atama problemi, greedy algoritma, tepe örtüsü problemi, küme örtüsü problemi, ağırlıklı küme örtüsü problemi., Combinatorial optimization, global optimization, cutting angle method, dominating subset with the minimal weight problem, heuristic, assignment problem, greedy algorithm, vertex cover problem, set covering problem, weighted set covering problem., Matematik A.B.D.
