Unkarilainen algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 4.3.2020 tarkistetusta versiosta . tarkastukset vaativat 6 muokkausta .

Unkarilainen algoritmi on optimointialgoritmi , joka ratkaisee osoitusongelman polynomiajassa (katso operaatiotutkimus ). Sen kehitti ja julkaisi Harold Kuhn vuonna 1955 . Kirjoittaja antoi sille nimen "Unkarilainen menetelmä" johtuen siitä, että algoritmi perustuu suurelta osin kahden unkarilaisen matemaatikon König ja Egerváry

James Mancres havaitsi vuonna 1957, että algoritmi on (tiukka) polynomi. Siitä lähtien algoritmi on tunnettu myös Kuhn-Mankres- algoritmina tai Mankres-algoritmina osoitusongelman ratkaisemiseksi . Alkuperäisen algoritmin aikamonimutkaisuus oli, mutta Edmonds Karp samoin osoittivat, että sitä voitiin muokata käyntiajan saavuttamiseksi. Modifioitua unkarilaista algoritmia kutsutaan Hopcroft-Karp-algoritmiksi. Ford ja Fulkerson laajensivat menetelmän yleisiin kuljetusongelmiin. Vuonna 2006 havaittiin, että Jacobi oli löytänyt 1800-luvun ratkaisun toimeksiantoongelmaan, joka julkaistiin latinaksi vuoden 1890 postuumikokoelmassa. [1] [2] $O(n^{4})$ $O(n^{3})$

Esimerkki

Oletetaan, että työntekijöitä on kolme: Ivan, Peter ja Andrey. On tarpeen jakaa heidän kesken kolmen tyyppisen työn suorittaminen (jota kutsumme A, B, C), jokaisen työntekijän on suoritettava vain yhden tyyppinen työ. Miten se tehdään niin, että työntekijöiden palkkoihin kuluu mahdollisimman vähän rahaa? Ensin sinun on rakennettava kustannusmatriisi .

	A	B	C
Ivan	10 000 ruplaa.	20 000 ruplaa.	30 000 ruplaa.
Peter	30 000 ruplaa.	30 000 ruplaa.	30 000 ruplaa.
Andrew	30 000 ruplaa.	30 000 ruplaa.	20 000 ruplaa.

Yllä olevaan taulukkoon sovellettu unkarilainen algoritmi antaa meille vaaditun jakauman: Ivan tekee työn A, Peter tekee työn B, Andrey tekee työn C.

Ongelman selvitys

Annettu ei-negatiivinen n × n -matriisi , jossa i : nnen rivin ja j :nnen sarakkeen elementti vastaa kustannuksia, jotka aiheutuvat i : nnen työntekijän suorittamasta j - tyypin työstä . On tarpeen löytää tällainen työn vastaavuus työntekijöille, jotta työvoimakustannukset ovat alhaisimmat. Jos tavoitteena on löytää kohde, jolla on korkeimmat kustannukset, niin ratkaisu pelkistyy juuri muotoillun ongelman ratkaisemiseen korvaamalla kukin kustannus C maksimikustannusten ja C :n välisellä erolla . [3]

Tärkeimmät ideat

Algoritmi perustuu kahteen ajatukseen:

jos sama luku vähennetään tietyn rivin tai sarakkeen kaikista elementeistä , kokonaiskustannukset pienenevät ja optimaalinen ratkaisu ei muutu; $y$ $y$
jos on nollakustannusratkaisu, se on optimaalinen.

Algoritmi etsii arvoja vähennettäviksi jokaisen rivin ja jokaisen sarakkeen kaikista elementeistä (eri riveillä ja sarakkeilla eri tavalla), niin että kaikki matriisin elementit pysyvät ei-negatiivisina, mutta näkyviin tulee nollaratkaisu.

Määritelmät

Algoritmia on helpompi kuvata, jos ongelma muotoillaan käyttämällä kaksiosaista graafia . Annettu täydellinen kaksiosainen graafi G=(S, T; E) , jossa n pistettä vastaa työntekijöitä ( S ) ja n pistettä vastaa työtyyppejä ( T ); kunkin reunan c(i, j) hinta ei ole negatiivinen. On löydettävä täydellinen tai täydellinen yhteensopivuus halvimmalla hinnalla.

Kutsumme funktiopotentiaalia , jos jokaiselle . Potentiaaliarvo määritellään . On helppo nähdä, että täydellisen yhteensovittamisen hinta ei ole pienempi kuin minkään potentiaalin arvo. Unkarilainen menetelmä löytää täydellisen vastaavuuden ja potentiaalin samalla kustannus/arvolla, mikä osoittaa, että molemmat suureet ovat optimaalisia. Itse asiassa hän löytää täydellisen yhteensopivuuden jäykkien reunojen kanssa: reunan sanotaan olevan jäykkä mahdolliselle jos . Jäykkä reunaosakuvaaja merkitään nimellä . Täydellisen vastaavuuden hinta (jos sellainen on) on yhtä suuri kuin . $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$

