 |
 |
Ureyim.az |  |
 |
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.[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]
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.
Macar alqoritmi aşağıdakı sahələrdə geniş tətbiq olunur:
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:
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.
 |
 |
UREYIM.AZ |  |
 |
|
