Magyar algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. március 4-én felülvizsgált verziótól ; az ellenőrzések 6 szerkesztést igényelnek .

A magyar algoritmus egy olyan optimalizáló algoritmus, amely a hozzárendelési problémát polinomiális időben oldja meg (lásd: Műveletekkutatás ). Harold Kuhn fejlesztette ki és adta ki 1955 -ben . A szerző a "Magyar Módszer" nevet adta annak, hogy az algoritmus nagyrészt két magyar matematikus König és Egerváry

James Mancres 1957-ben megfigyelte, hogy az algoritmus (szigorúan) polinomiális. Azóta az algoritmust Kuhn-Mankres algoritmusként vagy a hozzárendelési probléma megoldására szolgáló Mankres algoritmusként is ismerik . Az eredeti algoritmus időbeli összetettsége az volt , de Edmonds Karp valamint megmutatta, hogy módosítható a futási idő eléréséhez. A módosított magyar algoritmust Hopcroft-Karp algoritmusnak nevezzük. Ford és Fulkerson kiterjesztette a módszert az általános közlekedési problémákra. 2006-ban kiderült, hogy Jacobi 19. századi megoldást talált a feladatkiosztás problémájára, amelyet latinul tettek közzé egy 1890-es posztumusz iratgyűjteményben. [1] [2] $O(n^{4})$ $O(n^{3})$

Példa

Tegyük fel, hogy három alkalmazott van: Ivan, Peter és Andrey. Három munkatípus (amit A-nak, B-nek, C-nek nevezünk) elvégzését kell elosztani közöttük, minden dolgozónak csak egyfajta munkát kell végeznie. Hogyan lehet ezt úgy csinálni, hogy a legkevesebb pénzt költsük a dolgozók bérére? Először is fel kell építeni egy költségmátrixot .

	A	B	C
Ivan	10.000 dörzsölje.	20.000 dörzsölje.	30.000 dörzsölje.
Péter	30.000 dörzsölje.	30.000 dörzsölje.	30.000 dörzsölje.
András	30.000 dörzsölje.	30.000 dörzsölje.	20.000 dörzsölje.

A fenti táblázatra alkalmazott magyar algoritmus megadja a szükséges eloszlást: Ivan A feladatot, Péter B, Andrey C munkát végez.

A probléma leírása

Adott egy nemnegatív n × n mátrix , ahol az i - edik sor és a j -edik oszlop eleme megfelel az i - edik munkás által a j -edik típusú munka elvégzésének költségének. Meg kell találni a munka és az alkalmazottak közötti megfelelést, hogy a munkaerőköltségek a legalacsonyabbak legyenek. Ha a cél a legmagasabb költségű úti cél megtalálása, akkor a megoldás az imént megfogalmazott probléma megoldására redukálódik úgy, hogy minden C költséget a maximális költség és C különbségével helyettesítünk . [3]

Fő ötletek

Az algoritmus két ötleten alapul:

ha ugyanazt a számot kivonjuk egy bizonyos sor vagy oszlop összes eleméből , akkor az összköltség -kal csökken , és az optimális megoldás nem változik; $y$ $y$
ha van zéró költségű megoldás, akkor az optimális.

Az algoritmus az egyes sorok és oszlopok összes eleméből kivonandó értékeket keres (különböző soroknál és oszlopoknál eltérő), így a mátrix összes eleme nem negatív marad, de nulla megoldás jelenik meg.

Definíciók

Az algoritmus könnyebben leírható, ha a problémát egy bipartit gráf segítségével fogalmazzuk meg . Adott egy teljes kétrészes G=(S, T; E) gráf, melynek n csúcsa az alkalmazottaknak ( S ) és n csúcsa a munkatípusoknak ( T ) felel meg; minden c(i, j) él költsége nem negatív. Meg kell találni a tökéletes vagy teljes párosítást a legalacsonyabb költséggel.

