Հունգարական ալգորիթմ

Հունգարական ալգորիթմ կամ հունգարական մեթոդ, կոմբինատոր օպտիմիզացիայի ալգորիթմ, որը լուծում է նշանակման խնդիրը բազմանդամային ժամանակում և որը ենթադրում է նախնական երկակի մեթոդներ։ Այն մշակվել և հրապարակվել է Հարոլդ Կուհնի կողմից 1955-ին, ով տվել է «Հունգարական մեթոդ» անվանումը, քանիր որ ալգորիթմը մեծ մասամբ հիմնված էր հունգարացի մաթեմատիկոսներ՝ Դենես Կոնիգի և Յենո Էգեվարիի աշխատանքների վրաHarold W. Kuhn, "The Hungarian Method for the assignment problem", Naval Research Logistics Quarterly, 2: 83–97, 1955.  Kuhn's original publication.Harold W. Kuhn, "Variants of the Hungarian method for assignment problems", Naval Research Logistics Quarterly, 3: 253–258, 1956.։ Սակայն, 2006 թվականին հայտնաբերվել է, որ  Կառլ Գուստավ Յակոբը լուծել էր նշանակման խնդիրը 19-րդ դարում, իսկ լուծումը հետմահու հրատարակվել էր 1890 թվականին (լատիներեն)։

Ջեյմս Մունկրեսը 1957 թվականին ալգորիթմը ուսումնասիրելիս նկատել է, որ այն (խիստ) բազմանդամային էJ. Munkres, "Algorithms for the Assignment and Transportation Problems", Journal of the Society for Industrial and Applied Mathematics, 5(1):32–38, 1957 March.։ Այս պատճառով ալգորիթմը երբմեն կոչում են Կուհն-Մունկրեսի ալգորիթմ կամ Մունկրեսի նշանակման ալգորիթմ։ Նախնական ալգորիթմի ժամանակի բարդությունը  էր, սակայն Ջեք Էդմոնդսը Ռիչարդ Կարպը նկատել է, որ հնարավոր է այն ձևափոխել է ստանալ  արագությամբ ալգորիթմ (այս եզրակացությանը անկախ հանգել է նաև Ն. Տոմիզավան)։ Ջոնկեր-Վոլգենտի ալգորիթը հունգարական մեթոդի  արագությամբ տարբերակներից է։ Ֆորդ-ֆալկերսոնի ալգորիթմը այս ալգորիթմի ընդարձակված տարբերակ է։

 Խնդիր 

 Օրինակ 
Այս պարզ օրինակում կան երեք աշխատողներ. Անին, Բարսեղը և Գոհարը Նրանցից մեկը պետք է մաքրի լոգարանը, մյուսը պետք է սրբի հատակը իսկ երրորդը պետք է լվանա պատուհանները, բայց նրանցից յուրաքանչյուրը տարբեր աշխատանքների համար տարբեր աշխատավարձ են պահանջում։ Խնդիրն է գտնել աշխատանքները աշխատողներին նշանակելու ամենաէժան տարբերակը։ Խնդիրը կարելի է ներկայացնել աշխատողների պահանջած աշխատավարձների մատրիցի տեսքով։ Օրինակ,
{| class="wikitable" style="text-align:center;"
! 
! Մաքրելլոգարանը
! Սրբելհատակը
! Լվանալպատուհանները
|-
! Անի
| $8
| $4
| $7
|-
! Բարսեղ
| $5
| $2
| $3
|-
! Գոհար
| $9
| $4
| $8
|}

Հունգարական մեթոդով այս խնդիրը լուծելու դեպքում կստանքն հետևյալ նշանակումը՝ Անին պետք մաքրի լոգարանները, Գոհարը պետք է սրբի հատակը, իսկ Բարսեղը պետք է լվանա պատուհանները, որը ընդհանուր գինը կկազմի $15։ Լուծումը կարելի է ստուգել բոլոր տարբերակները փորձելով.
{| class="wikitable" style="text-align:center;"
! 
! Անի
! Բարսեղ
! Գոհար
|-
! Անի
| —
| $17
| $16
|-
! Բարսեղ
| $18
| —
| $18
|-
! Գոհար
| $15
| $16
| —
|} (չնշանակված աշխատողը լվանում է պատուհանները)

 Մատրիցով ներկայացում 
Մատրիցով ներկայացման դեպքում տրված է n×n չափի ոչբացասական մատրից, որը i տողը և j սյան արժեքը հավասար է j աշխատանքն անելու համար i աշխատողի պահանջած վարձին։ Պետք է գտնել այնպիսի նշանակում, որ յուրաքանչյուր աշխատող ունենա ճիշտ մեկ աշխատանք և ընդհանուր գինը նվազագույնը լինի։ 

Սա կարելի է ներկայացնել որպես տրված C մատրիցի տողերի այնպիսի տեղափոխություն, որի հիմնական անկյունագծային գումարը նվազագույնն է, այսինքն

որտեղ P-ը տեղափոխված մատրիցն է։

Եթե պետք է գտնել առավելագույն գունը, ուրեմն պետք է պարզապես C մատրիցի գները դարձնել բացասական։

 Երկկողմանի գրաֆներով ներկայացում 
Ալգորիթմը հնարավոր է համարժեք նկարագրել, եթե խնդիրը ներկայացվի երկկողմ գրաֆով։ Ունենք  լրիվ երկկողմ գրաֆը,  գագաթները համապատասխանում են  աշխատողներին, իսկ  գագաթները՝  աշխատանքներին, իսկ  կշռով կողորը () համապատասխանում են աշխատողի պահանջած աշխատավարձին։ Այս դեպքում պետք է գտնել նավազագույն գնով կատարյալ զուգակցում։

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

Կատեգորիա:Ալգորիթմներ