Algoritmi kaksiosaisten graafien suhteen

Algoritmi tallentaa muistiin jokaisen jäykän reunan potentiaalin ja orientaation (suunnan asettamisen), jolla on se ominaisuus, että reunat suuntautuvat muodostamaan sovituksen, jota merkitsemme . Suunnattua graafia, joka koostuu jäykistä reunoista tietyllä suuntauksella, on merkitty . Siten joka hetki on olemassa kolmenlaisia reunoja: $y\$ $T\$ $S\$ $M$ $\mathbf {{\overrightarrow {G}}_{y}}$

ei-jäykkä (eikä kuulu ) $M\$
kova, mutta ei kuulu $M\$
kovaa ja omistettua $M\$

Aluksi kaikkialla on 0, ja kaikki reunat on suunnattu kohteesta kohteeseen (siis tyhjä). Jokaisessa vaiheessa joko muutetaan niin, että seuraavassa kappaleessa määriteltyä kärkijoukkoa lisätään, tai suuntaa muutetaan, jotta saadaan sovitus suuremmalla määrällä reunoja; se on aina totta, että kaikki reunat ovat jäykkiä. Prosessi päättyy, jos se sopii täydellisesti. $y\$ $S\$ $T\$ $M\$ $y\$ $Z\$ $M\$ $M\$

Olkoon jokaisessa vaiheessa ja oltava joukko kärkipisteitä, jotka eivät ole satunnaisia reunoja osoitteesta (eli pisteiden joukko , jotka eivät sisällä mitään reunaa, vaan joukko kärkipisteitä kohteesta , josta ei reunaa tule ulos). Merkitään joukosta kärkijoukkoja, jotka ovat saavutettavissa välillä - (se löytyy leveyshaulla ). $R_{S}\subseteq S$ $R_{T}\subseteq T$ $M\$ $R_{S}\$ $S$ $R_{T}\$ $T$ $Z\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$

Jos ei ole tyhjä, se tarkoittaa, että on vähintään yksi polku osoitteesta osoitteeseen . Valitsemme minkä tahansa näistä poluista ja muutamme sen kaikkien reunojen suunnan päinvastaiseksi. Vastaavuuden koko kasvaa yhdellä. $R_{T}\cap Z$ $\mathbf {{\overrightarrow {G}}_{y}}$ $R_{S}\$ $R_{T}\$

Todisteeksi huomautamme kaksi ilmeistä tosiasiaa:

Valitulla polulla reunat välillä - vuorottelevat reunojen välillä - . Tämä seuraa kaksiosaisesta graafista. $S\$ $T\$ $T\$ $S\$
Polun ensimmäinen kärki kuuluu , ja viimeinen piste kuuluu . Siksi sen ensimmäinen ja viimeinen reuna on suunnattu kohteesta kohteeseen . $S\$ $T\$ $S\$ $T\$

Määritelmän mukaan tästä seuraa, että valitulla polulla kuuluvat ja kuulumattomat reunat vuorottelevat, ja ensimmäinen ja viimeinen reuna eivät kuulu , eli polku on nousussa, josta todistettava väite seuraa. $\mathbf {{\overrightarrow {G}}_{y}}$ $M\$ $M\$

Jos tyhjä, laita . on positiivinen, koska ja välillä ei ole kovia reunoja . $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$

Todellakin, olkoon sellainen reuna (i, j) olemassa. Koska , mutta , kärkipiste on saavutettavissa kohteesta - , mutta kärki ei ole tavoitettavissa. $i\ in Z$ $j\notin Z$ $minä\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$ $j\$

Siksi se ei voi sisältää reunoja (i, j). Siksi mistä . Koska se on saavutettavissa osoitteesta , on polku johonkin osoitteeseen kuuluvasta kärjestä . Harkitse tämän polun viimeistä reunaa. Merkitse se (k, i). Koska se on tavoitettavissa välillä - , mutta tavoittamaton, . Koska , . Siksi on sattunut kahteen reunaan : ja , mikä on mahdotonta, koska on täsmäys. Ristiriita. $\mathbf {{\overrightarrow {G}}_{y}}$ $(i,j)\in M$ $en ole R_{S}$ $minä\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$ $minä\$ $R_{S}\$ $k\$ $R_{S}\$ $\mathbf {{\overrightarrow {G}}_{y}}$ $j\$ $k\neq j$ $(k,i)\in \mathbf {{\overrightarrow {G}}_{y}}$ $(i,k)\in M$ $minä\$ $M\$ $(i,j)\$ $(i,k)\$ $M\$