Meghívjuk a függvénypotenciált , ha mindegyik esetén . A potenciálértéket a következőképpen határozzuk meg . Könnyen belátható, hogy a tökéletes illeszkedés költsége nem kevesebb, mint bármely potenciál értéke. A magyar módszer teljes illeszkedést és potenciált talál azonos költség/érték mellett, ami azt bizonyítja, hogy mindkét mennyiség optimális. Valójában megtalálja a merev élek tökéletes illeszkedését: egy élről azt mondják, hogy merev a potenciálra , ha . A merev él részgráfot a következővel jelöljük . A teljes egyezés költsége -ben (ha létezik) egyenlő: . $y\colon (S\cup T)\to \mathbb {R}$ $y(i)+y(j)\leq c(i,j)$ $i\in S,j\in T$ $y=\sum _{v\in S\cup T}y(v)$ $ij$ $y$ $y(i)+y(j)=c(i,j)$ ${\mathbf {G_{y))}$ ${\mathbf {G_{y))}$ $y$

Algoritmus kétrészes gráfok szempontjából

Az algoritmus a memóriában tárolja az egyes merev élek potenciálját és orientációját (az irányt beállítva), aminek megvan az a tulajdonsága, hogy az élek ahonnan az élek irányulnak, hogy illeszkedést képezzenek, amit -vel jelölünk . Adott orientációjú merev élekből álló irányított gráfot jelöljük . Így minden pillanatban háromféle él létezik: $y\$ $T\$ $S\$ $M$ $\mathbf {{\overrightarrow {G}}_{y}}$

nem merev (és nem hozzátartozó ) $M\$
kemény, de nem hozzátartozó $M\$
kemény és birtokolt $M\$

Kezdetben mindenhol 0, és minden él innentől ig irányul (tehát üres). Minden lépésben vagy módosul úgy, hogy a következő bekezdésben definiált csúcsok halmaza megnövekszik, vagy az orientáció megváltozik, hogy nagyobb számú élt kapjunk; mindig igaz marad, hogy minden éle merev. A folyamat akkor ér véget, ha tökéletes egyezés. $y\$ $S\$ $T\$ $M\$ $y\$ $Z\$ $M\$ $M\$

Legyen minden lépésben és azoknak a csúcsoknak a halmaza, amelyek nem incidensek a -ból származó élekre (vagyis a -ból származó csúcsok halmaza , amelyek nem tartalmaznak éleket, hanem a -ból származó csúcsok halmazát , ahonnan nem jön ki él). Jelölje a tól -ig elérhető csúcsok halmazával ( a szélesség-első kereséssel megtalálható ). $R_{S}\subseteq S$ $R_{T}\subseteq T$ $M\$ $R_{S}\$ $S$ $R_{T}\$ $T$ $Z\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$

Ha nem üres, az azt jelenti, hogy van legalább egy elérési út tól ig . Ezen utak bármelyikét kiválasztjuk, és az összes élének irányát fordítva változtatjuk. Az egyezés mérete 1-gyel nő. $R_{T}\cap Z$ $\mathbf {{\overrightarrow {G}}_{y}}$ $R_{S}\$ $R_{T}\$

A bizonyításhoz két nyilvánvaló tényt jegyezzünk meg:

A kiválasztott útvonalon a -tól -ig terjedő élek váltakoznak a -tól -ig terjedő élekkel . Ez a bipartit gráfból következik. $S\$ $T\$ $T\$ $S\$
Az útvonal első csúcsa -hoz, az utolsó csúcs pedig -hez tartozik . Ezért az első és az utolsó éle inről -re irányul . $S\$ $T\$ $S\$ $T\$

Definíció szerint ebből következik, hogy a választott úton a hozzátartozó és nem tartozó élek váltakoznak, az első és az utolsó él pedig nem tartozik a -hoz , vagyis az út felemelkedik, amiből a bizonyított állítás következik. $\mathbf {{\overrightarrow {G}}_{y}}$ $M\$ $M\$

Ha üres, tegye be . pozitív, mert és között nincsenek kemény élek . $R_{T}\cap Z$ $\Delta :=\min\{c(i,j)-y(i)-y(j):i\in Z\cap S,j\in T\setminus Z\}$ $\Delta$ $Z\cap S$ $T\setminus Z$

