Birkhoff algoritmi - Birkhoff algorithm

Birxof algoritmi parchalanish algoritmi a bistoxastik matritsa ning qavariq birikmasiga almashtirish matritsalari. Tomonidan nashr etilgan Garret Birxof 1946 yilda.[1][2]:36 Uning ko'plab dasturlari mavjud. Bunday dasturlardan biri muammo uchun mo'ljallangan adolatli tasodifiy topshiriq: buyumlarning tasodifiy taqsimlanishini hisobga olgan holda, Birxof algoritmi uni deterministik ajratmalar bo'yicha lotereyaga aylantirishi mumkin.

Terminologiya

A bistoxastik matritsa (shuningdek deyiladi: ikki marta stoxastik) - bu barcha elementlar 0 dan katta yoki unga teng bo'lgan matritsa va har bir satr va ustundagi elementlarning yig'indisi 1 ga teng. Masalan, quyidagi 3 dan 3 gacha matritsa:

A almashtirish matritsasi har bir element 0 yoki 1 ga teng bo'lgan bistoxastik matritsaning alohida holatidir (shuning uchun har bir satrda va har bir ustunda to'liq bitta "1" mavjud). Masalan, quyidagi 3 dan 3 gacha matritsa:
A Birxof parchalanishi (shuningdek deyiladi: Birxof-fon-Neyman parchalanishi) bistoxastik matritsaning bu uning og'irligi manfiy bo'lmagan matritsalar yig'indisi sifatida taqdim etilishi. Masalan, yuqoridagi matritsa quyidagi summa sifatida taqdim etilishi mumkin:
Birkhoff algoritmi kirish sifatida bistoxastik matritsani qabul qiladi va Birkhoff dekompozitsiyasi sifatida qaytib keladi.

Asboblar

A almashtirish rejimi ning n-by-n matritsa X to'plamidir n yozuvlari X har bir satrdan va har bir ustundan to'liq bitta yozuvni o'z ichiga oladi. Teorema Denes König deydi:[3][2]:35

Har qanday bistoxastik matritsada barcha yozuvlar ijobiy bo'lgan permutatsiya to'plami mavjud.

The pozitivlik grafigi ning n-by-n matritsa X a ikki tomonlama grafik 2 bilann tepaliklar, unda bir tomonning tepalari joylashgan n qatorlar va boshqa tomonning tepalari bu n ustunlar, agar qator va ustun orasidagi chegara mavjud bo'lsa, agar bu satr va ustundagi yozuv ijobiy bo'lsa. Ijobiy yozuvlar bilan almashtirilgan to'plam a ga teng mukammal moslik ijobiy grafikada. Ikki tomonlama grafadagi mukammal moslikni polinom vaqtida topish mumkin, masalan. uchun har qanday algoritmdan foydalanish maksimal darajada muvofiqlik. Knig teoremasi quyidagilarga teng:

Har qanday bistoxastik matritsaning ijobiy grafigi mukammal moslikni tan oladi.

Matritsa deyiladi miqyosli-bistoxastik agar barcha elementlar zaif musbat bo'lsa va har bir satr va ustunning yig'indisi teng bo'lsa v, qayerda v ba'zi ijobiy doimiy. Boshqacha qilib aytganda, shunday v bistoxastik matritsa marta. Pozitivlik grafigiga masshtab ta'sir qilmagani uchun:

Har qanday miqyosli-bistoxastik matritsaning ijobiy grafigi mukammal moslikni tan oladi.

Algoritm

Yuqoridagi vositalar yordamida Birxof algoritmi quyidagicha ishlaydi.[4]:ilova B.

  1. Ruxsat bering men = 1.
  2. Pozitivlik grafigini tuzing GX ning X.
  3. In mukammal mosligini toping GX, ichida o'rnatilgan ijobiy almashtirishga mos keladi X.
  4. Ruxsat bering z[men]> 0 permutatsiya to'plamidagi eng kichik yozuv.
  5. Ruxsat bering P[men] musbat almashtirish majmuasida 1-sonli permutatsiya matritsasi bo'lishi kerak.
  6. X: = ga ruxsat bering X − z[men] P[men].
  7. Agar X tarkibida nolga teng bo'lmagan elementlar bo'lsa, Let men = men + 1 va 2-bosqichga qayting.
  8. Aks holda, summani qaytaring: z[1] P[1] + ... + z[2] P[2] + ... + z[men] P[men].

Algoritm to'g'ri, chunki 6-bosqichdan so'ng har bir satr va har bir ustundagi yig'indisi tushadi z[men]. Shuning uchun, matritsa X miqyosli-bistoxastik bo'lib qolmoqda. Shuning uchun, 3-bosqichda har doim mukammal moslik mavjud.

Ish vaqti murakkabligi

Tanlash bo'yicha z[men] 4-bosqichda, har bir iteratsiyada kamida bitta element X 0 ga aylanadi. Shuning uchun algoritm ko'pi bilan tugashi kerak n2 qadamlar. Biroq, oxirgi qadam bir vaqtning o'zida bajarilishi kerak n elementlar 0, shuning uchun algoritm maksimal darajada tugaydi n2 − n + 1 qadam.