Olkaamme lisätä on vertics alkaen ja vähentää klo vertics mukana . Uusi on edelleen potentiaalinen. $y\$ $\Delta$ $Z\cap S$ $y\$ $\Delta$ $Z\cap T$ $y\$

Todellakin, mille tahansa reunalle (i, j), , : $i\in S$ $j\in T$

jos , , niin c(i, j)-y(i)-y(j) ei muutu, koska ei y(i) eikä y(j) $en ole Z$ $j\notin Z$
jos , , niin c(i, j)-y(i)-y(j) ei muutu, koska y(i) kasvaa , ja y(j) pienenee saman verran $i\ in Z$ $j\in Z$ $\Delta$
jos , ero c(i, j)-y(i)-y(j) kasvaa , pysyy ei-negatiivisena $en ole Z$ $j\in Z$ $\Delta$
jos , erotus c(i, j)-y(i)-y(j) pienenee , mutta pysyy silti ei-negatiivisena, koska on pienin sellaisista eroista. $i\ in Z$ $j\notin Z$ $\Delta$ $\Delta$

Kaavio muuttuu, mutta sisältää tästä huolimatta . $\mathbf {{\overrightarrow {G}}_{y}}$ $M\$

Todellakin, jotta jostain reunasta (i, j), , , jätetään pois, on tarpeen tehdä siitä ei-jäykkä, eli lisätä eroa c(i, j)-y(i)-y(j) . Kuten olemme nähneet, ero kasvaa vain, jos , , toisin sanoen, on saavuttamaton kohteesta , mutta on saavutettavissa. Mutta tässä tapauksessa reuna (j, i) ei voi kuulua ryhmään , joten reuna ei kuulu joukkoon . $\mathbf {{\overrightarrow {G}}_{y}}$ $i\in S$ $j\in T$ $en ole Z$ $j\in Z$ $i$ $R_{S}$ $j$ $\mathbf {{\overrightarrow {G}}_{y}}$ $M$

Suuntaa uudet reunat kohdasta . Määritelmän mukaan pisteistä tavoitettavissa olevien kärkien joukko kasvaa (eikä jäykkien reunojen määrä välttämättä kasva). $S\$ $T\$ $\Delta$ $Z\$ $R_{S}$

Tämän väitteen todistamiseksi todistamme ensin, että mikään huippupiste ei katoa Z:sta. Olkoon . Sitten on polku jostakin V:stä V:hen kuuluvasta kärjestä. Kaikki tämän polun kärjet ovat saavutettavissa osoitteesta , eli ne kuuluvat Z:hen. Jokainen tämän polun reuna osuu kahteen kärkeen Z:stä. Kuten edellä näimme, tällaisilla reunoilla ero c(i, j )-y(i)-y(j) ei muutu. Tämä tarkoittaa, että kaikki polun reunat pysyvät jäykinä ja V on edelleen saavutettavissa osoitteesta . Todistetaan nyt, että vähintään yksi kärkipiste lisätään Z:hen. Tarkastellaan reunaa, jolla minimi saavutetaan . Tälle reunalle ero c(i, j)-y(i)-y(j) on nolla, joten siitä tulee jäykkä ja se suuntautuu S:stä T:hen, eli i:stä j:ään. Koska , j tulee myös tavoitettavissa kohteesta , eli se lisätään Z:hen. $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}$

Toistamme nämä vaiheet, kunnes siitä tulee täydellinen yhteensopivuus; tässä tapauksessa se antaa toimeksiannon halvimmalla hinnalla. Tämän algoritmiversion suoritusaika on : se täytetään kerran, ja siinä vaiheessa, kun se ei muutu, potentiaalisia muutoksia ei voi enää olla (koska se kasvaa joka kerta). Potentiaalin muuttamiseen tarvittava aika on . $M\$ $O(n^{4})$ $M\$ $n\$ $M\$ $n\$ $Z\$ $O(n^{2})$

Matriisitulkinta

Työntekijöille ja töille annetaan n × n -matriisi , joka määrittää kunkin työn kustannukset kullekin työntekijälle. Etsi minimikustannus työn tekemisestä siten, että jokainen työntekijä tekee täsmälleen yhden työn ja jokaisen työn tekee täsmälleen yksi työntekijä. $n$

Seuraavassa toimeksiannolla ymmärrämme työntekijöiden ja töiden välisen vastaavuuden, jonka kustannukset ovat nolla, kun olemme tehneet muutoksia, jotka vaikuttavat vain työpaikkojen kokonaiskustannuksiin.

Ensinnäkin kirjoitetaan ongelma matriisimuodossa:

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

jossa a, b, c, d ovat työntekijöitä, joiden on suoritettava työt 1, 2, 3, 4. Kertoimet a1, a2, a3, a4 ilmaisevat kustannuksia, jotka aiheutuvat töiden 1, 2, 3, 4 suorittamisesta työntekijälle "a", vastaavasti. Muilla symboleilla on samanlainen merkitys. Matriisi on neliön muotoinen, joten jokainen työntekijä voi tehdä vain yhden työn.

