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

Կաղապար:Տեղեկաքարտ Ալգորիթմ Հունգարական ալգորիթմ կամ հունգարական մեթոդ, կոմբինատոր օպտիմիզացիայի ալգորիթմ, որը լուծում է նշանակման խնդիրը բազմանդամային ժամանակում և որը ենթադրում է նախնական երկակի մեթոդներ։ Այն մշակվել և հրապարակվել է Հարոլդ Կուհնի կողմից 1955-ին, ով տվել է «Հունգարական մեթոդ» անվանումը, քանիր որ ալգորիթմը մեծ մասամբ հիմնված էր հունգարացի մաթեմատիկոսներ՝ Դենես Կոնիգի և Յենո Էգեվարիի աշխատանքների վրա։ Սակայն, 2006 թվականին հայտնաբերվել է, որ Կառլ Գուստավ Յակոբը լուծել էր նշանակման խնդիրը 19-րդ դարում, իսկ լուծումը հետմահու հրատարակվել էր 1890 թվականին (լատիներեն)։

Ջեյմս Մունկրեսը 1957 թվականին ալգորիթմը ուսումնասիրելիս նկատել է, որ այն (խիստ) բազմանդամային է։ Այս պատճառով ալգորիթմը երբմեն կոչում են Կուհն-Մունկրեսի ալգորիթմ կամ Մունկրեսի նշանակման ալգորիթմ։ Նախնական ալգորիթմի ժամանակի բարդությունը $O(n^4)$ էր, սակայն Ջեք Էդմոնդսը Ռիչարդ Կարպը նկատել է, որ հնարավոր է այն ձևափոխել է ստանալ $O(n^3)$ արագությամբ ալգորիթմ (այս եզրակացությանը անկախ հանգել է նաև Ն. Տոմիզավան)։ Ջոնկեր-Վոլգենտի ալգորիթը հունգարական մեթոդի $O(n^3)$ արագությամբ տարբերակներից է։ Ֆորդ-ֆալկերսոնի ալգորիթմը այս ալգորիթմի ընդարձակված տարբերակ է։

Խնդիր

Օրինակ

Այս պարզ օրինակում կան երեք աշխատողներ. Անին, Բարսեղը և Գոհարը Նրանցից մեկը պետք է մաքրի լոգարանը, մյուսը պետք է սրբի հատակը իսկ երրորդը պետք է լվանա պատուհանները, բայց նրանցից յուրաքանչյուրը տարբեր աշխատանքների համար տարբեր աշխատավարձ են պահանջում։ Խնդիրն է գտնել աշխատանքները աշխատողներին նշանակելու ամենաէժան տարբերակը։ Խնդիրը կարելի է ներկայացնել աշխատողների պահանջած աշխատավարձների մատրիցի տեսքով։ Օրինակ,

Կաղապար:Diagonal split header	Մաքրել լոգարանը	Սրբել հատակը	Լվանալ պատուհանները
Անի	$8	$4	$7
Բարսեղ	$5	$2	$3
Գոհար	$9	$4	$8

Հունգարական մեթոդով այս խնդիրը լուծելու դեպքում կստանքն հետևյալ նշանակումը՝ Անին պետք մաքրի լոգարանները, Գոհարը պետք է սրբի հատակը, իսկ Բարսեղը պետք է լվանա պատուհանները, որը ընդհանուր գինը կկազմի $15։ Լուծումը կարելի է ստուգել բոլոր տարբերակները փորձելով.

Կաղապար:Diagonal split header	Անի	Բարսեղ	Գոհար
Անի	—	$17	$16
Բարսեղ	$18	—	$18
Գոհար	$15	$16	—

(չնշանակված աշխատողը լվանում է պատուհանները)

Մատրիցով ներկայացում

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

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

$\underset{P}{\min }\mathrm{Tr}(PC),$

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

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

Երկկողմանի գրաֆներով ներկայացում

Ալգորիթմը հնարավոր է համարժեք նկարագրել, եթե խնդիրը ներկայացվի երկկողմ գրաֆով։ Ունենք $G=(S,T;E)$ լրիվ երկկողմ գրաֆը, Կաղապար:Mvar գագաթները համապատասխանում են Կաղապար:Mvar աշխատողներին, իսկ Կաղապար:Mvar գագաթները՝ Կաղապար:Mvar աշխատանքներին, իսկ $c(i,j)$ կշռով կողորը (Կաղապար:Mvar) համապատասխանում են աշխատողի պահանջած աշխատավարձին։ Այս դեպքում պետք է գտնել նավազագույն գնով կատարյալ զուգակցում։