Macar alqoritmi
Macar alqoritmi və ya Macar üsulu — ikitərəfli uyğunlaşdırma (Şablon:Dil-en) problemini həll etmək üçün istifadə olunan kombinator alqoritm.[1]Bu alqoritm ilk dəfə macar riyaziyyatçısı Yeno Eqervarinin nəticələrinə əsaslanaraq Harold Kun 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.[2][3]
Tarixi
Macar alqoritmi ilk dəfə 1955-ci ildə amerikalı riyaziyyatçı Harold U. Kun tərəfindən təqdim edilmişdir.[4]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.[5]
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.[6]
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.[7]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.[8][9]
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ı (Şablon:Dil-en)
- İş 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.[10]
- 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.[11]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
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.
- ↑ Şablon:Cite web
- ↑ 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.
- ↑ Şablon:Cite web
- ↑ Java implementation claiming time complexity Şablon:Wayback Python implementation Şablon:Wayback
- ↑ J. Munkres, "Algorithms for the Assignment and Transportation Problems", Journal of the Society for Industrial and Applied Mathematics, 5(1):32–38, 1957 March.
- ↑ Şablon:Cite journal
- ↑ Şablon:Cite journal
- ↑ Şablon:Cite journal
- ↑ Şablon:Cite web
- ↑ Şablon:Cite web