Vaihe 1

Vähennämme elementtejä rivi riviltä. Etsitään ensimmäisen rivin alkioista pienin (a1, a2, a3, a4) ja vähennetään se kaikista ensimmäisen rivin elementeistä. Tässä tapauksessa ainakin yksi ensimmäisen rivin elementeistä asetetaan nollaan. Teemme samoin kaikille muille linjoille. Nyt jokaisella matriisin rivillä on vähintään yksi nolla. Joskus nollat jo riittävät määränpään löytämiseen. Esimerkki on esitetty taulukossa. Punaiset nollat osoittavat määrättyjä töitä.

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

Suurella määrällä nollia voit löytää määränpään (nollahinta) käyttämällä algoritmia, joka etsii kaksiosaisten kaavioiden maksimivastineisuutta, esimerkiksi Hopcroft-Karp-algoritmia . Lisäksi, jos ainakin yhdessä sarakkeessa ei ole nollaelementtejä, osoitus ei ole mahdollista.

Vaihe 2

Usein ensimmäisessä vaiheessa ei ole tehtävää, kuten seuraavassa tapauksessa:

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

Tehtävän 1 voivat tehdä tehokkaasti (nollakustannuksin) sekä työntekijä a että työntekijä c, mutta tehtävää 3 ei kukaan voi tehdä tehokkaasti.

Tällaisissa tapauksissa toistamme sarakkeille vaiheen 1 ja tarkistamme uudelleen, onko määritys mahdollista.

Vaihe 3

Monissa tapauksissa saavutamme halutun tuloksen vaiheen 2 jälkeen. Joskus näin ei kuitenkaan ole, esimerkiksi:

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

Jos työntekijä d tekee työtä 2, ei ole ketään tehtävää 3 ja päinvastoin.

Tällaisissa tapauksissa noudatamme alla kuvattua menettelyä.

Ensinnäkin, käyttämällä mitä tahansa algoritmia maksimivastaavuuden löytämiseksi kaksiosaisesta graafista, annamme mahdollisimman monta työtä niille työntekijöille, jotka voivat suorittaa ne nollakustannuksilla. Taulukossa on esimerkki, määrätyt työt on korostettu punaisella.

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

Merkitse muistiin kaikki rivit ilman tehtäviä (rivi 1). Huomaa kaikki näillä riveillä olevat sarakkeet, joissa on nolla (sarake 1). Huomaa kaikki rivit, joissa on "punaisia" nollia näissä sarakkeissa (rivi 3). Jatkamme, kunnes uusia rivejä ja sarakkeita ei enää merkitä.

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

Nyt piirrämme viivoja kaikkien merkittyjen sarakkeiden ja merkitsemättömien rivien läpi.

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

Kaikilla näillä toimilla oli vain yksi tavoite: piirtää mahdollisimman vähän viivoja (pystysuorat ja vaakasuuntaiset) niin, että ne peittävät kaikki nollat. Voit käyttää mitä tahansa muuta menetelmää kuvatun sijaan.

Vaihe 4

Etsi matriisielementeistä, joita viivat eivät kata (tässä tapauksessa a2', a3', a4', c2', c3', c4'), pienin. Vähennä se kaikista merkitsemättömistä riveistä ja lisää se kaikkiin merkittyjen rivien ja sarakkeiden leikkauspisteisiin. Joten esimerkiksi jos listan pienin elementti on a2', saamme

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

Toista toimenpide (vaiheet 1-4), kunnes tapaaminen on mahdollista.

Bibliografia

R.E. Burkard, M. Dell'Amico, S. Martello: Tehtäväongelmat . 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. Kuhnin alkuperäinen julkaisu.
Harold W. Kuhn, "Unkarilaisen menetelmän vaihtoehdot osoitusongelmiin", 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 maaliskuu.
M. Fischetti, Lezioni di Ricerca Operativa, Edizioni Libreria Progetto Padova, Italia, 1995.
R. Ahuja, T. Magnanti, J. Orlin, Network Flows, Prentice Hall, 1993.

Muistiinpanot

↑ Jacobi C. De investigando ordine systematis aequationum differentialum vulgarium cujuscunque, CGJ Jacobi's gesammelte Werke, fünfter Band, herausgegeben von K. Weierstrass. - 1890.
↑ (linkki ei saatavilla) politechnique.fr Arkistoitu 29. tammikuuta 2020 Wayback Machinessa
↑ Arkistoitu kopio (linkki ei saatavilla) . Haettu 11. helmikuuta 2010. Arkistoitu alkuperäisestä 19. heinäkuuta 2011. (määrätön)