ALGORITMLARDA DEKOMPOZITSIYALASH USULLARI.
Hozirgi kunga kelib kompyuter olimlari ko'p sonli masalalarni hal qilishning samarali algoritmlarini olishga imkon beradigan bir qator samarali usullarni ishlab chiqdilar.Samarali algoritmlarni loyihalashtirishning eng muhim va eng keng qo'llaniladigan usuli bu dekompozitsiyalash deb nomlangan uslubdir. Ushbu usul n o'lchamdagi masalaning kichikroq masalalarga shunday parchalanishini ( nazarda
tutadi, shu kichik muammolarning echimlari asosida dastlabki masalaga echimini osongina olish mumkin. Biz ushbu texnikaning birlashma tartiblash yoki ikkilik qidiruv
daraxtlari kabi bir qator foydalanish usullarini yaxshi bilamiz.
Ushbu usulni ko'rsatish uchun taniqli Xanoy minoralari jumboqini ko'rib chiqamiz. Uchta A, B va S novda bor,birinchi navbatda A tayoqchasiga bir nechta disklar tiqiladi: eng katta diametrli disk pastki qismida, yuqoridan esa rasmda ko'rsatilgandek ketma ket kamayib boruvchi disklar ..
Eng kichik n disklarni A tayoqchadan B tayoqchaga o'tkazish muammosini n
o'lchamdagi ikkita kichik muammolardan iborat deb tasavvur qilish mumkin
1 Birinchidan, A tayoqdan S tayoqqa n 1 ta eng kichik disklarni A
tayoqchada qoldirib, ko'chirishingiz kerak Keyin ushbu diskni A dan B ga
ko'chirish kerak Keyin n 1 diskni C burilish joyidan B tayoqchasiga o'tkazish
kerak Ushbu n 1 disklarning harakati belgilangan usulni rekursiv ravishda
qo'llash orqali amalga oshiriladi Ko'chib yurmaydiganlardan kamroq, A, B
yoki S pinlaridagi harakatlanuvchi disklar ostida nima borligi haqida
o'ylashning hojati yo'q, garchi individual disklarning haqiqiy harakati unchalik
aniq ko'rinmasa ham, rekursiv qo'ng'iroq stakalari shakllanishi tufayli qo'lda
simulyatsiya qilish oson emas, kontseptual nuqtai nazardan, ushbu algoritm
hali ham uning to'g'riligini tushunish va isbotlash uchun juda oddiy (va agar
rivojlanish tezligi haqida gapiradigan bo'lsak, unda uning tengi yo'q)
Parchalanish usuli yordamida algoritmlarni ishlab chiqishda qulaylik bu
usulning juda mashhur bo'lishiga olib keldi bundan tashqari, ko'p hollarda
ushbu algoritmlar an'anaviy usullar bilan ishlab chiqilgan algoritmlarga
qaraganda samaraliroq.
Dekompozitsiya usullari algoritm dizaynida murakkab muammolarni kichikroq, boshqariladigan pastki muammolarga ajratish uchun ishlatiladigan usullardir. Muammoni parchalash orqali siz umumiy echim jarayonini soddalashtirishingiz, modullikni yaxshilashingiz va qayta foydalanishni yaxshilashingiz mumkin. Algoritmni loyihalashda ishlatiladigan bir nechta umumiy parchalanish usullari mavjud:
1. **Bo'ling va zabt eting**: bu usul masalani bir xil turdagi kichik kichik muammolarga ajratishni, har bir kichik muammoni mustaqil yechishni, so'ngra yechimlarni birlashtirib, dastlabki masala yechimini topishni o'z ichiga oladi. Bunga misollar birlashtirish saralash, quicksort va ikkilik qidiruv.
2. ** Dinamik dasturlash**: dinamik dasturlash-bu murakkab masalalarni sodda kichik muammolarga ajratish va har bir kichik muammoni faqat bir marta yechish, ortiqcha hisoblashlarning oldini olish uchun kichik muammolarning yechimlarini jadvalda saqlash usuli. Dinamik dasturlash, ayniqsa, subproblems bir-birining ustiga chiqqanda foydalidir, chunki bu echimlarni samarali qayta ishlatishga imkon beradi. Misollarga xalta muammosi va Fibonachchi ketma-ketligini hisoblash kiradi.
3. ** Ochko'z algoritmlar**: ochko'z algoritmlar global optimal topish umidi bilan har bir qadamda lokal optimal tanlovlarni amalga oshiradi. Ushbu algoritmlar har doim ham maqbul echimni kafolatlamaydi, lekin ular ko'pincha maqbul vaqt ichida Maqbulga yaqin echimlarni taqdim etadilar. Bunga misollar kiradi Dijkstra algoritmi grafikdagi eng qisqa yo'lni va minimal daraxt algoritmini topish uchun.
4. ** Yuqoridan pastga va pastdan yuqoriga dizayn**: yuqoridan pastga dizaynda siz umumiy muammodan boshlaysiz va hal qilish oson bo'lgan asosiy holatlarga erishguningizcha uni rekursiv ravishda kichikroq kichik muammolarga ajratasiz. Pastdan yuqoriga dizaynda siz eng kichik subproblems bilan boshlaysiz va katta subproblems uchun echimlarni takroran yaratasiz. Ikkala yondashuv ham muammo va dasturlash paradigmasiga qarab ishlatilishi mumkin.
5. ** Modulizatsiya**: modullashtirish muammoni alohida modul yoki funksiyalarga ajratishni o'z ichiga oladi, ularning har biri ma'lum bir vazifa yoki kichik vazifa uchun javobgardir. Bu kodni qayta ishlatishni targ'ib qiladi, disk raskadrovka va texnik xizmatni soddalashtiradi va o'qishni yaxshilaydi. Ob'ektga yo'naltirilgan dasturlash-bu sinflar va ob'ektlar orqali modulizatsiyani ta'kidlaydigan umumiy paradigma.
6. ** Parallellashtirish**: parallellashtirish masalani bir nechta protsessor birliklari yordamida bir vaqtda yechilishi mumkin bo'lgan mustaqil subproblemalarga ajratishni o'z ichiga oladi. Parallel algoritmlar zamonaviy apparat arxitekturalarining hisoblash kuchidan foydalangan holda keng ko'lamli muammolarni hal qilish uchun zarur bo'lgan vaqtni sezilarli darajada qisqartirishi mumkin.
7. ** Abstraktsiya ierarxiyasi**: bu usul muammoni tobora mavhum qatlamlar ierarxiyasiga ajratishni o'z ichiga oladi, har bir qatlam amalga oshirish tafsilotlarini yashiradi va yuqori darajadagi tushunchalarni ochib beradi. Ushbu yondashuv murakkablikni boshqarishga yordam beradi va modulli dizaynni osonlashtiradi.
Ushbu parchalanish usullari bir-birini istisno qilmaydi va ko'pincha muammoni samarali hal qilish uchun bir nechta usullarni birlashtirish mumkin. Dekompozitsiya usulini tanlash muammoning mohiyatiga, mavjud hisoblash resurslariga va echimning optimalligi, samaradorligi va soddaligi o'rtasidagi kerakli kelishuvlarga bog'liq.
Cheklovni qondirishda dekompozitsiya usuli cheklovni qondirish muammosini ikkilik va asiklik bo'lgan boshqa cheklovni qondirish muammosiga aylantiradi. Dekompozitsiya usullari o'zgaruvchilarni to'plamlarga guruhlash va har bir to'plam uchun kichik muammoni hal qilish orqali ishlaydi. Ushbu tarjimalar ikkilik asiklik muammolarni hal qilish a tortiladigan muammo.
Har bir tarkibiy cheklash konversiyadan keyin muammoni hal qilishning murakkablik o'lchovini aniqladi; bu o'lchov kenglik deb ataladi. Ruxsat etilgan maksimal kenglikni aniqlash-bu cheklovni qondirish muammolari subklassini aniqlashning bir usuli. Ushbu sinfdagi muammolarni echish ko'p parchalanish uchun polinom hisoblanadi; agar bu parchalanish uchun bo'lsa, sobit kenglikdagi muammolar sinfi cheklovni qondirish muammolarining tortiladigan subklassini hosil qiladi.
Dekompozitsiya usullari muammoni yechish osonroq bo'lgan yangisiga aylantiradi. Yangi muammo faqat ikkilik cheklovlarni o'z ichiga oladi ; ularning doiralari yo'naltirilgan asiklik grafikni hosil qiladi . Yangi muammoning o'zgaruvchilari har bir asl o'zgaruvchilar to'plamini ifodalaydi. Bu to'plamlar bir-biridan ajralib turishi shart emas, lekin ular asl o'zgaruvchilar to'plamini qamrab oladi. Tarjima o'zgaruvchilarning har bir to'plamiga nisbatan barcha qisman echimlarni topadi. Tarjima natijasida yuzaga keladigan muammo ushbu mahalliy echimlar o'rtasidagi o'zaro ta'sirni ifodalaydi.
Ta'rifga ko'ra, parchalanish usuli ikkilik asiklik muammoni keltirib chiqaradi; bunday masalalarni uning kattaligi bo'yicha vaqtli ko'phadda yechish mumkin. Natijada, asl muammoni avval uni tarjima qilish va keyin paydo bo'lgan masalani hal qilish orqali hal qilish mumkin; ammo, bu algoritm, agar parchalanish superpolinom darajada kattalashmasa, polinom-vaqt hisoblanadi. Parchalanish usulining kengligi u ishlab chiqargan muammo hajmining o'lchovidir. Dastlab, kenglik asl o'zgaruvchilar to'plamining maksimal kardinalligi sifatida aniqlangan; bir usul, gipertree dekompozitsiyasi, boshqa o'lchovdan foydalanadi. Qanday bo'lmasin, dekompozitsiyaning kengligi doimiy bilan chegaralangan o'lchamdagi parchalanish haddan tashqari katta muammolarni keltirib chiqarmasligi uchun aniqlanadi. Ruxsat etilgan kenglikdagi dekompozitsiyaga ega bo'lgan misollar parchalanish yo'li bilan asl nusxa o'lchamidagi polinom bilan chegaralangan o'lchamdagi misollarga tarjima qilinishi mumkin.
Muammoning kengligi uning minimal kenglikdagi parchalanish kengligidir. Ruxsat etilgan kenglikdagi dekompozitsiyalardan muammoni samarali hal qilish uchun foydalanish mumkin bo'lsa-da, misollar kengligidagi chegara, albatta, qat'iy tuzilmaviy cheklanishni keltirib chiqaradi . Haqiqatan ham, belgilangan kenglik muammosi belgilangan kenglikning parchalanishiga ega, ammo uni topish polinom bo'lmasligi mumkin. Ruxsat etilgan kenglik muammosini parchalanish yo'li bilan samarali hal qilish uchun uning past kenglikdagi parchalanishlaridan birini samarali ravishda topish kerak. Shu sababli, parchalanish usullari va ular bilan bog'liq kenglik ko'pnomli-vaqt bo'lgan muammoni hal qilish uchungina emas, balki qat'iy kenglikdagi masalaning qat'iy kenglikdagi parchalanishini topish polinom- vaqt.
Parchalanish usullari o'zboshimchalikdan hal qilish oson bo'lgan muammoni yaratadi. Ushbu yangi muammoning har bir o'zgaruvchisi asl o'zgaruvchilar to'plami bilan bog'langan; uning domenida bog'langan to'plamdagi o'zgaruvchilar uchun qiymatlar majmuasi mavjud; xususan, bu o'zgaruvchilar ustidan cheklovlar to'plamini qondiradigan kortejlar. Yangi muammoning cheklovlari ikkita yangi o'zgaruvchining qiymatlarini umumiy asl o'zgaruvchilarga mos keladigan ikkita kortej qiymatlari sifatida chegaralaydi. Yana uchta shart yangi muammoning eskisiga teng bo'lishini va samarali hal etilishini ta'minlaydi.
Yangi muammoni samarali yechish uchun yangi muammoning birlamchi grafigi asiklik bo'lishi kerak. Boshqacha qilib aytadigan bo'lsak, o'zgaruvchilarni cho'qqilar va (ikkilik) cheklovlarni qirralar sifatida ko'rish natijasida olingan grafik daraxt yoki o'rmon bo'lishi kerak .
Yangi muammo eskisiga ekvivalent bo'lishi uchun har bir asl cheklov kamida bitta yangi o'zgaruvchining domenini aniqlashning bir qismi sifatida qo'llaniladi. Buning uchun eski muammoning har bir cheklovi uchun yangi muammoning o'zgaruvchisi mavjud bo'lishini talab qiladi, shundayki, uning bog'langan asl o'zgaruvchilar to'plami cheklov doirasini o'z ichiga oladi va uning domenidagi barcha kortejlar cheklovni qondiradi.
Ekvivalentlikni ta'minlash uchun zarur bo'lgan yana bir shart shundaki, ikkilik cheklovlar bir xil qiymatni qabul qilish uchun har bir asl o'zgaruvchining barcha "nusxalari" ni majburlash uchun etarli. Xuddi shu asl o'zgaruvchi bir nechta yangi o'zgaruvchilar bilan bog'lanishi mumkinligi sababli, bu yangi o'zgaruvchining qiymatlari eski o'zgaruvchining qiymatiga mos kelishi kerak. Ikkilik cheklovlar ikki yangi o'zgaruvchilar o'rtasida taqsimlangan eski o'zgaruvchilarning tengligini ta'minlash uchun ishlatiladi. Yangi o'zgaruvchining ikkita nusxasi, agar ularning yangi o'zgaruvchilari o'rtasida ikkilik cheklovlar yo'li mavjud bo'lsa va bu yo'ldagi barcha yangi o'zgaruvchilar eski o'zgaruvchini o'z ichiga olgan bo'lsa, teng bo'ladi.
Misol cheklash qondirish muammosi; bu muammo ikkilikdir va cheklovlar ushbu grafikning qirralari bilan ifodalanadi.
Parchalanish daraxti; asl grafikning har bir chekkasi uchun uning ikkala so'nggi nuqtasini o'z ichiga olgan tugun mavjud; o'zgaruvchini o'z ichiga olgan barcha tugunlar ulanadi
Kichik muammoni hal qilish. Ushbu misol birinchi to'plamning o'zgaruvchilari bo'yicha barcha cheklovlardan iborat kichik muammoni hal qilishni ko'rsatadi
{x,y,z}. Xuddi shunday protsedura boshqa to'plamlar uchun ham amalga oshiriladi
{u,x,z} va {y,w}
Daraxtning har bir tuguniga o'zgaruvchi yasaladi. Uning sohasi - kortejlar to'plami bo'lgan qisman muammoning echimlari to'plami. Yangi muammoning cheklovlari faqat dastlabki o'zgaruvchilarning teng qiymatlarini o'z ichiga olgan kortejlarga ruxsat beradi. Rasmda ning tengligi
{Y}ko'rsatilgan: mos keladigan cheklov faqat ning birinchi korteji tomonidan bajariladi
(
(x, y, z) va birinchi kortej (y,w)}, va ikkinchi kortej bo'yicha (x, y, z) va ikkinchi kortej
(y,w). Bundan tashqari, ikkinchi kortej
(x, y, z)}uning chap bolasida qanoatlangan kortejni topa olmaydi (
(u,x,z)}). Shunday qilib, ikkinchi kortej
(u,x,z)}olib tashlash kerak.
Dekompozitsiya usuli odatda tugunlari yangi muammoning o'zgaruvchilari bo'lgan daraxtni taqdim etish orqali aniqlanadi; Har bir tugun uchun, shuningdek, asl o'zgaruvchilarning bog'langan to'plami va ehtimol yangi muammoda o'zgaruvchining domenini yaratish uchun foydalaniladigan asl cheklovlar to'plami taqdim etiladi. Yuqoridagi uchta shartdan (daraxt tuzilishi, cheklovlarning bajarilishi va asl o'zgaruvchilar nusxalarining ekvivalentligi) birinchisi ushbu ta'rif bilan avtomatik ravishda amalga oshiriladi. Cheklovlarni amalga oshirish sharti asosan quyidagicha ifodalanadi: har bir cheklov doirasi ba'zi tugunning o'zgaruvchilari kichik to'plamidir; biroq, agar tugunlar cheklovlar to'plami bilan bog'langan bo'lsa, boshqa shart qo'llanilishi mumkin. Asl o'zgaruvchilarning barcha nusxalarining ekvivalentligi odatda quyidagicha ifodalanadi: asl o'zgaruvchiga bog'langan tugunlar tomonidan induktsiya qilingan pastki grafik bog'langan.
Ikkilik muammolar uchun parchalanish usullari
Bir qator parchalanish usullari mavjud. Ularning ko'pchiligi misollar kengligini chegaralash orqali tranzit sinfni yaratadi. Quyida ikkilik cheklovlarni qondirish muammolari uchun aniqlangan parchalanish usullari keltirilgan. Muammoni ikkilik muammoga aylantirish yoki yashirin o'zgaruvchilar yordamida ikkilik qilish mumkinligi sababli , bu usullardan bilvosita ixtiyoriy cheklovlarni qondirish muammolari uchun daraxt parchalanishini ta'minlash uchun foydalanish mumkin.
Ikki ulangan komponentlar
Grafik nazariyasida ajratuvchi cho'qqi - bu grafik tugun bo'lib, undan olib tashlanganda grafikni "buzadi". Rasmiy ravishda, bu tugun bo'lib, uning grafikdan olib tashlanishi uning bog'langan komponentlari sonini oshiradi. Grafikning ikki bog'langan komponenti - bu uning tugunlarining maksimal to'plami bo'lib, induktsiyalangan pastki grafigi bog'langan va hech qanday ajratuvchi cho'qqiga ega emas. Grafik nazariyasidan ma'lumki, grafikning ikki bog'langan komponentlari va ajratuvchi uchlari daraxt hosil qiladi. Ushbu daraxtni quyidagicha qurish mumkin: uning tugunlari ikki bog'langan komponentlar va grafikning ajratuvchi uchlari; qirralar faqat ikki bog'langan komponentni ajratuvchi cho'qqi bilan bog'laydi va ayniqsa, bu cho'qqi komponentda bo'lsa sodir bo'ladi. Bu grafik aslida daraxt ekanligini isbotlash mumkin.
Ikkilik cheklovni qondirish muammosining cheklovlari tugunlari o'zgaruvchilar bo'lgan grafikning qirralari sifatida qaralsa, bu daraxt muammoning parchalanishi hisoblanadi. Dekompozitsiyaning kengligi ikki bog'langan komponentdagi tepaliklarning maksimal sonidir.
Tsiklni parchalash usuli muammoni tsiklik va asiklik qismga ajratadi. Tugunlari tugunlar to'plami bilan belgilangan daraxt hosil qiladigan boshqa parchalanish usullarining ta'rifiga to'g'ri kelmasa ham, uni bunday atamalar bilan osongina qayta shakllantirish mumkin.
Ushbu parchalanish usuli, ba'zi o'zgaruvchilarga qiymat berilgandan so'ng, bu o'zgaruvchilar yo'q qilinganidan keyin muammoning qolgan qismi asiklik bo'lishi mumkin degan fikrga asoslanadi. Rasmiy ravishda, grafikning sikl to'plami - bu grafikni undan olib tashlanganda uni asiklik qiladigan tugunlar to'plami. Shunga o'xshash ta'rifni cheklovni qondirish muammosi uchun uning asosiy grafigi yordamida berish mumkin. Tsikl dekompozitsiyasining kengligi - kesiklar to'plamidagi o'zgaruvchilar soni. Muammoning kengligi uning aylanish davrining parchalanishlarining minimal kengligidir.
Bunday parchalanish boshqa parchalanishlar sxemasiga to'g'ri kelmaydi, chunki parchalanish natijasi daraxt emas, balki o'zgaruvchilar to'plami (kesimdagilar) va daraxt (kesimdagi bo'lmagan o'zgaruvchilar tomonidan tuzilgan). Shu bilan birga, boshqa parchalanish usullari bilan hosil qilingan daraxtga o'xshash daraxt kesikni olib tashlash natijasida paydo bo'ladigan daraxtdan olinishi mumkin; bu ildiz tanlash, kesiklar to‘plamining barcha o‘zgaruvchilarini uning barcha tugunlariga va har bir tugunning o‘zgaruvchilarini uning barcha bolalariga qo‘shish orqali amalga oshiriladi. Bu tugun bilan bog'langan o'zgaruvchilarning maksimal soni kesilgan to'plamning o'lchamiga va ikkitaga teng bo'lgan daraxtga olib keladi. Ikki qo'shishdan tashqari, bu parchalanishning kengligi bo'lib, u ko'rib chiqilayotgan kesiklar to'plamidagi o'zgaruvchilar soni sifatida aniqlanadi.
Afsuski, olib tashlash uchun minimal to'plamni aniqlash NP-Hard muammosidir .
Daraxtlarning parchalanishi
Daraxtlarning parchalanishi grafik nazariyasidan mashhur tushunchadir. Ikkilik cheklovlar nuqtai nazaridan qayta tuzilgan, daraxtning parchalanishi tugunlari o'zgaruvchilar to'plami bilan bog'langan daraxtdir; har bir cheklov doirasi ba'zi bir tugunning o'zgaruvchilari to'plamida joylashgan va har bir o'zgaruvchiga bog'langan tugunlarning pastki daraxti ulanadi. Bu yuqorida ko'rsatilgan sxema bo'yicha ikkilik cheklovlar uchun parchalanishning eng umumiy shaklidir, chunki daraxtga qo'yilgan shartlar faqat asl va yangi muammoning ekvivalentini kafolatlash uchun zarur bo'lgan shartlardir.
Bunday parchalanishning kengligi bir xil tugun bilan bog'liq bo'lgan o'zgaruvchilarning maksimal soni minus birdir. Muammoning daraxt kengligi uning daraxt parchalanishining minimal kengligidir .
Paqirni yo'q qilish ma'lum bir daraxt parchalanishida ishlaydigan algoritm sifatida qayta shakllantirilishi mumkin. Xususan, o'zgaruvchilarning tartibini hisobga olgan holda, har bir o'zgaruvchi barcha cheklovlarni o'z ichiga olgan chelak bilan bog'lanadi, shunda o'zgaruvchi o'z doirasidagi eng katta bo'ladi. Paqirni yo'q qilish har bir chelak uchun tugunga ega bo'lgan daraxt parchalanishiga mos keladi. Ushbu tugun o'zining barcha cheklovlari bilan bog'langan va bu cheklovlarning barcha o'zgaruvchilari to'plamiga mos keladi. Paqir bilan bog'langan tugunning ota-onasi
�
�
{\displaystyle x_{i}}chelak bilan bog'langan tugundir
�
�
{\ displaystyle x_ {j}}, qayerda
�
�
{\ displaystyle x_ {j}}bilan chegaralangan eng katta tugundir
�
�
{\displaystyle x_{i}}va oldin
�
�
{\displaystyle x_{i}}buyurtmada.
Ixtiyoriy muammolar uchun parchalanish usullari
Ikkilik yoki boshqacha tarzda ixtiyoriy cheklovlarni qondirish muammosini tarjima qilish uchun quyidagi usullardan foydalanish mumkin. Ular ikkilik masalalarda ham ishlatilishi mumkinligi sababli, ular ikkilik muammoga tarjima qilish yoki yashirin o'zgaruvchilar yordamida cheklovlarni binar qilish natijasida ham ishlatilishi mumkin .
Ushbu usullarning ba'zilari cheklashlarni daraxt tugunlari bilan bog'laydi va tugunlar bilan bog'liq cheklovlar sonini hisobga olgan holda kenglikni belgilaydi. Bu ba'zi muammolarning kengligini kamaytirishi mumkin. Misol uchun, har bir tugun bilan o'nta o'zgaruvchi bog'langan dekompozitsiyaning kengligi o'nga ega; ammo, agar o'nta o'zgaruvchidan iborat ushbu to'plamlarning har biri cheklov doirasi bo'lsa, har bir tugun o'rniga ushbu cheklov bilan bog'lanishi mumkin, natijada kenglik bir bo'ladi.
Ikki ulangan komponentlar
Ixtiyoriy cheklovlarni qondirish muammosining ikki bog'langan parchalanishi uning asosiy grafigining ikki bog'langan parchalanishidir. Har bir cheklov daraxtning tuguniga qo'llanilishi mumkin, chunki har bir cheklov o'z o'zgaruvchilari bo'yicha birlamchi grafikda klik hosil qiladi va klik ikki bog'langan komponent yoki ikki bog'langan komponentning kichik to'plamidir.
Daraxtlarning parchalanishi
Ixtiyoriy cheklovlarni qondirish muammosining daraxt parchalanishi uning asosiy grafigining daraxt parchalanishidir. Har bir cheklov daraxtning tuguniga qo'llanilishi mumkin, chunki har bir cheklov birlamchi grafikdagi o'z o'zgaruvchilari bo'yicha klik hosil qiladi va daraxtning har bir parchalanishi uchun klikning o'zgaruvchilari ba'zi tugunlarning o'zgaruvchilarida to'liq o'z ichiga oladi.
Cycle hypercutsset
Bu gipergraflar uchun kesiklar ta'rifi yordamida sikl kesishishning bir xil usuli: gipergrafning sikl giperksetasi - bu qirralarning to'plami (cho'qqilar emas) va ularning barcha uchlari olib tashlanganida gipergrafni asiklik qiladi. Dekompozitsiyani giperksetning barcha o'zgaruvchilarini bittada guruhlash orqali olish mumkin. Bu tugunlari giperqirralar to'plami bo'lgan daraxtga olib keladi. Bunday parchalanishning kengligi tugunlar bilan bog'liq bo'lgan to'plamlarning maksimal o'lchamidir, agar asl muammo asiklik bo'lsa va aks holda uning minimal giperksetining o'lchami bitta bo'ladi. Muammoning kengligi uning parchalanishlarining minimal kengligidir.
Menteşe parchalanishi
Menteşe - bu quyida tavsiflangan ba'zi xususiyatlarga ega bo'lgan gipergrafik tugunlarning kichik to'plami. Menteşe dekompozitsiyasi gipergrafning minimal ilmoqlari bo'lgan o'zgaruvchilar to'plamiga asoslanadi, ularning tugunlari cheklovlarni qondirish muammosining o'zgaruvchilari va giperqirralari uning cheklovlari doirasi hisoblanadi.
Menteşaning ta'rifi quyidagicha. Mayli
�
{\displaystyle H}giperqirralar to'plami bo'lsin. ga nisbatan yo'l
�
{\displaystyle H}har birining keyingisi bilan kesishishi bo'sh bo'lmagan va tugunlarda mavjud bo'lmagan qirralarning ketma-ketligidir.
�
{\displaystyle H}. ga nisbatan qirralarning to'plami bog'langan
�
{\displaystyle H}agar uning har bir juft chekkasi uchun ga nisbatan yo'l mavjud bo'lsa
�
{\displaystyle H}ulardan ikkita tugun birinchi va oxirgi chekkadir. ga nisbatan bog'langan komponent
�
{\displaystyle H}ga nisbatan bog'langan qirralarning maksimal to'plamidir
�
{\displaystyle H}.
Menteşalar qisqartirilgan gipergraflar uchun belgilanadi, ular gipergraflar bo'lib, boshqasida hech qanday giperqirra mavjud emas. Kamida ikkita qirrali to'plam
�
{\displaystyle H}har bir ulangan komponent uchun menteşedir
�
{\displaystyle F}ga kelganda; .. ga kelsak; .. ning haqida
�
{\displaystyle H}, ichidagi barcha tugunlar
�
{\displaystyle F}ular ham mavjud
�
{\displaystyle H}hammasi bitta chetida joylashgan
�
{\displaystyle H}.
Menteşe dekompozitsiyasi cheklovlarni qondirish muammolari va gipergraflar o'rtasidagi muvofiqlikka asoslanadi. Muammo bilan bog'liq bo'lgan gipergraf muammoning o'zgaruvchilariga ega, chunki tugunlar giperqirralar kabi cheklovlar doirasi hisoblanadi. Cheklovni qondirish muammosining menteşeli dekompozitsiyasi tugunlari muammo bilan bog'liq bo'lgan gipergrafaning ba'zi minimal ilmoqlari bo'lgan va ba'zi boshqa shartlar bajariladigan daraxtdir. Muammolarning gipergraflar bilan mos kelishiga ko'ra, menteşe cheklovlar doiralari to'plamidir va shuning uchun cheklovlar to'plami sifatida qaralishi mumkin. Menteşe dekompozitsiyasini aniqlashning qo'shimcha shartlari uchta bo'lib, ulardan birinchi ikkitasi asl muammoning yangi bilan tengligini ta'minlaydi. Ekvivalentlikning ikkita sharti quyidagilardan iborat: har bir cheklov doirasi daraxtning kamida bitta tugunida joylashgan va asl muammoning o'zgaruvchisi tomonidan induktsiya qilingan pastki daraxt bog'langan. Qo'shimcha shart shundaki, agar ikkita tugun birlashtirilgan bo'lsa, ular aynan bitta cheklovni taqsimlaydilar va bu cheklov doirasi ikkita tugun tomonidan baham ko'rilgan barcha o'zgaruvchilarni o'z ichiga oladi.
Tugun cheklovlarining maksimal soni bir xil muammoning barcha menteşe dekompozitsiyalari uchun bir xil bo'ladi. Bu raqam muammoning aylanish darajasi yoki uning menteşe kengligi deb ataladi .
Daraxtlarni klasterlash
Daraxtlarni klasterlash yoki qo'shilish daraxti klasterlash cheklovlarni shunday birlashtirishga asoslangan bo'lib, natijada yuzaga keladigan muammo qo'shilish daraxtiga ega bo'ladi , bu qo'shilish daraxti parchalanish natijasidir.
Cheklovni qondirish muammosining qo'shilish daraxti - bu har bir tugun cheklovlar bilan bog'langan (va aksincha) va cheklovi o'zgaruvchini o'z ichiga olgan tugunlarning pastki daraxti bog'langan daraxt. Natijada, qo'shilish daraxtini ishlab chiqarishni alohida parchalanish shakli sifatida ko'rish mumkin, bu erda daraxtning har bir tugunini cheklash doirasi bilan bog'lash mumkin.
Barcha cheklovlarni qondirish muammolari birlashma daraxtiga ega emas. Biroq, cheklovlarni birlashtirish orqali birlashma daraxtini olish uchun muammolarni o'zgartirish mumkin. Daraxtlarni klasterlash muammoning birlashtiruvchi daraxtiga ega ekanligiga asoslanadi, agar uning birlamchi grafigi xordal bo‘lsa va muammoga mos bo‘lsa , ikkinchisi, birlamchi grafikning har bir maksimal klikasining o‘zgaruvchilari cheklash doirasi va aksincha. Daraxtlarni klasterlash ixtiyoriy muammoni shu ikki shart bajariladigan tarzda o'zgartiradi. Chordallik yangi ikkilik cheklovlarni qo'shish orqali amalga oshiriladi. Konformallik cheklovlarni birlashtirish orqali olinadi.
Xususan, akkordalik muammoga ba'zi "soxta" ikkilik cheklovlarni qo'shish orqali amalga oshiriladi. Bular har qanday qiymatlar juftligi bilan qanoatlantiriladigan ikkilik cheklovlar bo'lib, faqat muammoning asosiy grafigiga qirralar qo'shish uchun ishlatiladi. Xususan, xordallik ixtiyoriy tartib bo'yicha birlamchi grafikning induksiyalangan grafigini hosil qiluvchi qirralarni qo'shish orqali olinadi. Ushbu protsedura to'g'ri, chunki induktsiyalangan grafik har doim akkord bo'lib, asl grafikga qirralarning qo'shilishi bilan olinadi.
Muvofiqlik birlamchi grafikning maksimal kliklari aynan cheklovlar doirasi bo'lishini talab qiladi. Har bir asl cheklov doirasi birlamchi grafikda klique bo'lsa-da, bu klique har doim ham maksimal emas. Bundan tashqari, agar u dastlab maksimal bo'lsa ham, akkordalikni kuchaytirish kattaroq guruhni yaratishi mumkin. Konformallik cheklovlarni birlashtirish orqali amalga oshiriladi. Xususan, akkordalikni tatbiq etish natijasida yuzaga keladigan grafikning har bir maksimal klikasi uchun doira sifatida klik bilan yangi cheklov yaratiladi. Ushbu yangi cheklovning qoniqarli qiymatlari doirasi guruhda mavjud bo'lgan barcha dastlabki cheklovlarni qondiradigan qiymatlardir. Ushbu o'zgartirish orqali har bir asl cheklov kamida bitta yangi cheklovga "qo'shiladi". Haqiqatan ham, har bir asl cheklov doirasi asosiy grafikning bir qismidir. Bu klik akkordalikni qo'llashdan keyin ham klik bo'lib qoladi, chunki bu jarayon faqat yangi qirralarni kiritadi. Natijada, bu klik maksimal yoki maksimal klikada joylashgan.
Ushbu tarjima akkord grafigining maksimal kliklarini aniqlashni talab qiladi. Biroq, bu akkordalikni kuchaytirish uchun ishlatiladigan bir xil tartib yordamida osonlik bilan amalga oshirilishi mumkin. Har bir tugunning ota-onalari bir-biriga bog'langanligi sababli, maksimal kliklar tugundan (maksimal kardinallik tartibida klikaning maksimal tuguni) va uning barcha ota-onalaridan iborat. Natijada, bu maksimal kliklarni har bir tugunni ota-onasi bilan ko'rib chiqish orqali aniqlash mumkin.
Ushbu jarayondan kelib chiqadigan muammo birlashma daraxtiga ega va bunday qo'shilish daraxtini o'zgaruvchilarning bir xil tartibini qayta ishlatish orqali olish mumkin. Oxirgi tugundan birinchisiga qarab, har bir cheklov u bilan ko'proq o'zgaruvchilarni baham ko'radigan oldingi cheklash bilan bog'liq. Birlashtirilgan daraxt klasterini parchalanish usuli sifatida ko'rish mumkin, bunda:
qopqoqning elementlari - akkordalikni ta'minlash natijasida paydo bo'lgan grafikning kliklari;
daraxt - birlashuvchi daraxt;
har bir cheklov o'zgaruvchilar to'plami cheklov doirasini o'z ichiga olgan daraxtning barcha tugunlariga tayinlanadi.
Daraxtning klasterli dekompozitsiyasining kengligi daraxtning har bir tuguniga bog'liq bo'lgan o'zgaruvchilarning maksimal soni. Muammoning kengligi - bu daraxt klasterlarining parchalanishining minimal kengligi.
Menteşe/klasterli dekompozitsiya
Menteşe parchalanishining natijasini daraxtlar to'plami yordamida har bir ilgakni parchalash orqali yanada soddalashtirish mumkin. Boshqacha qilib aytganda, menteşalar aniqlangandan so'ng, ularning har birining daraxt klasteri ishlab chiqariladi. Olingan daraxt nuqtai nazaridan, shuning uchun har bir tugun daraxt bilan almashtiriladi.
So'rovlarni ajratish
So'rovlar dekompozitsiyasi daraxtning har bir tuguniga o'zgaruvchilar to'plami va cheklovlar to'plamini bog'laydi; har bir cheklov ba'zi tugun bilan bog'lanadi va berilgan o'zgaruvchi yoki cheklov bilan bog'langan tugunlar tomonidan induktsiya qilingan pastki daraxt ulanadi. Aniqrog'i, har bir o'zgaruvchi uchun ushbu o'zgaruvchiga bog'langan yoki ushbu o'zgaruvchiga ega bo'lgan cheklov bilan bog'langan tugunlarning pastki daraxti ulanadi. Dekompozitsiyaning kengligi tugun bilan bog'liq bo'lgan o'zgaruvchilar va cheklovlarning maksimal birlashtirilgan sonidir.
Cheklovlarni tugunlar bilan bog'lash, parchalanish va misollar kengligini kamaytirishi mumkin. Boshqa tomondan, kenglikning bu ta'rifi, agar parchalanish berilgan bo'lsa, ko'p nomli vaqt ichida qattiq kenglikdagi muammolarni hal qilishga imkon beradi. Bunday holda, yangi o'zgaruvchining sohasi ko'p nomli katta bo'lishi mumkin bo'lgan, lekin cheklangan miqdordagi cheklovlarga ega bo'lgan kichik muammoni echish orqali olinadi. Natijada, bu domen polinom o'lchamiga ega bo'lishi kafolatlanadi; ikki sohaning tengligi bo'lgan yangi muammoning cheklovlari ham ko'p nomli o'lchamga ega.
Sof so'rovlar dekompozitsiyasi bu so'rovlarning parchalanishi bo'lib, unda tugunlar faqat cheklovlar bilan bog'lanadi. Berilgan kenglikdagi so'rovlarning parchalanishidan logarifmik fazoda bir xil kenglikdagi sof so'rovlar dekompozitsiyasini qurish mumkin. Bu tugunning cheklovlarida bo'lmagan tugunning o'zgaruvchilarini ushbu o'zgaruvchilarni o'z ichiga olgan ba'zi cheklovlar bilan almashtirish orqali olinadi.
Bu parchalanish usulining kamchiligi shundaki, namunaning belgilangan kenglikga ega yoki yo'qligini tekshirish odatda NP-to'liqdir ; Bu kenglik 4 bilan isbotlangan
Gipertree parchalanishi
Gipertree dekompozitsiyasi daraxtning har bir tuguniga o'zgaruvchilar to'plami va cheklovlar to'plamini bog'laydi. Tugun cheklovlariga tugun bilan bog'langan yangi o'zgaruvchining domenini yaratishda foydalanilmaydigan o'zgaruvchilarni o'z ichiga olishiga ruxsat berish orqali so'rovlarning parchalanishini kengaytiradi. Parchalanish usuli uchun umumiy shartlardan tashqari (har bir cheklov doirasi hech bo'lmaganda tugun bilan bog'langan o'zgaruvchilar to'plamida va asl o'zgaruvchi tomonidan induktsiya qilingan pastki daraxt ulangan), quyidagi ikkita shartni bajarish kerak:
tugundagi har bir asl o'zgaruvchi tugun bilan bog'langan kamida bitta cheklov doirasida bo'ladi;
tugunning o'zgaruvchisi bo'lmagan tugun cheklovlarining o'zgaruvchilari tugunga ildiz otgan pastki daraxtda sodir bo'lmaydi.
Daraxtning parchalanishining kengligi har bir tugun bilan bog'liq bo'lgan cheklovlarning maksimal soni. Agar bu kenglik doimiy bilan chegaralangan bo'lsa, ko'p nomli vaqt ichida asl masalaga ekvivalent muammoni qurish mumkin. Tugunga bog'lanmagan, lekin tugun cheklovlari doirasidagi o'zgaruvchilar ushbu misolni yaratishda "prognoz qilinadi". Buni birinchi navbatda tugun o‘zgaruvchilari ustidagi cheklovlarni proyeksiya qilish va keyin ushbu kichik muammoning barcha yechimlarini topish yoki birinchi navbatda kichik muammoni barcha cheklovlar bilan yechish va keyin qo‘shimcha o‘zgaruvchilarni olib tashlash orqali amalga oshirilishi mumkin.
Yuqoridagi ikkita talab asl va yangi muammoning ekvivalentligini kafolatlash uchun shart emas. Ular chegaralangan kenglikdagi masalalarni polinom vaqtida yechish mumkinligini kafolatlash uchun kerak.
Ba'zi o'zgaruvchilar tugun bilan samarali bog'lanmagan bo'lsa-da, cheklovni tugun bilan bog'lash imkoniyati so'rov kengligidan kamroq kenglikni keltirib chiqarishi mumkin. Misol uchun, agar tugun bog'langan bo'lsa
{
�
(
�
,
�
)
,
�
,
�
,
�
}
{\displaystyle \{C(a,b),c,d,e\}}so'rovlar dekompozitsiyasida va cheklovda
�
(
�
,
�
,
�
,
�
)
{\ displaystyle D (c, d, e, f)}mavjud bo'lsa, gipertree dekompozitsiyasi bir xil tugunni cheklovlar bilan bog'lashi mumkin
{
�
,
�
}
{\displaystyle \{C,D\}}va o'zgaruvchilar
{
�
,
�
,
�
,
�
,
�
}
{\displaystyle \{a,b,c,d,e\}}. Kenglikni tekshirishda faqat cheklovlar hisoblanganligi sababli, bu tugun ikkinchi kenglikka ega. Xuddi shu tugun so'rovlar dekompozitsiyasidan foydalanganda to'rtta kenglikka ega (bitta cheklov va uchta o'zgaruvchi). Ikki yoki undan ortiq o'zgaruvchilarni bitta cheklash bilan almashtirish mumkin bo'lsa, bu cheklov tugun bilan bog'lanmagan o'zgaruvchini o'z ichiga olgan bo'lsa ham, kenglikni qisqartirish mumkin.
Umumiy giperdaraxt parchalanishi
Umumlashtirilgan gipertree dekompozitsiyalari gipertree dekompozitsiyalari kabi aniqlanadi, ammo oxirgi talab bekor qilinadi; bu "tugunning o'zgaruvchisi bo'lmagan tugun cheklovlarining o'zgaruvchilari tugunga ildiz otgan pastki daraxtda yuzaga kelmaydi" shartidir. Muammoni polinom vaqtida aniq yechish mumkin, agar uning belgilangan kenglikdagi dekompozitsiyasi berilgan bo'lsa. Shu bilan birga, belgilangan kenglikdagi cheklov oson bo'lishi ma'lum emas, chunki 2001 yildan boshlab, hatto mavjudligi ma'lum bo'lsa ham, qattiq kenglikning parchalanishini topishning murakkabligi ma'lum emas .
Taqqoslash
Namunalarning kengligi parchalanish usullarining samaradorligi shaklidir. Haqiqatan ham, muammolarni qat'iy kenglikdagi parchalanishlardan hal qilish mumkinligini hisobga olsak, parchalanish bo'yicha kenglik qanchalik kam bo'lsa, bu parchalanish yordamida samarali hal qilinadigan misollar shunchalik ko'p bo'ladi.
Ba'zi parchalanishlar kenglik sifatida tugunning o'zgaruvchilari sonini (yoki shunga o'xshash miqdorni) ishlatadi. Boshqalar: sikl giperkutsi, menteşe dekompozitsiyasi, so‘rovlar dekompozitsiyasi, giperdaraxt parchalanishi va umumiy giperdaraxt parchalanishi cheklovlarni (yoki ularning giperqirralar ko‘rinishidagi doiralarini) tugunlar bilan bog‘laydi va kenglikdagi tugun bilan bog‘liq cheklovlar sonini o‘z ichiga oladi. Bu kenglik nuqtai nazaridan sezilarli tejash bo'lishi mumkin. Haqiqatan ham, bitta cheklov bilan bog'liq muammolar
�
{\displaystyle n}o'zgaruvchilar faqat bitta tugunli daraxtda parchalanishi mumkin. Bu tugun bilan bog'lanishi mumkin
�
{\displaystyle n}o'zgaruvchilar yoki bitta cheklov bilan. O'zgaruvchilar sonini hisoblash kenglikka olib keladi
�
{\displaystyle n}, cheklashlar sonini hisoblash esa kenglikka olib keladi
1
{\displaystyle 1}.
Boshqa barcha parchalanish usullarini taqqoslash umumlashtirish va urishga asoslangan. Umumlashtirish har bir muammoning kengligi borligini anglatadi
�
{\displaystyle n}usulga ko'ra kengligi bilan chegaralangan
�
+
�
{\displaystyle n+k}belgilangan uchun
�
{\displaystyle k}. Kaltaklash, dekompozitsiya usuliga ko'ra o'zgarmas kenglikka ega bo'lgan, ammo boshqasiga ko'ra emas, balki muammolar sinflari mavjudligini anglatadi. Quyidagilar so'rovlarning parchalanishi hisobga olinmaydigan ixtiyoriy muammolar uchun natijalar:
hypertree dekompozitsiyasi boshqa barcha usullarni umumlashtiradi va uradi
Daraxt klasteri bilan yaxshilangan ilgak parchalanishi ilgak parchalanishini ham, daraxt klasterini ham umumlashtiradi va yengadi
daraxtlarning klasterlanishi daraxtning parchalanishiga teng (birlamchi grafikda)
ikkala menteşe dekompozitsiyasi va daraxt klasteri ikki bog'langan komponentlarni umumlashtiradi va uradi
sikl kesishmasi (asosiy grafikda) sikl giperksetlari va daraxtlar to'plami bilan umumlashtiriladi va uriladi.
Bundan tashqari, daraxt klasterining kengligi muammoning induktsiyalangan kengligi va bittaga teng ekanligini ko'rsatish mumkin . Ruxsat etilgan induktsiyali kenglik masalasi uchun polinom bo'lgan adaptiv izchillik algoritmi daraxtlarni to'plashning birinchi bosqichidagi kabi muammolarni ekvivalentlarga aylantiradi.
Parchalanishdan yechish
Parchalanish daraxtini hisobga olgan holda, yuqorida tavsiflangan ikkilik daraxtga o'xshash masalani qurish va uni hal qilish orqali hal qilish mumkin. Bu ko'p nomli vaqt masalasidir, chunki uni polinom vaqtida, masalan, yo'nalishli yoy izchilligini ta'minlash algoritmi yordamida hal qilish mumkin .
Parchalanish natijasida yuzaga keladigan ikkilik asiklik muammolarning ixtisoslashtirilgan algoritmi quyidagicha tasvirlangan. U daraxtning chekkalari bo'ylab, barglardan ildizga va orqaga o'tadigan cheklovlar yaratish orqali ishlaydi. Bir chekka bo'ylab o'tkazilgan cheklov grafikning chetning bir tomonidagi qismining boshqa tomoniga barcha cheklovlarining ta'sirini "jamlaydi".
♟ "Chess Engines", algoritmlar, kompyuter qanday shaxmat o'ynaydi ❔
Ushbu postda kompyuter bizga qarshi qanday shaxmat o'ynashini ko'rib chiqamiz.
Kompyuterni insonga kabi fikrlashga majburlash xato. Kompyuterga "ko'rishni" emas, doskani bir qator satr bilan ifodalovchi FEN (https://www.chess.com/terms/fen-chess)ni tushuntirish lozim. Biz tajribalarga, kompyuter esa ko'rsatmalar asosida o'ynaydi. Ko'rsatmalar to'plami esa algoritmdir. Kompyuter shaxmatda foydalaniladigan asosiy taktika va algoritmlar bilan davom etamiz.
🧮 "Evaluation" funksiyasi
Funksiya har bir yurish davomida ustunlik kim tomonda ekanligini sonlar orqali ifodalaydi. Avvalgi maqsad raqibning ko'proq donalarini olish edi(xuddi shashkadagidek). Funksiyaning kamchiligi: 4ta piyodani 1ta ferz + 1ta otdan ustun deb hisoblaydi(4>2). Keyinroq funksiya donalarning qiymatini ham hisoblay boshladi("material" xususiyati). O'yinchining berilgan pozitsiyadagi yurishlar sonining ko'pligi uning "mobility" xususiyatini xarakterlaydi (ko'proq joyga egalik || himoya qilish). "Material" va "mobility" xususiyatlari yig'indisi hisoblanadi(=E). Kompyuter yurish kimning foydasi ekanligini aniqlash uchun yuqoridagi yig'indi natijasi "E"ni, yurish navbati o'zida bo'lganda 1ga, aksincha bo'lsa -1ga ko'paytiradi(|±E| ochkoga "yedirib"/"yeb" qo'ydi).
🌳 "Search Tree"(!= binary)
Tasavvur qiling sizda A'dan boshlab atigi B va C yurish varianti mavjud. B yurishda E = -8(M:ferz va piyodan almashinadi), C yurishda E = 0(M:"ferz"lar almashinadi). Barcha yurishlar davomini ketma-ket qo'gozda birlashtirib tasvirlansa, daraxt(tree) chizmasini ko'ramiz. Yurishlar bir-biriga ulangan joylar uning shoxlari, barglari esa "evaluation" funksiyasining natijasi hisoblanadi. A'dan B'ga chiqarilgan daraxtning shoxi ferz'ning yurishi va shoxning bargi E = -8 deyishimiz mumkin(yurish natijasi). Kompyuter eng yaxshi yurishni topish uchun shu daraxtdagi o'zining foydasiga ishlaydigan shoxlar zanjirini izlaydi xolos.
⚔️ "MiniMax" backtracking (https://en.wikipedia.org/wiki/Backtracking) algoritmi
Kompyuter har bir shoxlar zanjirining umumiy "evaluation" natija(ochko)sini hisoblab chiqadi. Funksiya snayperlar kabi ya'ni yaxshi mergan, yomon o'lja bo'lishi shart. Ya'ni o'yin boshidanoq o'zi uchun +'ga(max), raqib uchun -'ga(min) ishlaydigan yurishni(shoxni) topib, ushbu amalni eng yaxshi ochkoni topmaguniga qadar qaytadan shoxga ulangan shoxlarga qo'llaydi(rekursiya). Unga maksimum ochko beradigan yurish, sizni minimum ochko beradigan yurishga majburlaydi.
🪓 "Alpha-Beta Pruning"(optimallashtirish)
O'yin boshida jami 400xil(20x20) o'yinlar mavjud. Qiziq tomoni, shaxmatda o'ynalishi mumkin bo'lgan o'yinlar soni, olamdagi atomlardan ham ko'p(10^120>10^82). MiniMax'ni bu darajadagi katta "tree"ni hisoblay olmasligi aniq. Yuqoridagi misoldan, MiniMax C yurishni tanlashi tayin. Lekin ungacha "evaluation" funksiyasi B yurishdan keyin sodir bo'ladigan minglab yurishlarni("daraxt"ning shoxlarini) ham hisoblaydi(vaqtni oladi). Alfa-beta taktikasi ferzni berib qo'ygan(E=-8)dan keyin sodir bo'ladigan yurishlarning hammasini sifatsiz deb sanab, ushbu yurish boshlangan shoxni daraxtdan olib tashlab, daraxt hajmini kichkiraytiradi va qidiruvni tezlatadi.
📜 "Transposition" Jadvali
Shaxmatda aynan bir xil pozitsiyalar, turli yurishlar bilan hosil qilinishi mumkin("transposition"). Bir xil pozitsiyalarni keltirib chiqaruvchi "tree"ning shoxlarini qayta hisoblamaslik uchun, hisoblangan pozitsiyalar qiymati "transposition" jadvalida saqlanadi. Ular hash-table (https://www.youtube.com/watch?v=MfhjkfocRR0) orqali amalga oshirilganligi uchun istalgan amal O(1) vaqtda bajariladi.
🗺 Xaritalar
O'yinni boshidagi maxsus "opening"larda kompyuter har bir dona uchun alohida tuzilgan maxsus xaritalar to'plamidan foydalanadi. Shox uchun tuzilgan xarita mavjud bo'lmaganida, kompyuter shoxni himoyalash o'rniga doska markazida aylantirib yurardi.
Yuqoridagi asosiy komponentlardan foydalanib, bemalol shaxmat o'ynaydigan qo'lbola "engine" qurishingiz mumkin. Kompyuter bilan shaxmat o'ynash, qo'lida pistoleti bor bola bilan boks tushishga o'xshaydi. Siz boks tushaman deysiz, lekin u sizni otib qo'yadi...
Don't follow your dreams, follow @AbduazizPy
Foydalanilgan adabiyotlar:
https://en.wikipedia.org/wiki/Decomposition_method_(constraint_satisfaction)
http://www.cs.uu.nl/research/projects/treewidthlib/
https://en.wikipedia.org/wiki/Anytime_Algorithm
https://web.archive.org/web/20060512022851/http://www.ics.uci.edu/~vgogate/
http://www.dbai.tuwien.ac.at/proj/hypertree/downloads.html
http://carlit.toulouse.inra.fr/cgi-bin/awki.cgi/ToolBarIntro
http://www.itu.dk/people/sathi/treed/
https://en.wikipedia.org/wiki/Anytime_algorithm
https://en.wikipedia.org/wiki/Decomposition_method_(constraint_satisfaction)
https://en.wikipedia.org/wiki/Decomposition_method_(multidisciplinary_design_optimization)
|
