Մասնակից:Araqsya Manukyan/Սևագրություն
Սա Araqsya Manukyan մասնակցի սևագրության էջն է՝ «ավազարկղը», և մասնակցի էջի ենթաէջերից մեկն է։ Այն ծառայում է որպես սևագիր և փորձարկումների վայր։ Սա հանրագիտարանային հոդված չէ։ Ձեր անձնական ավազարկղը ստեղծելու համար սեղմեք այստեղ։ Այլ ավազարկղեր՝ Ընդհանուր ավազարկղ |
Մաթեմատիկայում և համակարգչային գիտության մեջ կայուն ամուսնության խնդիրը (SMP) յուրաքանչյուր տարրի համար տրված մի շարք նախասիրությունների պայմաններում տարրի երկու խմբերի միջև կայուն համապատասխանություն գտնելն է: Համապատասխանությունը մի խմբի տարրերի քարտեզագրումն է մյուս խմբի տարրերի հետ: Համապատասխանությունը կայուն է բոլոր դեպքերում, բացի հետևյալ երկուսից.
- Առաջինը ընտրված խմբի տրված A տարրերից որոշները ավելի նախապատվությունը տալիս են երկրորդը ընտրված խմբի տրված B տարրերից որոշներին, քան մի տարրի, որին արդեն A-ն համապատասխանեցրած է, և
- B-ն նույնպես գերադասում է A-ն, քան այն տարրը, որին B-ն արդեն համապատասխանում է
Այսինքն, համապատասխանությունը կայուն է, երբ գոյություն չունի որևէ այլընտրանքային զույգ (A, B), որում և A-ն և B-ն անհատապես կլինեն ավելի լավը, քան կլինեին այն տարրի հետ, որին նրանք իրականում համապատասխանում են:
Կայուն ամուսնության խնդիրը սովորաբար ձևակերպվում է հետևյալ կերպ. Տրված են n տղամարդ և n կին, որտեղ յուրաքանչյուր ոք ըստ նախասիրության համարակալել է հակառակ սեռի բոլոր անդամներին եզակի թվերով 1-ից մինչև n , ամուսնացրել տղամարդկանց և կանանց այնպես, որ չլինեն հակառակ սեռի երկու մարդ, որոնք ավելի կնախընտրեին մեկ ուրիշի, քան իրենց զուգընկերոջը: Եթե չկան այդպիսի մարդիկ, բոլոր ամուսնությունները "կայուն" են:
Կայուն ամուսնության խնդրի լուծման ալգորիթմները լուծում են գտնում իրական աշխարհի տարբեր իրավիճակներում, որոնցից ամենահայտնին հանդիսանում է բժիշկ շրջանավարտների նշանակումը իրենց առաջին հիվանդանոցում:[1]
Լուծում[խմբագրել | խմբագրել կոդը]
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]
Տես նաև[խմբագրել | խմբագրել կոդը]
- Assignment problem
- Stable roommates problem a similar problem, but with one set of size n and n-1 preferences
Հղումներ[խմբագրել | խմբագրել կոդը]
- ↑ Stable Matching Algorithms
- ↑ D. Gale and L. S. Shapley: "College Admissions and the Stability of Marriage", American Mathematical Monthly 69, 9-14, 1962.
- ↑ Harry Mairson: "The Stable Marriage Problem", The Brandeis Review 12, 1992 (online).
- ↑ 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].
Արտաքին հղումներ[խմբագրել | խմբագրել կոդը]
- Interactive Flash Demonstration of SMP
- http://kuznets.fas.harvard.edu/~aroth/alroth.html#NRMP
- http://www.dcs.gla.ac.uk/research/algorithms/stable/EGSapplet/EGS.html
- Gale-Shapley JavaScript Demonstration
- SMP Lecture Notes
Category:Game theory Category:Cooperative games Category:Mathematical problems Category:Matching hy:Կայուն ամուսնության խնդիրը