Կայուն ամուսնության խնդիր

Մաթեմատիկայում և համակարգչային գիտության մեջ կայուն ամուսնության խնդիրը (SMP) յուրաքանչյուր տարրի համար տրված մի շարք նախասիրությունների պայմաններում տարրի երկու խմբերի միջև կայուն համապատասխանություն գտնելն է։ Համապատասխանությունը մի խմբի տարրերի քարտեզագրումն է մյուս խմբի տարրերի հետ։ Համապատասխանությունը կայուն է բոլոր դեպքերում, բացի հետևյալ երկուսից.

  1. Առաջինը ընտրված խմբի տրված A տարրերից որոշները ավելի նախապատվությունը տալիս են երկրորդը ընտրված խմբի տրված B տարրերից որոշներին, քան մի տարրի, որին արդեն A-ն համապատասխանեցրած է, և
  2. B-ն նույնպես գերադասում է A-ն, քան այն տարրը, որին B-ն արդեն համապատասխանում է

Այսինքն, համապատասխանությունը կայուն է, երբ գոյություն չունի որևէ այլընտրանքային զույգ (A, B), որում և A-ն և B-ն անհատապես կլինեն ավելի լավը, քան կլինեին այն տարրի հետ, որին նրանք իրականում համապատասխանում են։

Կայուն ամուսնության խնդիրը սովորաբար ձևակերպվում է հետևյալ կերպ. Տրված են n տղամարդ և n կին, որտեղ յուրաքանչյուր ոք ըստ նախասիրության համարակալել է հակառակ սեռի բոլոր անդամներին եզակի թվերով 1-ից մինչև n, ամուսնացրել տղամարդկանց և կանանց այնպես, որ չլինեն հակառակ սեռի երկու մարդ, որոնք ավելի կնախընտրեին մեկ ուրիշի, քան իրենց զուգընկերոջը։ Եթե չկան այդպիսի մարդիկ, բոլոր ամուսնությունները "կայուն" են։

Կայուն ամուսնության խնդրի լուծման ալգորիթմները լուծում են գտնում իրական աշխարհի տարբեր իրավիճակներում, որոնցից ամենահայտնին հանդիսանում է բժիշկ շրջանավարտների նշանակումը իրենց առաջին հիվանդանոցում[1]։

Լուծում

[խմբագրել | խմբագրել կոդը]
Animation showing an example of the Gale-Shapley algorithm

1962 թվականին Դավիթ Գեյլը և Լոյդ Շեպլին ապացուցեցին, որ ցանկացած հավասար թվով կանանց և տղամարդկանց համար միշտ հնարավոր է լուծել Կայուն Ամուսնության Խնդիրը և բոլոր ամուսնությունները դարձնել կայուն։ Դրա համար նրանք ներկայացրեցին ալգորիթմ[2][3]։

Գեյլ-Շեպլի ալգորիթմը ներառում է մի շարք "փուլեր" (կամ "կրկնողություններ"), որտեղ յուրաքանչյուր չնշանված տղամարդ "ամուսնության առաջարկություն է անում" ամենանախընտրելի կնոջը։ Հետո յուրաքանչյուր կին քննարկում է իր բոլոր երկրպագուներին և նրան, ում նա ավելի է նախընտրում, ասում է "Հնարավոր է", իսկ մնացածներին՝ "Ոչ"։ Դրանից հետո նա պայմանականորեն "նշանվում է" այն երկրպագուի հետ, ում նա ավելի է նախընտրում։ Առաջին փուլում նախ ա) յուրաքանչյուր չնշանված տղամարդ առաջարկություն է անում այն կնոջը, ում նա ավելի է նախընտրում, և հետո բ) յուրաքանչյուր կին պատասխանում է "հնարավոր է" այն երկրպագուին, ոմ նա ավելի է նախընտրում և "Ոչ"` մնացած երկրպագուներին։ Յուրաքանչյուր հաջորդ փուլում նախ ա) յուրաքանչյուր չնշանված տղամարդ առաջարկություն է անում ամենանախընտրելի կնոջը, ում նա դեռ առաջարկություն չի արել (անկախ նրանից` կինը արդեն նշանված է, թե ոչ), և հետո բ) յուրաքանչյուր կին պատասխանում է "հնարավոր է" այն երկրպագուին, ում նա ավելի է նախընտրում (կամ իր գոյություն ունեցող պայմանական զուգընկերը կամ մեկ ուրիշը) և մերժում է մնացածներին (այդ թվում նրա ներկա պայմանական զուգընկերը)։