1960 yilda Joshnson, Dulmage va Mendelson Birxof algoritmi eng ko'pi bilan tugashini ko'rsatdilar n2 − 2n + 2 qadam, bu umuman qattiq (ya'ni ba'zi hollarda) n2 − 2n + 2 ta almashtirish matritsasi talab qilinishi mumkin).[5]

Odil bo'linishda dastur

In adolatli tasodifiy topshiriq muammo bor n ob'ektlar va n ob'ektlarga nisbatan turli xil imtiyozlarga ega odamlar. Har bir insonga ob'ekt berish talab qilinadi. Adolatni ta'minlash uchun ajratish tasodifiy ravishda amalga oshiriladi: har bir (shaxs, ob'ekt) juftligi uchun har bir kishi va har bir ob'ekt uchun ehtimolliklar yig'indisi 1 ga teng bo'lgan ehtimollik hisoblanadi. ehtimollik-ketma-ket protsedura ehtimolliklarni hisoblab chiqishi mumkin, chunki har bir agent, ehtimolliklar matritsasiga qarab, boshqa barcha odamlar qatoridan ko'ra o'z ehtimolliklar qatorini afzal ko'radi (bu xususiyat deyiladi hasad-ozodlik ). Shu sababli ushbu tasodifiy ajratishni amalda qanday amalga oshirish kerakligi haqida savol tug'iladi? Har bir ob'ekt uchun alohida-alohida tasodifiy tasodifiy tanlash mumkin emas, chunki buning natijasida ba'zi odamlar ko'p narsalarni olishadi, boshqalari esa ob'ektlarni olmaydilar.

Bu erda Birkhoff algoritmi foydalidir. Ehtimollar ketma-ket algoritmi bilan hisoblangan ehtimolliklar matritsasi bistoxastikdir. Birxof algoritmi uni permutatsion matritsalarning qavariq birikmasiga aylantirishi mumkin. Har bir almashtirish matritsasi har bir agent aynan bitta ob'ektni qabul qiladigan deterministik topshiriqni ifodalaydi. Har bir bunday matritsaning koeffitsienti ehtimollik sifatida talqin etiladi; hisoblangan ehtimolliklar asosida tasodifiy bitta topshiriqni tanlash va uni amalga oshirish mumkin.

Kengaytmalar

Birkhoff dekompozitsiyasini minimal atamalar sonini hisoblash bilan hisoblash muammosi ko'rsatilgan Qattiq-qattiq, lekin uni hisoblash uchun ba'zi evristika ma'lum.[6][7] Ushbu teorema umumiy stoxastik matritsa uchun deterministik o'tish matritsalari bilan kengaytirilishi mumkin.[8]

Shuningdek qarang

Adabiyotlar

  1. ^ Birxof, Garret (1946), "Tres observaciones sobre el algebra lineal [Lineer algebra bo'yicha uchta kuzatuv]", Univ. Yo'q. Tukuman. Revista A., 5: 147–151, JANOB  0020547.
  2. ^ a b Lovash, Laslo; Plummer, M. D. (1986), Moslik nazariyasi, Diskret matematika yilnomalari, 29, Shimoliy Gollandiya, ISBN  0-444-87916-1, JANOB  0859549
  3. ^ König, Den (1916), "Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére", Matematikai és Természettudományi Értesítő, 34: 104–119.
  4. ^ Aziz, Xaris (2020). "Bir vaqtning o'zida Ex-ante va Ex-post adolatli bo'lishiga erishish". arXiv:2004.02554 [cs.GT ].
  5. ^ Jonson, Dayan M.; Dulmage, A. L .; Mendelsohn, N. S. (1960-09-01). "G. Birxofning ikki karra stoxastik matritsalar algoritmi to'g'risida". Kanada matematik byulleteni. 3 (3): 237–242. doi:10.4153 / cmb-1960-029-5. ISSN  0008-4395.
  6. ^ Dyufosse, Fanni; Uçar, Bora (may, 2016). "Ikki marta stoxastik matritsalarning Birxof-von Neyman dekompozitsiyasi to'g'risida eslatmalar" (PDF). Chiziqli algebra va uning qo'llanilishi. 497: 108–115. doi:10.1016 / j.laa.2016.02.023.
  7. ^ Dyufosse, Fanni; Kaya, Kamer; Panagiotas, Ioannis; Uçar, Bora (2018). "Ikki marta stoxastik matritsalarning Birkhoff-von Neyman dekompozitsiyasi to'g'risida qo'shimcha eslatmalar" (PDF). Chiziqli algebra va uning qo'llanilishi. 554: 68–78. doi:10.1016 / j.laa.2018.05.017. ISSN  0024-3795.
  8. ^ Siz, Feliks X.-F .; Vang, Yue; Qian, Hong (2016). "Stoxastik dinamika: Markov zanjirlari va tasodifiy transformatsiyalar". Diskret va uzluksiz dinamik tizimlar - B seriyali. 21 (7): 2337–2361. doi:10.3934 / dcdsb.2016050.