K-minimal daraxt daraxti - K-minimum spanning tree

Yo'naltirilmagan grafikaga misol chekka xarajatlar bilan
4-MST
6-MST

The k- minimal uzunlikdagi daraxtlar muammosi, o'qigan nazariy informatika, aniq narxga ega bo'lgan daraxtni so'raydi k tepaliklar va kattaroq grafika subgrafasini hosil qiladi. U shuningdek k-MST yoki chetga tortilgan k-kardinallik daraxti. Ushbu daraxtni topish Qattiq-qattiq, lekin uni doimiy ichida taxmin qilish mumkin taxminiy nisbati yilda polinom vaqti.

Muammoni hal qilish

Muammoni kiritish an yo'naltirilmagan grafik uning chekkalarida og'irliklar bilan va a raqam k. Chiqish bilan daraxt k tepaliklar va k − 1 chiqadigan daraxtning barcha qirralari kirish grafigiga tegishli bo'lgan qirralar. Chiqish qiymati uning chekkalari og'irliklari yig'indisidir va maqsad minimal narxga ega bo'lgan daraxtni topishdir. Muammo tomonidan shakllantirildi Lozovanu va Zelikovskiy (1993)[1] va tomonidan Ravi va boshq. (1996).

Ravi va boshq. shuningdek, masalaning geometrik versiyasini ko'rib chiqdi, bu graf muammosining maxsus holati sifatida qaralishi mumkin.Geometrik k- minimal uzunlikdagi daraxtlar muammosi, kirish tekislikdagi nuqtalar to'plamidir. Shunga qaramay, chiqish bilan daraxt bo'lishi kerak k Umumiy sonini minimallashtirgan holda, uning tepalari sifatida nuqtalarning Evklid uzunligi uning qirralari. Ya'ni, bu grafik k- a bo'yicha minimal daraxt daraxti to'liq grafik og'irlik sifatida Evklid masofalari bilan.[2]

Hisoblashning murakkabligi

Qachon k sobit doimiy, k- minimal daraxtlar muammosini hal qilish mumkin polinom vaqti tomonidan a qo'pol kuch bilan qidirish barchasini sinab ko'radigan algoritm k- tepaliklar uchlari, ammo o'zgaruvchan uchun k, k- minimal uzunlikdagi daraxtlar muammosi ko'rsatilgan Qattiq-qattiq tomonidan a kamaytirish dan Shtayner daraxti muammo.[1][2]

