Կայուն ամուսնության խնդիր
From Wikipedia, the free encyclopedia
Մաթեմատիկայում և համակարգչային գիտության մեջ կայուն ամուսնության խնդիրը (SMP) յուրաքանչյուր տարրի համար տրված մի շարք նախասիրությունների պայմաններում տարրի երկու խմբերի միջև կայուն համապատասխանություն գտնելն է։ Համապատասխանությունը մի խմբի տարրերի քարտեզագրումն է մյուս խմբի տարրերի հետ։ Համապատասխանությունը կայուն է բոլոր դեպքերում, բացի հետևյալ երկուսից.
- Առաջինը ընտրված խմբի տրված A տարրերից որոշները ավելի նախապատվությունը տալիս են երկրորդը ընտրված խմբի տրված B տարրերից որոշներին, քան մի տարրի, որին արդեն A-ն համապատասխանեցրած է, և
- B-ն նույնպես գերադասում է A-ն, քան այն տարրը, որին B-ն արդեն համապատասխանում է
Այսինքն, համապատասխանությունը կայուն է, երբ գոյություն չունի որևէ այլընտրանքային զույգ (A, B), որում և A-ն և B-ն անհատապես կլինեն ավելի լավը, քան կլինեին այն տարրի հետ, որին նրանք իրականում համապատասխանում են։
Կայուն ամուսնության խնդիրը սովորաբար ձևակերպվում է հետևյալ կերպ. Տրված են n տղամարդ և n կին, որտեղ յուրաքանչյուր ոք ըստ նախասիրության համարակալել է հակառակ սեռի բոլոր անդամներին եզակի թվերով 1-ից մինչև n, ամուսնացրել տղամարդկանց և կանանց այնպես, որ չլինեն հակառակ սեռի երկու մարդ, որոնք ավելի կնախընտրեին մեկ ուրիշի, քան իրենց զուգընկերոջը։ Եթե չկան այդպիսի մարդիկ, բոլոր ամուսնությունները "կայուն" են։
Կայուն ամուսնության խնդրի լուծման ալգորիթմները լուծում են գտնում իրական աշխարհի տարբեր իրավիճակներում, որոնցից ամենահայտնին հանդիսանում է բժիշկ շրջանավարտների նշանակումը իրենց առաջին հիվանդանոցում[1]։