Macar alqoritmi və ya Macar üsulu ikitərəfli uyğunlaşdırma ing assignment problemini həll etmək üçün istifadə olunan kom

Macar alqoritmi və ya Macar üsulu — ikitərəfli uyğunlaşdırma (ing. assignment) problemini həll etmək üçün istifadə olunan kombinator alqoritm.Bu alqoritm ilk dəfə macar riyaziyyatçısı nəticələrinə əsaslanaraq tərəfindən 1955-ci ildə təqdim edilmişdir. Kun bu alqoritmə "Macar üsulu" adını məhz macar alimlərinə ehtiram əlaməti olaraq vermişdir.

Tarixi

Macar alqoritmi ilk dəfə 1955-ci ildə amerikalı riyaziyyatçı Harold U. Kun tərəfindən təqdim edilmişdir.Kun bu alqoritmi macar riyaziyyatçısı Çarlz Eqervarinin nəticələrinə əsaslanaraq hazırlamış və alqoritmə "Macar üsulu" adını vermişdir. Eqervari 1931-ci ildə dərc etdiyi işində ikitərəfli qraflarda maksimum uyğunluq problemini dəyərləndirən nəzəri əsaslar qoymuşdur. Kun həmin nəzəriyyələri praktik alqoritmik formaya salaraq assignment problem üçün səmərəli həll üsulu təklif etmişdir.

1957-ci ildə amerikalı riyaziyyatçı Ceyms Munkres bu alqoritmi daha da inkişaf etdirərək onu sistemləşdirmiş və təkmilləşdirmişdir. Bu səbəbdən, bəzi mənbələrdə bu metod Kun–Munkres alqoritmi kimi də adlandırılır. Munkres alqoritmin implementasiyasını sadələşdirmiş və onu müxtəlif praktik sahələrdə tətbiq etmək mümkün olmuşdur.

Macar alqoritmi XX əsrin ikinci yarısından etibarən əməliyyatlar tədqiqi, optimallaşdırma nəzəriyyəsi, sənaye mühəndisliyi və kompüter elmlərində geniş tətbiq tapmışdır.Xüsusilə kompüterləşmə dövründə bu alqoritm süni intellekt, maşın öyrənməsi və robot texnikası sahələrində obyektlərin uyğunlaşdırılması və planlaşdırma kimi məsələlərin həllində mühüm rol oynamışdır.

Günümüzdə Macar alqoritmi yalnız nəzəri riyaziyyatda deyil, həm də real həyatda qarşılaşılan çoxsaylı qərar qəbuletmə və resurs bölgüsü problemlərində istifadə olunur.

Tətbiq sahələri

Macar alqoritmi aşağıdakı sahələrdə geniş tətbiq olunur:

Tapşırıqların icraçılara optimal şəkildə təyin olunması (ing. assignment problem)
İş planlaşdırması və resurs bölgüsü
Robotların koordinasiyası
Nəqliyyat və logistika
Kompüter görməsi və obyektlərin uyğunlaşdırılması

Problemin tərifi

Assignment problemi aşağıdakı kimi formalaşdırılır: Verilmiş n×n ölçülü dəyər matrisi (məsələn, məsrəf, zaman və ya məsafə matrisləri) üzrə hər bir iş bir işçiyə elə təyin olunmalıdır ki, ümumi məsrəf minimum (və ya maksimum) olsun. Hər iş yalnız bir işçiyə, hər işçi yalnız bir işə təyin edilə bilər.

Macar alqoritmi aşağıdakı əsas mərhələlərlə həyata keçirilir:

Sətir normallaşdırması — hər bir sətirdəki minimum dəyər çıxılaraq matrisdə sıfırlar yaradılır.
Sütun normallaşdırması — eyni əməliyyat sütunlar üzrə həyata keçirilir.
Sıfırların örtülməsi — ən az sayda sətir və sütun istifadə edərək bütün sıfırlar örtülür.
Optimallığın yoxlanması — əgər örtükdə istifadə olunan xətlərin sayı n-ə bərabərdirsə, optimal uyğunluq tapılmışdır.
Matrisin düzəldilməsi — əgər optimal həll hələ tapılmayıbsa, örtülməmiş elementlərdən ən kiçik dəyər seçilir, bu dəyər örtülməmiş elementlərdən çıxılır və örtülmüş kəsişən elementlərə əlavə edilir. Bu proses uyğunluq tapılanadək təkrarlanır.

Məsələn

Aşağıdakı məsrəf matrisi verilmiş olsun:

	A	B	C
1	9	2	7
2	6	4	3
3	5	8	1