Valóban, legyen egy ilyen él (i, j). Mivel a , de , a csúcs elérhető től -ig , de a csúcs elérhetetlen. $i\in Z$ $j\notin Z$ $én\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$ $j\$

Ezért nem tartalmazhat éleket (i, j). Ezért honnan . Mivel elérhetõ -tól -ig , van egy elérési út a -hoz tartozó valamelyik csúcsból . Tekintsük ennek az útnak az utolsó szélét. Jelölje (k, i). Mivel től ig elérhető , de elérhetetlen, . Mivel , . Ezért beesik a : és két élére , ami lehetetlen, mivel egy illesztés. Ellentmondás. $\mathbf {{\overrightarrow {G}}_{y}}$ $(i,j)\-ben M$ $én\nem R_{S}$ $én\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$ $én\$ $R_{S}\$ $k\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$ $j\$ $k\neq j$ $(k,i)\in \mathbf {{\overrightarrow {G}}_{y}}$ $(i,k)\-ben M$ $én\$ $M\$ $(i,j)\$ $(i,k)\$ $M\$

Növeljünk a -ból származó csúcsokon, és csökkenjünk -al a -ben szereplő csúcsokon . Az új továbbra is potenciális. $y\$ $\Delta$ $Z\cap S$ $y\$ $\Delta$ $Z\sapka T$ $y\$

Valójában bármely élre (i, j), , : $i\in S$ $j\in T$

ha , , akkor c(i, j)-y(i)-y(j) nem változik, mert sem y(i), sem y(j) $nem vagyok Z$ $j\notin Z$
ha , , akkor c(i, j)-y(i)-y(j) nem változik, mert y(i) -vel nő , y(j) pedig ugyanennyivel csökken $i\in Z$ $j\in Z$ $\Delta$
ha , akkor a c(i, j)-y(i)-y(j) különbség növekszik -vel , ezért nem negatív marad $nem vagyok Z$ $j\in Z$ $\Delta$
ha , , akkor a c(i, j)-y(i)-y(j) különbség -vel csökken , de továbbra is nem negatív marad, mert az ilyen különbségek közül a legkisebb. $i\in Z$ $j\notin Z$ $\Delta$ $\Delta$

A grafikon megváltozik, de ennek ellenére tartalmaz . $\mathbf {{\overrightarrow {G}}_{y}}$ $M\$

Valójában ahhoz, hogy valamely (i, j), , , élből kizárjuk, nem merevvé kell tenni, vagyis növelni kell a c(i, j)-y(i)-y(j) különbséget. . Mint láttuk, a különbség csak akkor növekszik, ha , , más szóval elérhetetlen -ból , de elérhető. De ebben az esetben a (j, i) él nem tartozhat -hoz , ezért az él nem tartozik a -hoz . $\mathbf {{\overrightarrow {G}}_{y}}$ $i\in S$ $j\in T$ $nem vagyok Z$ $j\in Z$ $én$ $R_{S}$ $j$ $\mathbf {{\overrightarrow {G}}_{y}}$ $M$

Irányítsa az új éleket inről -re . Definíció szerint a -ból elérhető csúcsok halmaza növekedni fog (és a merev élek száma nem feltétlenül növekszik). $S\$ $T\$ $\Delta$ $Z\$ $R_{S}$