Այս ալգորիթմը երաշխավորում է, որ.

Բոլորը ամուսնանում են։ Երբ կինը նշանվում է, նա միշտ նշանված է ինչ-որ մեկի հետ։ Այսպիսով, վերջում չի կարող լինել չնշանված կին և տղամարդ, քանի որ նա ինչ-որ պահի պետք է նրան առաջարկություն արած լինի (քանի որ տղամարդը, անհրաժեշտության դեպքում, առաջարկություն է անում բոլորին)։
Ամուսնությունները կայուն են։ Ենթադրենք Ալիսը և Բոբը նշանված են, բայց ոչ իրար հետ։ Ալգորիթմի ավարտից հետո ոչ Ալիսը, ոչ Բոբը չեն կարող ավելի նախընտրել մեկը մյուսին, քան իրենց ներկա զուգընկերոջը։ Եթե Բոբը նախընտրում է Ալիսին, քան իր զուգընկերուհուն, ապա նա պետք է նախքան իր ներկա զուգընկերուհուն առաջարկություն անելը Ալիսին առաջարկություն արած լիներ։ Եթե Ալիսը ընդուներ նրա առաջարկը քանի դեռ չէր ամուսնացել, նա պետք է լքեր նրան այն մարդու համար, ում նա ավելի շատ է սիրում, այդ պատճառով կարող ենք ասել, որ նա չի սիրում Բոբին ավելի շատ քան իր ներկա զուգընկերոջը։ Եթե Ալիսը մերժեց նրա առաջարկը, դա նշանակում է, որ նա այն մարդու հետ է, ում սիրում է ավելի շատ, քան Բոբին։

Ալգորիթմ

[խմբագրել | խմբագրել կոդը]

