Hukmronlik tahlili - Domination analysis

Dominantlik tahlili ning taxminiy algoritm Glover va Punnen tomonidan 1997 yilda kiritilgan uning ishlashini baholashning bir usuli. Klassikadan farqli o'laroq taxminiy nisbati hisoblangan eritmaning sonli sifatini va optimal echim bilan taqqoslaydigan tahlil, hukmronlik tahlili hisoblangan eritmaning darajasini barcha mumkin bo'lgan echimlarning tartiblangan tartibida o'rganishni o'z ichiga oladi. Ushbu tahlil uslubida algoritmga ega deyiladi ustunlik raqami yoki hukmronlik raqami K, agar mavjud bo'lsa K algoritm natijasi eng yaxshi bo'lgan muammoga turli xil echimlar. Hokimiyat tahlili a yordamida ham ifodalanishi mumkin hukmronlik darajasi, bu eritma maydonining berilgan eritmadan yaxshiroq bo'lmagan qismi; bu raqam har doim [0,1] oralig'ida joylashgan bo'lib, katta sonlar yaxshiroq echimlarni ko'rsatmoqda. Dominantlik tahlili eng ko'p hal etilishi mumkin bo'lgan echimlarning umumiy soni ma'lum bo'lgan va aniq echimi qiyin bo'lgan muammolarga nisbatan qo'llaniladi.

Masalan, Sayohat qilayotgan sotuvchi muammosi, lar bor (n-1)! bilan muammo misoli uchun mumkin bo'lgan echimlar n shaharlar. Agar algoritm dominantlik raqamiga (n-1) !, yoki unga teng ravishda hukmronlik koeffitsienti 1 ga yaqin bo'lsa, unda ustunlik soni pastroq bo'lgan algoritmdan afzalroq qabul qilinishi mumkin.

Agar samarali topish mumkin bo'lsa tasodifiy namunalar Muammoni hal qilish maydonchasi, xuddi Sayohat qiluvchi sotuvchi muammosida bo'lgani kabi, u uchun a tasodifiy algoritm yuqori ehtimollik bilan yuqori hukmronlik koeffitsientiga ega bo'lgan echimni topish uchun: shunchaki namunalar to'plamini tuzing va ular orasidan eng yaxshi echimni tanlang. (Qarang, masalan, Orlin va Sharma.)

Bu erda tasvirlangan dominantlik sonini grafaning hukmronlik soni bilan aralashtirib yubormaslik kerak. hukmron to'plam grafikning

So'nggi paytlarda evristikaning samaradorligini baholash uchun hukmronlik tahlili qo'llanilgan maqolalar soni ko'paymoqda. Ushbu turdagi tahlil klassik taxminiy nisbatni tahlil qilish an'analari bilan raqobatlashadigan deb qaralishi mumkin. Ikkala choralar bir-birini to'ldiruvchi sifatida ko'rib chiqilishi mumkin.

Ma'lum natijalar

Ushbu bo'lim ma'lum natijalar bo'yicha texnik so'rovni o'z ichiga oladi.

Vertex Cover

 Yaqinlashmaslik. Ε> 0. bo'lsin P = NP, Vertex Cover uchun dominant soni 3 ^ ((n-n ^ ε) / 3) dan katta bo'ladigan polinom algoritmi yo'q.

Xalta

 Yaqinlashmaslik. Ε> 0 bo'lsin. P = NP bo'lmasa, Knapsack uchun uning dominant raqami 2 ^ (n-n ^ ε) dan katta bo'ladigan polinom algoritmi mavjud emas.

Maksimum to'yinganlik

TSP

Adabiyotlar

  • Glover, F. va Punnen, A. P. (1997). "Sayohat qiluvchi sayohatchining muammosi: yangi echiladigan holatlar va taxminiy algoritmlarni ishlab chiqish bilan bog'liqliklar". J. Oper. Res. Soc. 48 (5): 502–510. doi:10.1057 / palgrave.jors.2600392.CS1 maint: bir nechta ism: mualliflar ro'yxati (havola)
  • Gutin, Gregori va Yeo, Anders (2004). "Dominantlik tahliliga kirish" (PDF). Onlaynda optimallashtirish. Tashqi havola | noshir = (Yordam bering)CS1 maint: bir nechta ism: mualliflar ro'yxati (havola)
  • Orlin, Jeyms B. va Sharma, Dushyant (2002). "Kengaytirilgan mahalla: ta'rifi va tavsifi" (PDF).CS1 maint: bir nechta ism: mualliflar ro'yxati (havola)