Ennek az állításnak a bizonyítására először bebizonyítjuk, hogy Z-ből egyetlen csúcs sem tűnik el. Legyen . Ezután van egy út valamelyik V-hez tartozó csúcstól V-ig. Ezen az úton minden csúcs elérhető -ból , azaz Z-hez tartozik. Ezen az úton minden él két csúcsra esik Z-ből. Amint fentebb láttuk, ilyen éleknél a c(i, j )-y(i)-y(j) különbség nem változik. Ez azt jelenti, hogy az útvonal minden éle merev marad, és V továbbra is elérhető lesz a -ból . Most bizonyítsuk be, hogy legalább egy csúcs hozzáadódik Z-hez. Tekintsük azt az élt, amelyen elérjük a minimumot . Ennél az élnél a c(i, j)-y(i)-y(j) különbség nulla lesz, ezért merev lesz, és S-ből T-be, azaz i-ből j-be irányul. Mivel , j is elérhetővé válik -ból , azaz hozzáadódik Z-hez. $V\in Z$ $R_{S}$ $R_{S}$ $R_{S}$ $\min\{c(i,j)-y(i)-y(j):i\in Z\cap S,j\in T\setminus Z\}$ $i\in Z$ $R_{S}$

Addig ismételjük ezeket a lépéseket, amíg tökéletes egyezés nem lesz; ebben az esetben a legalacsonyabb költséggel adja meg a megbízást. Az algoritmus ezen verziójának végrehajtási ideje : egyszer van kitöltve , és abban a szakaszban, amikor nem változik, nem lehet több potenciális változás (mivel minden alkalommal növekszik). A potenciál megváltoztatásához szükséges idő . $M\$ $O(n^{4})$ $M\$ $n\$ $M\$ $n\$ $Z\$ $O(n^{2})$

Mátrix értelmezés

Dolgozók és munkák esetében egy n × n mátrix adott, amely meghatározza az egyes munkák költségét minden egyes munkavállaló számára. Határozza meg egy munka elvégzésének minimális költségét úgy, hogy minden dolgozó pontosan egy munkát végez, és minden munkát pontosan egy munkás végez. $n$

A következőkben a megbízáson a dolgozók és a munkakörök közötti megfelelést értjük, amelynek nulla költsége van, miután olyan átalakításokat végeztünk, amelyek csak a munkák összköltségét érintik.

Először is írjuk fel a problémát mátrix formában:

{\begin{bmatrix}a1&a2&a3&a4\\b1&b2&b3&b4\\c1&c2&c3&c4\\d1&d2&d3&d4\end{bmátrix))

ahol a, b, c, d azok a munkavállalók, akiknek az 1., 2., 3., 4. munkakört kell ellátniuk. Az a1, a2, a3, a4 együtthatók az 1., 2., 3., 4. munkavégzés költségét jelölik az „a” alkalmazott által, illetőleg. Más szimbólumok is hasonló jelentéssel bírnak. A mátrix négyzet alakú, így minden dolgozó csak egy munkát végezhet.

1. lépés

Soronként redukáljuk az elemeket. Megkeressük az első sor elemei közül a legkisebbet (a1, a2, a3, a4), és kivonjuk az első sor összes eleméből. Ebben az esetben az első sor legalább egyik eleme nullára lesz állítva. Ugyanezt tesszük az összes többi sorral is. Most a mátrix minden sorában van legalább egy nulla. Néha már a nullák is elegendőek a cél megtalálásához. Egy példa látható a táblázatban. A piros nullák a hozzárendelt munkákat jelzik.

0	a2'	0	a4'
b1'	b2'	b3'	0
0	c2'	c3'	c4'
d1'	0	d3'	d4'

Nagyszámú nulla esetén a cél megtalálásához (nulla költség) használhat egy algoritmust a bipartit gráfok maximális egyezésének megtalálására, például a Hopcroft-Karp algoritmust . Továbbá, ha legalább egy oszlopban nincs null elem, akkor a hozzárendelés nem lehetséges.

2. lépés

Gyakran az első lépésben nincs hozzárendelés, mint a következő esetben:

0	a2'	a3'	a4'
b1'	b2'	b3'	0
0	c2'	c3'	c4'
d1'	0	d3'	d4'

Az 1. feladatot hatékonyan (nulla költséggel) elvégezheti a és c dolgozó is, de a 3. feladatot senki sem tudja hatékonyan elvégezni.

Ilyen esetekben megismételjük az 1. lépést az oszlopoknál, és újra ellenőrizzük, hogy lehetséges-e a hozzárendelés.

3. lépés