function stableMatching { 

Initialize all m ∈ M and w ∈ W to free
while ∃ free man m who still has a woman w to propose to {
w = m's highest ranked such woman to whom he has not yet proposed
if w is free
(m, w) become engaged
else some pair (m', w) already exists
if w prefers m to m'
(m, w) become engaged
m' becomes free
else
(m', w) remain engaged
}
}

Լուծման օպտիմալություն

[խմբագրել | խմբագրել կոդը]

Մինչ լուծումը կայուն է այն պարտադիր կերպով օպտիմալ չէ բոլոր անհատների տեսանկյունից։ Ալգորիթմի ավանդական ձևը օպտիմալ է առաջարկներ նախաձեռնողի համար։ Օրինակ.

Կան երեք երկրպագու (A, B, C) և երեք գրախոս (X, Y, Z), որոնք ունեն հետևյալ նախապատվությունները. 

A։ YXZ B։ ZYX C։ XZY X։ BAC Y։ CBA Z։ ACB

Կա երեք կայուն լուծում. 

երկրպագուները ստանում են իրենց առաջին ընտրությունը, իսկ գրախոսները՝ երրորդ (AY, BZ, CX)
բոլոր մասնակիցները ստանում են իրենց երկրորդ ընտրությունը (AX, BY, CZ)
գրախոսները ստանում են իրենց առաջին ընտրությունը, իսկ երկրպագուները՝ երրորդ (AZ, BX, CY)

Դրանք բոլորը կայուն են, որովհետև անկայունությունը պահանջում է, որ բոլոր մասնակիցները ուրախ լինեն այլընտրանքային համապատասխանությունից։ Յուրաքանչյուրին իրենց երկրորդ ընտրությունը տալը երաշխավորում է, որ որևէ այլ համապատասխանություն կողմերից մեկի համար կլիներ անցանկալի։ Ալգորիթմը համընկնում է օպտիմալ լուծման մի կետում, որովհետև յուրաքանչյուր գրախոս ուղղակի ստանում է մեկ առաջարկ, ուստի ընտրում է այդ առաջարկը որպես լավագույն ընտրություն՝ երաշխավորելով, որ յուրաքանչյուր երկրպագու ունի ընդունված առաջարկ՝ ավարտելով համապատասխանությունը։ Օպտիմալության այս անհամաչափությունը պայմանավորված է նրանով, որ երկրպագուներն ունեն մի ամբողջ շարք ընտրելու համար, բայց գրախոսները ընտրում են երկրպագուների սահմանափակ ենթաբազմությունից ժամանակի ցանկացած պահի։

Նմանատիպ խնդիրներ

[խմբագրել | խմբագրել կոդը]

Կշռված համապատասխանության խնդիրը (weighted matching problem) փորձում է գտնել համապատասխանություն կշռված երկմասնյա գրաֆում, որն ունի առավելագույն կշիռ։ Առավելագույն կշռված համապատասխանությունները պարտադիր չէ, որ լինեն կայուն, բայց որոշ ծրագրերում առավելագույն կշռված համապատասխանությունը ավելի լավն է, քան կայունը։

Կայուն հարևանների խնդիրը (stable roommates problem) նման է կայուն ամուսնության խնդրին, բայց տարբերվում է նրանով, որ բոլոր մասնակիցները պատկանում են միևնույն տեսակին (հավասար թվով "տղամարդկանց" և "կանանց" բաժանված լինելու փոխարեն)։

Հիվանդանոցներ/բնակիչներ խնդիրը (hospitals/residents problem) - նաև հայտնի որպես քոլեջի ընդունելության խնդիր - տարբերվում է կայուն ամուսնության խնդրից նրանով, որ "կանայք" կարող են ընդունել "առաջարկություններ" ավելի քան մեկ "տղամարդուց" (օրինակ, հիվանդանոցը կարող է ընդունել բազմաթիվ բնակիչներ, կամ քոլեջը կարող է ընդունել մեկից ավելի ուսանող)։ Ալգորիթմը, որը լուծում է հիվանդանոցներ/բնակիչներ խնդիրը կարող է լինել հիվանդանոցի կողմնորոշում ունեցող (իգական օպտիմալ) կամ բնակիչների կողմնորոշում ունեցող (արական օպտիմալ)։

Հիվանդանոցներ/բնակիչներ խնդիրը զույգերով (hospitals/residents problem with couples) թույլ է տալիս բնակիչների մեծամասնությանը կազմել զույգեր, ովքեր պետք է միասին նշանակված լինեն կամ նույն հիվանդանոցում, կամ զույգի կողմից ընտրված որոշակի զույգ հիվանդանոցներում (օրինակ, ամուսնացած զույգը ցանկանում է երաշխավորել, որ նրանք կմնան միասին և չեն մնա այն ծրագրերում, որոնք գտնվում են իրարից հեռու)։ Զույգերի ավելացումը հիվանդանոցներ/բնակիչներ խնդրին ներկայացնում է NP-խնդիրը ամբողջությամբ[4]։

Տես նաև

[խմբագրել | խմբագրել կոդը]

Ծանոթագրություններ

[խմբագրել | խմբագրել կոդը]
  1. ↑ Stable Matching Algorithms
  2. ↑ D. Gale and L. S. Shapley: "College Admissions and the Stability of Marriage", American Mathematical Monthly 69, 9-14, 1962.
  3. ↑ Harry Mairson: "The Stable Marriage Problem", The Brandeis Review 12, 1992 (online).
  4. ↑ D. Gusfield and R. W. Irving, The Stable Marriage Problem: Structure and Algorithms, p. 54; MIT Press, 1989.

Դասագրքեր և այլ կարևոր հղումներ, որոնք չեն մեջբերվել տեքստում

[խմբագրել | խմբագրել կոդը]
  • Dubins, L., and Freedman, D. (1981). Machiavelli and the Gale-Shapley algorithm. The American Mathematical Monthly, 88(7), 485–494.
  • Knuth, D. E. (1976). Marriages stables. Montreal։ Les Presses de I'Universite de Montreal.
  • Roth, A. E. (1984). The evolution of the labor market for medical interns and residents։ A case study in game theory. Journal of Political Economy, 92, 991–1016.
  • Roth, A. E., and Sotomayor, M. A. O. (1990). Two-sided matching։ A study in game-theoretic modeling and analysis. Cambridge University Press.
  • Shoham, Yoav; Leyton-Brown, Kevin (2009). Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. New York: Cambridge University Press. ISBN 978-0-521-89943-7. See Section 10.6.4; downloadable free online.
  • Schummer, J., and Vohra, R. V. (2007). Mechanism design without money. In Nisan, N., Roughgarden, T., Tardos, E., and Vazirani, V. (Eds.). (2007). Algorithmic game theory. Cambridge, UK։ Cambridge University Press, chapter 10, 243–265.
  • Kleinberg, J., and Tardos, E. (2005) Algorithm Design, Chapter 1, pp 1–12. See companion website for the Text [1] Արխիվացված 2011-05-14 Wayback Machine.

Արտաքին հղումներ

[խմբագրել | խմբագրել կոդը]