Macar alqoritmi vasitəsilə bu tapşırıqlar elə uyğunlaşdırılır ki, ümumi məsrəf minimum olur.Macar alqoritmi dəyişməzlik prinsipi, duallıq nəzəriyyəsi və qraf nəzəriyyəsi (xüsusilə ikiqat qrafda maksimum uyğunluq) əsasında işləyir. Bu alqoritm polinomial zamanlı alqoritm olmaqla, O(n³) zaman mürəkkəbliyinə malikdir.

İstinadlar

"Hungarian Algorithm for Solving the Assignment Problem". e-maxx :: algo. August 23, 2012. May 14, 2023 tarixində arxivləşdirilib. İstifadə tarixi: May 13, 2023.
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". 16 October 2015 tarixində arxivləşdirilib.
Java implementation claiming $O(n^{3})$ time complexity Arxiv surəti 23 yanvar 2022 tarixindən (Wayback Machine) saytında Python implementation Arxiv surəti 24 noyabr 2020 tarixindən (Wayback Machine) saytında
J. Munkres, "Algorithms for the Assignment and Transportation Problems", Journal of the Society for Industrial and Applied Mathematics, 5(1):32–38, 1957 March.
Flood, Merrill M. "The Traveling-Salesman Problem". Operations Research. 4 (1). 1956: 61–75. doi:10.1287/opre.4.1.61. ISSN 0030-364X.
Edmonds, Jack; Karp, Richard M. "Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems". Journal of the ACM (ingilis). 19 (2). 1972-04-01: 248–264. doi:10.1145/321694.321699.
Tomizawa, N. "On some techniques useful for solution of transportation network problems". Networks (ingilis). 1 (2). 1971: 173–194. doi:10.1002/net.3230010206. ISSN 1097-0037.
"Solving assignment problem using min-cost-flow". Algorithms for Competitive Programming. July 17, 2022. May 14, 2023 tarixində arxivləşdirilib. İstifadə tarixi: May 14, 2023.
Jacob Kogler. "Minimum-cost flow - Successive shortest path algorithm". Algorithms for Competitive Programming. December 20, 2022. İstifadə tarixi: May 14, 2023.

Xarici keçidlər

Bruff, Derek, The Assignment Problem and the Hungarian Method (matrix formalism).
Mordecai J. Golin, Bipartite Matching and the Hungarian Method (biograph formalism), Course Notes, Hong Kong University of Science and Technology.
Hungarian maximum matching algorithm (both formalisms), in Brilliant website.
R. A. Pilgrim, Munkres' Assignment Algorithm. Modified for Rectangular Matrices, Course notes, Murray State University.
Mike Dawes, The Optimal Assignment Problem, Course notes, University of Western Ontario.
On Kuhn's Hungarian Method – A tribute from Hungary, András Frank, Egervary Research Group, Pazmany P. setany 1/C, H1117, Budapest, Hungary.
Lecture: Fundamentals of Operations Research — Assignment Problem — Hungarian Algorithm, Prof. G. Srinivasan, Department of Management Studies, IIT Madras.
Extension: Assignment sensitivity analysis (with O(n^4) time complexity), Liu, Shell.
Solve any Assignment Problem online, provides a step by step explanation of the Hungarian Algorithm.

[1] "Hungarian Algorithm for Solving the Assignment Problem". e-maxx :: algo. August 23, 2012. May 14, 2023 tarixində arxivləşdirilib. İstifadə tarixi: May 13, 2023.

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

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

[4] "Presentation". 16 October 2015 tarixində arxivləşdirilib.

[5] Java implementation claiming $O(n^{3})$ time complexity Arxiv surəti 23 yanvar 2022 tarixindən (Wayback Machine) saytında Python implementation Arxiv surəti 24 noyabr 2020 tarixindən (Wayback Machine) saytında

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

[flood-7] Flood, Merrill M. "The Traveling-Salesman Problem". Operations Research. 4 (1). 1956: 61–75. doi:10.1287/opre.4.1.61. ISSN 0030-364X.

[8] Edmonds, Jack; Karp, Richard M. "Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems". Journal of the ACM (ingilis). 19 (2). 1972-04-01: 248–264. doi:10.1145/321694.321699.

[9] Tomizawa, N. "On some techniques useful for solution of transportation network problems". Networks (ingilis). 1 (2). 1971: 173–194. doi:10.1002/net.3230010206. ISSN 1097-0037.

[10] "Solving assignment problem using min-cost-flow". Algorithms for Competitive Programming. July 17, 2022. May 14, 2023 tarixində arxivləşdirilib. İstifadə tarixi: May 14, 2023.

[11] Jacob Kogler. "Minimum-cost flow - Successive shortest path algorithm". Algorithms for Competitive Programming. December 20, 2022. İstifadə tarixi: May 14, 2023.