Ko'p sinov texnikasi - Multi-trials technique

The ko'p sinov texnikasi Schneider va boshq. uchun ishlaydi taqsimlangan algoritmlar va simmetriyani samarali ravishda buzishga imkon beradi. Simmetriyani buzish, masalan, ko'plab sub'ektlar bir xil manbaga bir vaqtning o'zida kirishni xohlaydigan resurslarni taqsimlash muammolarida zarurdir. Ko'pchilik xabar o'tmoqda algoritmlar odatda har bir xabar almashinuvi uchun simmetriyani buzish uchun bitta urinishni qo'llaydi. The ko'p sinov texnikasi har qanday xabar almashish uchun ko'proq urinishlarni qo'llash orqali ushbu yondashuvdan ustun turadi.[1]

Masalan, O (Δ) hisoblash uchun oddiy algoritmda vertexni bo'yash, bu erda Δ grafadagi maksimal darajani bildiradi, har bir rangsiz tugun tasodifiy mavjud rangni tanlaydi va agar biron bir qo'shni (bir vaqtning o'zida) bir xil rangni tanlamasa, uni saqlaydi. Ko'p sinov texnikasi uchun tugun har bir aloqa turida tanlangan ranglar sonini asta-sekin oshiradi. Texnika talab qilinadigan aloqa turlarini eksponent ravishda kamaytirishdan ko'proq narsani berishi mumkin. Ammo, agar maksimal daraja small kichikroq bo'lsa, yanada samarali texnikalar mavjud, masalan. Richard Koul tomonidan (kengaytirilgan) tanga tashlash texnikasi va Uzi Vishkin.[2]

Izohlar

  1. ^ Shnayder (2010)
  2. ^ Shnayder (2008)

Adabiyotlar

  • Schneider, J. (2010), "Tarqatilgan simmetriyani sindirishning yangi usuli" (PDF), Ish yuritish Tarqatilgan hisoblash tamoyillari bo'yicha simpozium
  • Schneider, J. (2008), "O'sish chegaralangan grafikalar uchun taqsimlangan maksimal mustaqil algoritm log-yulduz" (PDF), Ish yuritish Tarqatilgan hisoblash tamoyillari bo'yicha simpozium