Qisqartirish Shtayner daraxti muammosining bir nusxasini kiritadi: tortilgan grafik, uning uchlari pastki qismi terminal sifatida tanlangan. Shtayner daraxti muammosining maqsadi ushbu terminallarni og'irligi iloji boricha kichikroq daraxt bilan bog'lashdir. Ushbu muammoni k- minimal uzunlikdagi daraxt muammosi, Ravi va boshq. (1996) har bir terminalga juda ko'p sonli nol og'irlikdagi daraxtlarni biriktiring t har bir daraxt uchun tepaliklar. (Bilan grafik uchun n tepaliklar va r terminallardan foydalanadilar t = n − r − 1 har bir daraxtga tepaliklar qo'shildi.) Keyin, ular so'raydi k-bu kengaytirilgan grafadagi minimal minimal daraxt k = rt. Ushbu ko'p tepaliklarni a-ga qo'shishning yagona usuli k- yoyilgan daraxt har bir qo'shilgan daraxtdan kamida bitta tepadan foydalanishi kerak, chunki qo'shilgan daraxtlardan bittasi ham o'tkazib yuborilgan bo'lsa, u erda yetarli tepaliklar qolmaydi. Biroq, bu tanlov uchun k, buning uchun mumkin k- barcha terminallarni ulash uchun kerak bo'ladigan asl grafaning chekkalarini kiritish uchun yoyilgan daraxt. Shuning uchun k-minimal shpal daraxti optimal Shtayner daraxtini qo'shilgan daraxtlarning nol og'irlikdagi qirralari bilan birlashtirib, umumiy daraxt hajmini etarlicha katta qilish uchun hosil bo'lishi kerak.[2]

Hatto chekka og'irliklari to'plamga tegishli bo'lgan grafik uchun ham {1, 2, 3}, eng maqbul echim qiymati berilgan chegaradan kichikligini tekshirish To'liq emas. U NP-ni to'ldiradi planar grafikalar. Masalaning geometrik versiyasi ham NP-qattiq, lekin kvadrat ildizlarning yig'indisini taqqoslash qiyin bo'lgani uchun NPga tegishli ekanligi ma'lum emas; Buning o'rniga u kamaytiriladigan muammolar sinfiga kiradi reallarning ekzistensial nazariyasi.[2]

The k-minimal uzunlikdagi daraxtni topish mumkin polinom vaqti chegaralangan grafikalar uchun kenglik va faqat ikkita aniq chekka og'irliklari bo'lgan grafikalar uchun.[2]

Yaqinlashish algoritmlari

Ga maqbul echim topishning yuqori hisoblash murakkabligi tufayli k- minimal daraxt daraxti, muammo bo'yicha olib borilgan tadqiqotlarning aksariyati diqqat markazida bo'lgan taxminiy algoritmlar muammo uchun. Bunday algoritmlarning maqsadi kichik bilan polinom vaqtidagi taxminiy echimni topishdir taxminiy nisbati. Yaqinlashish nisbati hisoblangan eritma uzunligining eng yomon holat uchun maqbul uzunlikka nisbati sifatida aniqlanadi, bu nisbatni maksimal darajada oshiradi. Chunki NP-ning qattiqligini kamaytirish k- minimal darajadagi daraxtlar muammosi barcha echimlarning og'irligini saqlaydi, shuningdek ularni saqlaydi yaqinlashishning qattiqligi muammoning. Xususan, chunki Shtayner daraxti muammosi NP-ga yaqinlashishi qiyin taxminiy nisbati 96/95 dan yaxshiroq,[3] Xuddi shu narsa k- minimal uzunlikdagi daraxtlar muammosi.

Umumiy muammo uchun ma'lum bo'lgan eng yaxshi taxminiy taxminiy nisbatni 2 ga etadi va quyidagicha Garg (2005).[4] Ushbu yaqinlashish asosan primal-dual sxemasiga asoslanadi Goemans va Uilyamson (1992).[5]Kiritish nuqtadagi nuqtalardan iborat bo'lganda Evklid samolyoti (har qanday ikkitasini daraxtga ularning masofasiga teng narx bilan bog'lash mumkin) mavjud a polinom vaqtini taxminiy sxemasi tomonidan ishlab chiqilgan Arora (1998).[6]

Adabiyotlar

  1. ^ a b Lozovanu, D .; Zelikovskiy, A. (1993), "Minimal va chegaralangan daraxt muammolari", Tezele Congresului XVIII al Academiei Romano-Americane, Kishniev, p. 25. Iqtibos sifatida Ravi va boshq. (1996).
  2. ^ a b v d e Ravi, R .; Sundaram, R .; Marathe, M .; Rozenkrantz, D .; Ravi, S. (1996), "Qisqa yoki kichik daraxtlar", Diskret matematika bo'yicha SIAM jurnali, 9 (2): 178–200, arXiv:matematik / 9409222, doi:10.1137 / S0895480194266331, S2CID  8253322. Ushbu asarning dastlabki versiyasi ilgari, Diskret algoritmlar bo'yicha 5-yillik ACM-SIAM simpoziumida, 1994 yil, 546–555-betlarda namoyish etilgan edi.
  3. ^ Chlebik, Miroslav; Chlebíková, Janka (2008), "Grafalardagi Shtayner daraxti muammosi: yaqinlashmaslik natijalari", Nazariy kompyuter fanlari, 406 (3): 207–214, doi:10.1016 / j.tcs.2008.06.046.
  4. ^ Garg, Naveen (2005), "Epsilonni tejash: grafikalardagi k-MST muammosi uchun 2 ga yaqinlik", Hisoblash nazariyasi bo'yicha 37-yillik ACM simpoziumi materiallari, 396-402 betlar, doi:10.1145/1060590.1060650, S2CID  17089806..
  5. ^ Goemans, M.; Uilyamson, P. (1992), "Cheklangan o'rmon muammolari uchun umumiy taxmin texnikasi", Hisoblash bo'yicha SIAM jurnali, 24 (2): 296–317, CiteSeerX  10.1.1.55.7342, doi:10.1137 / S0097539793242618, S2CID  1796896.
  6. ^ Arora, Sanjeev (1998), "Evklidli sayohatchi sotuvchi uchun vaqtni polinomiyasiga yaqinlashtirish sxemalari va boshqa geometrik muammolar", ACM jurnali, 45 (5): 753–782, doi:10.1145/290179.290180, S2CID  3023351.

Tashqi havolalar