Pishiriqlar texnikasi - Bakers technique - Wikipedia

Yilda nazariy informatika, Beykerning texnikasi loyihalashtirish usuli hisoblanadi polinom-vaqtni taxminiy sxemalari (PTAS) bo'yicha muammolar planar grafikalar. Uning nomi berilgan Brenda Beyker, uni 1983 yilgi konferentsiyada e'lon qilgan va ACM jurnali 1994 yilda.

Beykerning texnikasi g'oyani grafikani qatlamlarga ajratishdir, shunda muammo har bir qatlamda optimal tarzda echilishi mumkin, so'ngra har bir qatlamdan echimlarni oqilona birlashtirib, natijada amalga oshiriladigan echimga olib keladi. Ushbu uslub PTAS-larga quyidagi muammolar uchun javob berdi: subgraf izomorfizmi, maksimal mustaqil to'plam, minimal vertikal qopqoq, minimal ustunlik to'plami, eng kam chekka ustunlik to'plami, maksimal uchburchakni moslashtirish va boshqalar.

The ikki o'lchovlilik nazariyasi ning Erik Demeyn, Fedor Fomin, Hojiagayi, va Dimitrios Thilikos va uning tarmog'i parchalanishni soddalashtirish (Demain, Xojiagayi va Kavarabayashi (2005),Demain, Xojiagayi va Kavarabayashi (2011) ) Beyker texnikasining ko'plab muammolarni hal qilish uchun ishlatilishini umumlashtiradi va sezilarli darajada kengaytiradi planar grafikalar va umuman olganda qat'iy belgilangan voyaga etmaganlar bundan mustasno, masalan, cheklangan turdagi grafikalar, shuningdek, kabi kichik yoshdagi bolalarni qabul qilish ostida yopilmagan boshqa grafikalar sinflariga 1-planar grafikalar.

Texnika namunasi

Beykerning texnikasini namoyish qilishda foydalanadigan misol - bu maksimal vazn mustaqil to'plam muammo.

Algoritm

MUSTAQIL SET (, , ) Ixtiyoriy vertexni tanlang         uchun birinchi qidiruv darajalarini toping  ildiz otgan  :     uchun         tarkibiy qismlarini toping  ning  o'chirgandan so'ng     uchun        hisoblash , maksimal og'irlikdagi mustaqil to'plam         ruxsat bering  orasida eng katta vaznning echimi bo'ling     qaytish 

E'tibor bering, yuqoridagi algoritm mumkin, chunki har biri ajratilgan mustaqil to'plamlarning birlashishi.

Dinamik dasturlash

Dinamik dasturlash har biri uchun maksimal og'irlikdagi mustaqil to'plamni hisoblashda ishlatiladi . Ushbu dinamik dastur ishlaydi, chunki har biri a - rejadan tashqari grafik. NP bilan to'ldirilgan ko'plab muammolarni dinamik dasturlash bilan hal qilish mumkin - rejadan tashqari grafikalar. Beykerning texnikasi berilgan planar grafikalarni ushbu turdagi subgrafalar bilan qoplash, har bir subgrafga echimini dinamik dasturlash yordamida topish va echimlarni yopishtirish deb talqin qilinishi mumkin.

Adabiyotlar

  • Beyker, B. (1994), "Planar grafikalar bo'yicha NP to'liq muammolarini taxminiy algoritmlari", ACM jurnali, 41 (1): 153–180, doi:10.1145/174644.174650, S2CID  9706753.
  • Beyker, B. (1983), "Planar grafikalar bo'yicha to'liq yakuniy muammolarni algoritmlari", Fokuslar, 24.
  • Bodlaender, H. (1988), "Kengligi chegaralangan grafikalar bo'yicha dinamik dasturlash", ICALP, Kompyuter fanidan ma'ruza matnlari, 317: 105–118, doi:10.1007/3-540-19488-6_110, ISBN  978-3-540-19488-0.
  • Demain, E.; Hojiagayi, M .; Kavarabayashi, K. (2005), "Algoritmik grafik nazariyasi: parchalanish, yaqinlashish va rang berish" (PDF), Fokuslar, 46: 637–646, doi:10.1109 / SFCS.2005.14, ISBN  0-7695-2468-0, S2CID  13238254.
  • Demain, E.; Hojiagayi, M .; Kavarabayashi, K. (2011), "H-minorasiz grafikalar va algoritmik dasturlarda qisqarish dekompozitsiyasi", STOC, 43: 441, doi:10.1145/1993636.1993696, hdl:1721.1/73855, ISBN  9781450306911, S2CID  16516718.
  • Demain, E.; Hojiagayi, M .; Nishimura, N .; Ragde, P .; Thilikos, D. (2004), "Graflar sinflari uchun taxminiy algoritmlar, bir chiziqli grafikalarni voyaga etmaganlar bundan mustasno.", J. Komput. Syst. Ilmiy ish., 69 (2): 166–195, doi:10.1016 / j.jcss.2003.12.001.
  • Eppshteyn, D. (2000), "Kichik yopiq grafikali oilalarda diametri va kengligi.", Algoritmika, 27 (3): 275–291, arXiv:matematik / 9907126v1, doi:10.1007 / s004530010020, S2CID  3172160.
  • Eppshteyn, D. (1995), "Planar grafikalardagi subgraf izomorfizmi va u bilan bog'liq muammolar.", SODA, 6.
  • Grigoryev, Aleksandr; Bodlaender, Xans L. (2007), "Bir chekkada bir nechta o'tish joylari bo'lgan ko'miladigan grafikalar algoritmlari", Algoritmika, 49 (1): 1–11, doi:10.1007 / s00453-007-0010-x, hdl:1874/17980, JANOB  2344391, S2CID  8174422.