Sok esetben a 2. lépés után érjük el a kívánt eredményt. De néha nem ez a helyzet, például:

0	a2'	a3'	a4'
b1'	b2'	b3'	0
0	c2'	c3'	c4'
d1'	0	0	d4'

Ha d dolgozó a 2. feladatot végzi, akkor nincs senki, aki elvégezze a 3. feladatot, és fordítva.

Ilyen esetekben az alábbiakban leírt eljárást követjük.

Először is, bármilyen algoritmus segítségével megtaláljuk a maximális egyezést egy bipartit gráfban, a lehető legtöbb munkát hozzárendeljük azoknak a dolgozóknak, akik nulla költséggel tudják elvégezni azokat. A táblázatban egy példa látható, a hozzárendelt munkák pirossal vannak kiemelve.

0	a2'	a3'	a4'
b1'	b2'	b3'	0
0	c2'	c3'	c4'
d1'	0	0	d4'

Jegyezze fel az összes hozzárendelés nélküli sort (1. sor). Jegyezze fel az összes nullát tartalmazó oszlopot ezekben a sorokban (1. oszlop). Jegyezze fel az összes „piros” nullát tartalmazó sort ezekben az oszlopokban (3. sor). Addig folytatjuk, amíg az új sorok és oszlopok meg nem jelennek.

×
0	a2'	a3'	a4'	×
b1'	b2'	b3'	0
0	c2'	c3'	c4'	×
d1'	0	0	d4'

Most vonalakat húzunk az összes megjelölt oszlopon és jelöletlen soron.

×
0	a2'	a3'	a4'	×
b1'	b2'	b3'	0
0	c2'	c3'	c4'	×
d1'	0	0	d4'

Mindezek a műveletek csak egy célt követtek: a lehető legkevesebb vonalat (függőleges és vízszintes) rajzolni, hogy az összes nullát lefedje. Használhat bármilyen más módszert a leírtak helyett.

4. lépés

A vonalakkal nem lefedett mátrixelemek közül (jelen esetben ezek a2', a3', a4', c2', c3', c4') keresse meg a legkisebbet. Vonja ki az összes jelöletlen sorból, és adja hozzá a megjelölt sorok és oszlopok összes metszéspontjához. Így például ha a felsoroltak legkisebb eleme a2', akkor azt kapjuk

×
0	0	a3'-a2'	a4'-a2'	×
b1'+a2'	b2'	b3'	0
0	c2'-a2'	c3'-a2'	c4'-а2'	×
d1'+a2'	0	0	d4'

Ismételje meg az eljárást (1-4. lépés), amíg a találkozó lehetséges.

Bibliográfia

R.E. Burkard, M. Dell'Amico, S. Martello: Hozzárendelési problémák . SIAM, Philadelphia (PA.) 2009. ISBN 978-0-89871-663-4
Harold W. Kuhn, "The Hungarian Method for the assignment problem", Naval Research Logistics Quarterly , 2 :83-97, 1955. Kuhn eredeti publikációja.
Harold W. Kuhn, "Variants of the Hungarian method for assignment problems", Naval Research Logistics Quarterly , 3 , 253-258, 1956.
J. Munkres, "Algoritms for the Assignment and Transportation Problems", Journal of the Society for Industrial and Applied Mathematics , 5 (1):32-38, 1957. március.
M. Fischetti, Lezioni di Ricerca Operativa, Edizioni Libreria Progetto Padova, Italia, 1995.
R. Ahuja, T. Magnanti, J. Orlin, Network Flows, Prentice Hall, 1993.

Jegyzetek

↑ Jacobi C. De investigando ordine systematis aequationum differentialum vulgarium cujuscunque, CGJ Jacobi's gesammelte Werke, fünfter Band, herausgegeben von K. Weierstrass. - 1890.
↑ (nem elérhető link) politechnique.fr Archiválva : 2020. január 29. a Wayback Machine -nél
↑ Archivált másolat (a hivatkozás nem elérhető) . Letöltve: 2010. február 11. Az eredetiből archiválva : 2011. július 19.. (határozatlan)