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

Հունգարական ալգորիթմ
Տեսակ	ալգորիթմ
Հայտնաբերող	Հարոլդ Կուհն

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

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

Խնդիր խմբագրել

Օրինակ խմբագրել

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

Առաջադրանք Աշխատող	Մաքրել լոգարանը	Սրբել հատակը	Լվանալ պատուհանները
Անի	$8	$4	$7
Բարսեղ	$5	$2	$3
Գոհար	$9	$4	$8

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

Մաքրել Սրբել	Անի	Բարսեղ	Գոհար
Անի	—	$17	$16
Բարսեղ	$18	—	$18
Գոհար	$15	$16	—

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

Մատրիցով ներկայացում խմբագրել

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

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

\min _{P}\operatorname {Tr} (PC)\;,

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

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

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

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

Ծանոթագրություններ խմբագրել

↑ 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.
↑ «Presentation». Արխիվացված է օրիգինալից 2015 թ․ հոկտեմբերի 16-ին.
↑ J. Munkres, "Algorithms for the Assignment and Transportation Problems", Journal of the Society for Industrial and Applied Mathematics, 5(1):32–38, 1957 March.
↑ Edmonds, Jack; Karp, Richard M. (1972 թ․ ապրիլի 1). «Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems». Journal of the ACM (անգլերեն). 19 (2): 248–264. doi:10.1145/321694.321699. S2CID 6375478.
↑ Tomizawa, N. (1971). «On some techniques useful for solution of transportation network problems». Networks (անգլերեն). 1 (2): 173–194. doi:10.1002/net.3230010206. ISSN 1097-0037.
↑ Jonker, R.; Volgenant, A. (1987 թ․ դեկտեմբեր). «A shortest augmenting path algorithm for dense and sparse linear assignment problems». Computing. 38 (4): 325–340. doi:10.1007/BF02278710. S2CID 7806079.

[kuhn1955-1] Harold W. Kuhn, "The Hungarian Method for the assignment problem", Naval Research Logistics Quarterly, 2: 83–97, 1955. Kuhn's original publication.

[kuhn1956-2] Harold W. Kuhn, "Variants of the Hungarian method for assignment problems", Naval Research Logistics Quarterly, 3: 253–258, 1956.

[3] «Presentation». Արխիվացված է օրիգինալից 2015 թ․ հոկտեմբերի 16-ին.

[munkres-4] J. Munkres, "Algorithms for the Assignment and Transportation Problems", Journal of the Society for Industrial and Applied Mathematics, 5(1):32–38, 1957 March.

[5] Edmonds, Jack; Karp, Richard M. (1972 թ․ ապրիլի 1). «Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems». Journal of the ACM (անգլերեն). 19 (2): 248–264. doi:10.1145/321694.321699. S2CID 6375478.

[6] Tomizawa, N. (1971). «On some techniques useful for solution of transportation network problems». Networks (անգլերեն). 1 (2): 173–194. doi:10.1002/net.3230010206. ISSN 1097-0037.

[JVAlg-7] Jonker, R.; Volgenant, A. (1987 թ․ դեկտեմբեր). «A shortest augmenting path algorithm for dense and sparse linear assignment problems». Computing. 38 (4): 325–340. doi:10.1007/BF02278710. S2CID 7806079.

[1]

[2]

[3]

[4]

[5]

[6]

[7]