Transcript
V EGE ÜNİVERSİTESİ FEN BİLİMLERİ ENSTİTÜSÜ (DOKTORA TEZİ) MİNİMAL AĞIRLIKLI DOMİNANT ALT KÜME PROBLEMİ (MADAK) ÜZERİNE Burak ORDİN Matematk Ana Blm Dalı Blm Dalı Kodu: Sunuş Tarh: Tez Danışmanı: Doç. Dr. Urfat G. NURİYEV Bornova - İZMİR VI ÖZET MİNİMAL AĞIRLIKLI DOMİNANT ALT KÜME PROBLEMİ (MADAK) ÜZERİNE ORDİN, Burak Doktora Tez, Matematk Bölümü Tez Yönetcs : Doç.Dr.Urfat NURİYEV Ekm 2004, 40 sayfa Son yıllarda Global Optmzasyon problemler nn genş br sınıfı çn Kesen Açılar Yöntem (Cuttng Angle Method) adında yen br yöntem gelştrlmektedr. Bu yöntem teratf olup her adımında kends de yne br Global Optmzasyon problem olan br yardımcı problem n çözülmes gerekr. Bu tezde yukarıda fade edlen Altproblem e denk, Mnmal Ağırlıklı Domnant Alt Küme (MADAK) sml yen br Kombnatoryal Optmzasyon problem tanımlanmıştır. Problemn özellkler ortaya konmuş, bu özellkler göz önüne alınarak çözüm algortmaları önerlmş ve problemn ekonomk yorumu verlmştr. Daha sonra MADAK problem nn graflarla gösterm yapılmış ve Altproblem n çözümü çn MADAK problem yardımıyla çözüm yaklaşımları sunulmuştur. Ayrıca, MADAK problem nn Atama problem nn genel br hal olduğu gösterlp, problemn NP-Tam (NP-Complete) ve Güçlü NP-Tam (NP-Complete n the Strong Sense) sınıftan olduğu spatlanmıştır. Gelştrlen heurstk algortmalarla yapılan hesaplama denemeler de yaklaşımın yararlılığını ortaya koymaktadır. Anahtar sözcükler: Kombnatoryal Optmzasyon, Global Optmzasyon, Kesen Açılar Yöntem, Mnmal Ağırlıklı Domnant Alt Küme Problem, Heurstk Algortma, Atama Problem, Greedy Algortma, Tepe Örtüsü Problem, Küme Örtüsü Problem, Ağırlıklı Küme Örtüsü Problem. VII ABSTRACT ON DOMINATING SUBSET WITH THE MINIMAL WEIGHT (DSMW) PROBLEM ORDIN, Burak Phd. Thess, Mathematcs Department Supervsor: Assocate Professors Urfat NURİYEV October 2004, 40 pages Recently a new method, whch s called the Cuttng Angle Method (CAM), for solvng a broad class of Global Optmzaton problems has been developed. Ths s an teratve method and n each teraton of the CAM a Subproblem has to be solved, whch s n turn, generally, a global optmzaton problem. In ths thess t s defned a new combnatorcal Domnatng Subset wth the Mnmal Weght (DSMW) problem that s equvalent to the above Subproblem and the propertes of the problem are nvestgated. Then t s proposed the algorthms whch have a rato bounds n polynomal tme, by usng above propertes for solvng the DSMW problem and the economcal nterpretatons of the problem are gven. After that the DSMW problem s presented by graphs and some approaches as usng the DSMW problem are expressed for solvng the Subproblem. In addton the DSMW problem s expressed as a knd of Assgnment problem. It s proved that the DSMW problem s NP- Complete and NP-Complete n the Strong Sense. The computatonal experments show the effectveness of the proposed heurstc algorthms. Key words: Combnatoral Optmzaton, Global Optmzaton, Cuttng Angle Method, Domnatng Subset wth the Mnmal Weght Problem, Heurstc, Assgnment Problem, Greedy Algorthm, Vertex Cover Problem, Set Coverng Problem, Weghted Set Coverng Problem. VIII TEŞEKKÜR Doktora çalışmalarıma başladığımdan tbaren, gerek ders aşamasında ve gerekse tez aşamasında yaptığı eleştr ve önerler, karşılaştığım her türlü sorunlarımda göstermş olduğu anlayış ve büyük sabrı çn hocam sayın Doç.Dr. Urfat NURİYEV e en çten teşekkürlerm sunarım. Doktora öğretmm boyunca gösterdkler hoşgörü, destek ve en önemls de sevgler çn matematk bölümü öğretm elemanlarına ve sekreteryasına teşekkürü br borç blrm. Bunun yanısıra, öğrenclk hayatımın her dönemnde ben destekleyen annem Sevm Ordn, babam Al Ordn ve sevgl kardeşm Mehmet Onur Ordn e sonsuz teşekkür ederm. IX İÇİNDEKİLER Sayfa No ÖZET...V ABSTRACT...VII TEŞEKKÜR...IX.GİRİŞ KOMBİNATORYAL OPTİMİZASYON PROBLEMLERİ VE ALGORİTMALARIN KARMAŞIKLIĞI Kombnatoryal Optmzasyon Problemler Tepe Örtüsü Problem Küme Örtüsü Problem Ağırlıklı Küme Örtüsü Problem Atama Problem Algortmaların Karmaşıklığı Algortmaların Analz P ve NP Sınıflar Güçlü NP-Tamlık Kombnatoryal Optmzasyon Problemlernn Çözüm Yöntemler Kesn Çözüm Yöntemler Dal-Sınır Teknğ Dnamk Programlama Heurstk Algortmalar GreedyAlgortmalar Atama Problem nn Çözümü çn Macar Algortmasının Karmaşıklığı Üzerne Küme Örtüsü problemnn çözümü çn Greedy Algortması ve Analz MİNİMAL AĞIRLIKLI DOMİNANT ALT KÜME PROBLEMİ Br Global Optmzasyon Yardımcı Problem...2 X İÇİNDEKİLER(Devam) Sayfa No 3.2. Mnmal Ağırlıklı Domnant Alt Küme Problemnn Ekonomk Yorumu Mnmal Ağırlıklı Domnant Alt Küme Problem çn Bazı Tanımlar Mnmal Ağırlıklı Domnant Alt Küme Problemnn Graflarla Gösterlmes Mnmal Ağırlıklı Domnant Alt Küme Problem nn Atama Problem le Kıyaslanması Mnmal Ağırlıklı Domnant Alt Küme problem nn Ağırlıklı Küme Örtüsü Problem le Kıyaslanması MİNİMAL AĞIRLIKLI DOMİNANT ALT KÜME PROBLEMİ NİN MATEMATİKSEL ANALİZİ Mnmal Ağırlıklı Domnant Alt Küme Problemnn Özellkler Mnmal Ağırlıklı Domnant Alt Küme Problemnn NP-Tam lığının İspatı Mnmal Ağırlıklı Domnant Alt Küme Problem nn Güçlü NP-Tam lığının İspatı MİNİMAL AĞIRLIKLI DOMİNANT ALT KÜME PROBLEMİ İÇİN ÇÖZÜM YAKLAŞIMLARI Mnmal Ağırlıklı Domnant Alt Küme Problem n Çözmek İçn Br Greedy Algortması Greedy Algortmasının Analz Mnmal Ağırlıklı Domnant Alt Küme Problem n Çözmek İçn Greedy Algortmaları nın Kombnasyonu 52 XI İÇİNDEKİLER(Devam) Sayfa No 5.3 Mnmal Ağırlıklı Domnant Alt Küme Problem n Çözmek İçn Heurstk Br Algortma Mnmal Ağırlıklı Domnant Alt Küme Problem n Çözmek İçn Br Başka Heurstk Algortma Hesaplama Denemeler SONUÇ...78 YARARLANILAN KAYNAKLAR...80 EKLER...90 Ek. Tamsayı Elemanlı Grd Matrslern Oluşturmak İçn Program Kodu...90 Ek 2. Reel Sayı Elemanlı Grd Matrslern Oluşturmak İçn Program Kodu Ek 3. Dal&Sınır Yöntemyle Çözüm İçn Program Kodu.96 Ek 4. Heurstk 5.3 le Çözüm İçn Program Kodu...99 Ek 5. Heurstk 5.4 le Çözüm İçn Program Kodu... Ek 6. Heurstk 5.5 le Çözüm İçn Program Kodu...25 ÖZGEÇMİŞ..40 XII. GİRİŞ 997 yılından günümüze Global Optmzasyon problemlernn genş br sınıfını çözmek çn Kesen Açılar Yöntem (Cuttng Angle Method) olarak adlandırılan yen br yöntem gelştrlmeye başlanmıştır (Rubnov, 2000). Kesen Açılar Yöntem konveks mnmzasyonda Kesen Yüzey Metodu (Cuttng Plane Method) nun genelleştrlmes olarak fade edlr ve bu yöntem teratf olup, her adımında yne br global optmzasyon problem olan br Altproblem (yardımcı problem) n çözülmes gerekr. Bu Altproblem n S = x x =, x 0, =,..., n, burada x = ( x,..., x ) n = kümes üzernde tanımlı br derecel, poztf, artan homoen fonksyonların mnmzasyonunda ortaya çıkar. Br Global Optmzasyon problem nn Kesen Açılar Yöntem le çözümünde Altproblem n çözümü çn kullanılan metodun y olması çözümün hızlı bulunmasını etkler. Bugüne kadar Altproblem n çözümü çn gelştrlen metodlar, problemn tanım kümes büyüdükçe problemn büyüklüğüne göre polnomal olmayan zamanlar da çözüm üreteblmektedr. Bu tezde, yukarıda sözü geçen Altproblem e denk olan Mnmal Ağırlıklı Domnant Alt Küme (MADAK) Problem olarak adlandırdığımız yen br boole değşkenl kombnatoryal optmzasyon XIII problem tanımlanıp, özellkler verlmş ve problemn ekonomk yorumu fade edlmştr. Daha sonra se problemn graflar la gösterm yapılmıştır. NP-Tam sınıftan (aynı zamanda güçlü NP-Tam sınıftan) olduğu spatlanan MADAK problem çn gelştrlen algortmaların, Altproblem n çözümü çn kullanılması Global Optmzasyon problemler nn Kesen Açılar Yöntem yle çözümünde büyük yarar sağlamaktadır. Bunun yanısıra MADAK problem br şe br şlem noktasının karşı getrldğ Atama problem le kıyaslandığında br şe brden fazla şlem noktasının atanablrlğ sebebyle Atama problem nn genel br haldr. Atama problem nn çözümü çn polnomal zamanlı Macar algortması (Hungaran Method) blnmektedr, ama MADAK problem NP-Tam sınıftan olup çözümü çn heurstk algortmaların gelştrlmes önem taşımaktadır. MADAK problem nde şler kümesndek bütün elemanların, seçlen alt kümeler yardımıyla örtülmes stendğnden bu problem aynı zamanda br Ağırlıklı Küme Örtüsü problemdr ve Küme Örtüsü problemler çn gelştrlen algortmalar MADAK problem nn çözümüne uyarlanablr. Bu tez grş zleyen dört bölümden oluşmaktadır. XIV İknc bölümde; Optmzasyon problem nn tanımı verlp, türler fade edlmş ve bu tezde kullanılacak bazı optmzasyon problemler ncelenmştr. Daha sonra algortmaların analz ve P, NP sınıf kavramları açıklanıp, kombnatoryal optmzasyon problemler nn çözüm yöntemler ele alınmıştır. Üçüncü bölümde; Global Optmzasyon problemler nn Kesen Açılar Yöntem yle çözümünde karşılaşılan br Altproblem fade edlp, bu Altproblem e denk yen br problem olan Mnmal Ağırlıklı Domnant Alt Küme (MADAK) problem tanımlanmıştır. Matematksel model verlen problem e at bazı tanımlar ortaya konup, problemn graflar la gösterm yapılmıştır. Bu bölümde ayrıca, MADAK problem nn Atama problem ve Ağırlıklı Küme Örtüsü problem le kıyaslaması verlmştr.. Dördüncü bölümde, MADAK problem nn Matematksel analz yapılıp, NP-Tam ve Güçlü NP-Tam sınıftan olduğu spatlanmıştır. Son bölümde; MADAK problemnn çözümü çn dört değşk heurstk algortma önerlmştr. Önerlen algortmalar farklı boyutlardak problemlere uygulanıp, hesaplama denemeler yapılmış ve sonuçların Dal&Buda yöntemndek sonuçlarla kıyaslamaları sunulmuştur. Bu tezde yen br NP-Tam Kombnatoryal Optmzasyon problem tanımlanıp, bu problem çn çözüm yöntemler ncelenmştr. Tanımlanan problem yardımıyla NP-Tam sınıftan olan yardımcı problem n çözümünde yen ve etkn br çözüm yaklaşımı sunulmuştur. XV 2. KOMBİNATORYAL OPTİMİZASYON PROBLEMLERİ VE ALGORİTMALARIN KARMAŞIKLIĞI Bu bölümde, Kombnatoryal Optmzasyon problem tanımlanıp, lerleyen bölümler de kullanılacak bazı optmzasyon problemler verlmştr. Bunun yanısıra algortmaların analz konusuna değnlmş ve kombnatoryal optmzasyon problemler nn çözümünde önem arz eden bazı sınıflar ncelenmştr. 2.. Kombnatoryal Optmzasyon Problemler Optmzasyon problemler k kategorde ncelenr: Sürekl değşkenller ve Dskrt (yada Kombnatoryal) değşkenller (Papadmtrou and Stegltz, 982). Sürekl değşkenl problemler de genellkle reel sayıların br kümes üzernde tanımlı br fonksyon araştırılır. Kombnatoryal problemler de se sonlu br kümeden br nesne yada sayılablr sonsuz br küme (tpk olarak br tamsayılar kümes, permütasyonlar kümes yada graflar) üzernde tanımlanmış br fonksyon araştırılır. Bu problemler oldukça farklı özellklere sahp olup çözümler çnde kullanılan metotlar oldukça farklıdır. Br optmzasyon problemnn tanımı aşağıdak gb verleblr. XVI Tanım 2... F herhang br küme (uygun noktalar kümes), c se + c : F R tanımlı malyet fonksyonu olsun. Burada optmzasyon problemnn br örneğ (F,c) kls şeklnde verlr. Problem, y F çn c( f ) c( y) olacak şeklde br f F elemanının bulunmasıdır. Böyle br f noktasına verlen br örnek çn br global optmal çözüm adı verlr. Tanım I br optmzasyon problemnn örneğ olmak üzere, Π = I şeklnde verlen örnek (breysel) optmzasyon problemler kümesne optmzasyon problem denr. İlerleyen bölümlerde kullanılacak olan bazı optmzasyon problemler aşağıda tanımlanmıştır Tepe Örtüsü Problem (TÖP) V ve E sırasıyla tepeler le ayrıtlar kümesn göstermek üzere br G=(V, E) grafı verlsn. Bu problemde, K V (K 0 herhang br tamsayı) olacak şeklde G grafının elemanları sayısı K dan küçük olan br tepe örtüsü var mı? sorusuna yanıt aranır. Yan TÖP de stenlen, C K çn, her [ u, v] E v C yada u C olacak şeklde C V tepeler kümesnn bulunmasıdır (Garey and Johnson, 979). XVII Küme Örtüsü Problem (KÖP) KÖP de, verlen br X kümes çn, bu kümenn alt kümelernn öyle br F ales alındığında bu aledek kümelern brleşm kümes X kümesne karşı gelsn, X=U S s F Amaç, X n tüm elemanlarını örten mnmum boyutlu br C F altkümesnn bulunmasıdır (Cormen et al., 200). X=U S s C Bu problem çoğu kaynak seçm problemn modelleyen br optmzasyon problemdr ve çok yaygınca artan kombnatoryal problemlern br genellemesdr. Farzedelm k, X br problem çözmek çn gerekl olan yeteneklern kümes olsun. Problem üzernde çalışmaya uygun nsanların br kümes verldğnde, mümkün olduğunca az sayıda nsan çeren br topluluğun oluşturulması küme örtme problemnn temel br örneğ olarak verleblr. Örnek 2... X = x, x,..., kümes verlsn. 2 x2 F = S = x, x2, x3, x4, x5, x6, S 2 = x5, x6, x8, x9, S3 = x, x4, x7, x0, S = x, x, x, x, x, S = x, x, x, x, S = x, x XVIII kümesnden br C F küme örtüsü C=S 3, S 4, S 5 şeklnde verleblr (Bkz Şekl 2..). S x x 2 x 3 x 4 x 5 x 6 S 2 x 7 x 8 x 9 x 0 x x 2 S 6 S 3 S 4 S 5 Şekl 2... Küme Örtüsü Problem Ağırlıklı Küme Örtüsü Problem (AKÖP) KÖP ele alındığında farzedelm k, F ales çndek her br S kümesne br w ağırlığı karşı getrlsn ve br C örtüsünün ağırlığı S C w şeklnde tanımlansın. Problemn amacı verlen koşullar altında br mnmum ağırlıklı örtü belrlemektr (Cormen et. Al., 200). KÖP w ağırlıkları ken AKÖP ün özel br hal olarak düşünüleblr Atama Problem (AP) Br ş noktasına br şlem noktasının (şgören, şlemc, vb...) karşı getrldğ problemler Atama Problem olarak adlandırılır. XIX Matematksel model, n = x =, =,...,n, (2..4.) n = x =, =,..., n, (2..4.2) x = 0 veya, =,..., n; =,..., n, (2..4.3) k.a. Eny c x. (2..4.4) x 0 = şeklnde fade edlr. Bu problem de verlen x ler aşağıdak gb tanımlanıp, x.ş. şleme atandığında = 0 aks halde c ler se. nc şn. nc şleme verlmesnn sstem etknlğne katkısını (kar, malyet, zaman, vb ) gösterr (Kara, 2000). AP nn çözümü çn en etkn yöntemlerden br Macar Algortması dır (Papadmtrou and Stegltz, 982). 2.2. Algortmaların Karmaşıklığı XX Algortmaların Analz Optmzasyon problemlernde değşken ve kısıt sayıları problemlern büyüklüğünü belrlemede yeterldr. Br graf problemnde se düğüm ve ayrıt sayısı büyüklüğü belrler. Buna benzer bçmde her problemn büyüklük parametrelern tanımlayablrz. Bu büyüklük parametrelern tanımlamada amaç, algortmaların problemler çözmede alacağı zamanı bu parametrelern br şlev olarak göstermektr (Papadmtrou and Stegltz, 982). Artmetk şlemlern ve karşılaştırma şlemler gb bast şlemlern blgsayarda sabt zaman aldığını varsayarak algortmanın alacağı zamanı yalnızca problemn büyüklük parametreler cnsnden yazablrz. Br algortmanın zaman karmaşıklığı, aşağıda tanımlanan asmtotk notasyona göre karmaşıklık mertebesn gösteren br fadedr. Tanım (Cormen, et al., 200) f(n) ve g(n), Z + R + e tanımlı fonksyonlar olsunlar. Eğer n n0 (n ve n 0 poztf sabtler) çn f ( n) c. g( n) olacak şeklde öyle br c 0 sabt varsa f ( n) = O( g( n)) olarak yazılıp, f(n) fonksyonları O(g(n)) le asmtotk olarak üstten sınırlıdır şeklnde fade edlr.. Tanım m ve n br optmzasyon problemnn büyüklük parametreler olmak üzere T: Z Z R e tanımlı br fonksyon olsun. Buna göre br optmzasyon problemn çözen br algortmanın XXI süresel karmaşıklığı O(G(m,n), T ( m, n) C. G( m, n) koşulunu sağlayan herhang br şlevdr. Burada C sabt br sayı ve T(m,n) se süresel karmaşıklık fonksyonudur. İlk olarak J. Edmons tarafından ortaya atılan y-kötü algortma ayrımının test şte bu süresel karmaşıklığa dayandırılmaktadır. Br algortma eğer süresel karmaşıklığı, büyüklük parametrelernn br polnomu se y kabul edlmektedr. P herhang br polnom ken, zaman (süresel) karmaşıklığı O(p(n)) olan algortmalara polnomal (polnom sınırlı) algortmalar denr (Örneğn, karmaşıklığı O(m 3.n 2 ), O(m.n+n 3 ) v.b...olanlar). Bunların dışındak algortmalar se polnom sınırlı olmayan (exponental) algortmalar adını alır (Örneğn, karmaşıklığı O(2 n ), O(m!.n!), v.b.olanlar) P ve NP Sınıflar Her br Optmzasyon problemn aşağıda fade edlen tanıma problem gb yazmak mümkündür (Garey and Johnson, 979). Tanım Evet yada Hayır şeklnde yalnızca k cevabı olan problemlere Tanıma problem ler adı verlr. Tanıma problemler genellkle k kısımdan oluşan standart bçmde fade edlrler. Brnc kısımda problemn koşulları graf, fonksyon ve benzer termlerle verlr, knc kısımda se cevabı evet yada hayır olan soru fade edlr. XXII Tanıma problemler karmaşıklıklarına göre sınıflandırılırlar. Eğer br tanıma problem polnom zamanda çözüm veren br algortma le çözüleblyorsa bu durumda bu problem P sınıftandır. P sınıf algortmalar çn matematksel form Turng maknaları tarafından tanımlanır. Br Turng maknası sağdan ve soldan sonsuz uzunluğa sahp ve eşt hücrelere bölünmüş br şert, dare kısmı ve br de okuyucu/yazıcı başlıktan meydana gelr. Makna br başlangıç durumundan tbaren çalışmaya başlar ve grd kümesnden alınan br kelmenn her sembolü çn br çıktı üretr. Makne q Y ve q N olmak üzere k durumdan brne gelndğnde çalışmasını sonlandırır. Bu durumlardan brncs Evet, kncs Hayır anlamını taşır. Br Turng maknasına verlen br x grds çn, makna anlamını, q Y durumunda sonlanıyorsa o grdy kabul edyor q N durumunda sonlanıyorsa da kabul etmyor anlamını taşır (Garey and Johnson, 979; Papadmtrou and Stegltz, 982). Aşağıda P ve NP sınıf kavramları Turng maknasının k türü olan Determnstk Turng maknası (DTM) ve determnstk olmayan (Nondetermnstc) Turng maknası (NDTM) aracılığında tanımlanmıştır. Tanım br grd alfabes olmak üzere, M programı tarafından * tanınan L M dl = x Σ : M, x ' kabul eder şeklnde verlsn. L M XXIII Buna göre aşağıdak gb tanımlanan dller sınıfına Polnom (P) sınıf adı verlr. P = L : L = L olacak şeklde br polnom zamanlı DTM nın M M programı var dır. Tanım NP (Nonpolnomal) sınıf aşağıdak şeklde tanımlanır. NP = L : L = L olacak şeklde br polnom zamanlı NDTM nn M M programı var dır. NP sınıf, tanıma problemlernn daha genş sınıfı olarak görülür. Br başka fade le P, NP nn br alt kümes dr. Çünkü determnstk olmayan Turng maknası determnstk Turng maknası le çözüleblen tüm problemler çözeblr. Br problemn NP sınıftan olması çn polnom zamanlı bazı algortma larla her br örneğnn cevaplanablmes gerekmez. Temelde gereken şudur: Eğer I br problemn evet cevaplı br örneğ se o zaman burada onun geçerllğn polnom zamanda kontrol edeblen br algortma var demektr. Tanım L ve * Σ L herhang k alfabe üzernde * 2 Σ 2 tanımlı k dl olsun. Öyle br f fonksyonu varsa k f * *, x L f ( x) : L 2 2 ve aşağıda belrtlen ()-() koşulları sağlanıyorsa o zaman L dl L 2 dlne polnomal çevrleblr (ndrgeneblr) denr ve L P L 2 şeklnde gösterlr. XXIV () f fonksyonunu polnomal zamanda hesaplayablen algortma olmalı (f polnomal dr), * ( ) x çn, x L f ( x) L2 sağlanmalı. Polnomal ndrgeneblrlk yardımıyla NP sınıf çnde bazı özel sınıflar tanımlanablr Güçlü NP-Tam lık Tanım NP sınıfındak her br problem, br Π problemne ndrgeneblyorsa Π problem NP-Zor (NP-Hard), aynı zamanda Π nn kendsde NP sınıftan se Π ye NP-Tam (NP-Complete) problem denr. Br başka fadeyle, Π ' ' NP problem çn Π NP ve Π P Π Π NP Tam dır. Lemma L, L NP, L NP Tam ken, L P L L NP Tam dır Verlen lemma ya göre, herhang br problemn NP-Tam olduğunu göstermek çn; ) Π NP, ' ' 2) Π NP Tam ken Π Π, olduğunu göstermek yeterldr. P XXV D Π, Π problem çn tüm örnek problemler kümesn göstermek + üzere Length: D Π Z fonksyonu I örnek problemnn br kodlama şemasında kodlamak çn kullanılan sembollern sayısını, Max: + D Π Z fonksyon u da I örnek problem nde kullanılan en büyük tamsayıyı göstersn. Tanım Her br Π tanıma problem ve katsayıları tamsayı olan p polnomu çn Π p le [] I p( Length[ I ]) Max olacak şeklde Π dek breysel (örnek) I problem lernn oluşturduğu alt küme gösterlr. Tanım Verlen br Π problemnde I DΠ çn [] I p( Length[]) I Max olacak şeklde br p polnomu yoksa o zaman Π problem sayısal parametre problem (Number problem) adını alır. Tanım Π P se ve Π p NP Tam olacak şeklde p polnomu varsa, Π problemne güçlü NP-Tam problem denr. Br başka fadeyle, eğer Π NP Tam se ve sayısal parametrel değlse Π problem güçlü NP-Tam sınıf (NP-Complete n the Strong Sense) tandır (Papapdmtrou and Stegltz, 982) KOMBİNATORYAL OPTİMİZASYON PROBLEMLERİNİN ÇÖZÜM YÖNTEMLERİ XXVI Kombnatoryal Optmzasyon problemler çn; çözüm uzayının alt setlere ayrılıp optmallğe götürmeyen çözüm seçeneklernn elendğ Dal-Sınır yöntem, çözüme gderken her aşamanın öncek aşamalar le sırasal lşk çnde olduğu, her br aşamada bulunan çözümün kend başına problemn br çözümü olmadığı ancak optmal çözümün br parçasını belrleyen blgy çerdğ ynelemel br yöntem olan Dnamk programlama yöntem gb kesn çözüm yöntemler gelştrlmştr. Bu yöntemler NP-Tam sınıftan problemler çn üssel zamanlı hesaplama gerektren yöntemlerdr. Bu nedenle belrtlen yöntemlern yanısıra NP-Tam sınıftan olan problemler çn polnomal zamanda çözüm üreteblmek önem taşıdığından, problemn çözümünde bulunulan
