Хуваарилалтын бодлогыг бодох Унгарын алгоритм¶

Хуваарилалтын бодлогын томьёолол¶

Хуваарилалтын бодлогын хэд хэдэн стандарт томьёолол байдаг (тэдгээр нь бүгд үндсэндээ эквивалент). Тэдгээрийн зарим нь энд байна:

$n$ ажил ба $n$ ажилтан байна. Ажилтан бүр тодорхой ажлын хувьд хүлээж буй мөнгөний хэмжээгээ заана. Ажилтан бүрийг зөвхөн нэг ажилд хуваарилж болно. Зорилго нь нийт өртгийг хамгийн бага болгохоор ажлуудыг ажилтнуудад хуваарилах явдал юм.
$n \times n$ матриц $A$ өгөгдсөн бол багана бүрээс яг нэг тоо сонгогдох ба сонгосон тоонуудын нийлбэр хамгийн бага байхаар мөр бүрээс нэг тоо сонгох даалгавар юм.
$n \times n$ матриц $A$ өгөгдсөн бол $\sum A[i]\left[p[i]\right]$ утга хамгийн бага байх $n$ урттай сэлгэмэл $p$-г олох даалгавар юм.
Хэсэг бүрд $n$ оройтой, ирмэг бүрд жин оноогдсон бүрэн хоёр хэсэгт графыг авч үзье. Зорилго нь нийт жин нь хамгийн бага байх төгс тааруулалтыг олох явдал юм.

Дээрх бүх хувилбар нь "квадрат" бодлого, өөрөөр хэлбэл хоёр хэмжээс нь үргэлж $n$-тэй тэнцүү байдгийг тэмдэглэх нь чухал. Практикт $n$ нь $m$-тэй тэнцүү биш байх, $\min(n,m)$ элемент сонгох даалгавартай ижил төстэй "тэгш өнцөгт" томьёолол олонтаа тохиолддог. Гэвч "тэгш өнцөгт" бодлогыг тэг эсвэл хязгааргүй утгатай мөр эсвэл багана нэмэх замаар үргэлж "квадрат" бодлого болгон хувиргаж болохыг ажиглаж болно.

Мөн хамгийн бага шийд хайхтай адилаар хамгийн их шийд олох бодлогыг ч тавьж болохыг тэмдэглэе. Гэвч эдгээр хоёр бодлого хоорондоо эквивалент: бүх жинг $-1$-ээр үржүүлэхэд хангалттай.

Унгарын алгоритм¶

Түүхэн лавлагаа¶

Алгоритмыг Харолд Кун 1955 онд боловсруулж нийтэлсэн. Кун өөрөө үүнийг Унгар математикч Денеш Кёниг, Енё Эгервари нарын өмнөх ажил дээр суурилсан тул "Унгарын" гэсэн нэр өгсөн.
1957 онд Жеймс Мункрес энэ алгоритм өртгөөс үл хамааран (чанд утгаараа) олон гишүүнт хугацаанд ажилладгийг харуулсан.
Тиймээс уран зохиолд энэ алгоритмыг зөвхөн "Унгарын" төдийгүй "Кун-Мункресийн алгоритм" эсвэл "Мункресийн алгоритм" гэж бас мэддэг.
Гэвч 2006 онд Герман математикч Карл Густав Якоби ижил алгоритмыг Кунаас зуун жилийн өмнө зохиосныг саяхан илрүүлсэн. Түүний 1890 онд нас барсны дараа нийтлэгдсэн Дурын энгийн дифференциал тэгшитгэлийн системийн эрэмбийг судлах тухай бүтээлд бусад олдворуудын дунд хуваарилалтын бодлогыг бодох олон гишүүнт алгоритм агуулагдаж байсан. Харамсалтай нь нийтлэл Латин хэл дээр байсан тул математикчдын дунд анзаарагдалгүй өнгөрсөн.

Мөн Куны анхны алгоритм $\mathcal{O}(n^4)$ асимптот complexity-тэй байсан бөгөөд зөвхөн хожим Жак Эдмондс, Ричард Карп нар (мөн тэднээс бие даан Томизава) үүнийг $\mathcal{O}(n^3)$ асимптот complexity болгон хэрхэн сайжруулахыг харуулсныг тэмдэглэх нь зүйтэй.

$\mathcal{O}(n^4)$ алгоритм¶

Ойлгомжгүй байдлаас зайлсхийхийн тулд бид голчлон матрицын томьёолол дахь хуваарилалтын бодлогыг авч үзэж байгааг шууд тэмдэглэе (өөрөөр хэлбэл матриц $A$ өгөгдсөн бол түүнээс өөр өөр мөр, баганад байрлах $n$ нүд сонгох хэрэгтэй). Бид массивыг $1$-ээс эхлэн индексжүүлнэ, өөрөөр хэлбэл жишээ нь матриц $A$ нь $A[1 \dots n][1 \dots n]$ индекстэй.

Мөн бид матриц A дахь бүх тоог сөрөг биш гэж үзнэ (хэрэв тийм биш бол та бүх тоонд ямар нэг тогтмолыг нэмэх замаар матрицыг үргэлж сөрөг биш болгож болно).

Дараах нөхцөлийг хангах дурын хоёр тооны массив $u[1 \ldots n]$ ба $v[1 \ldots n]$-г потенциал гэж нэрлэе:

$$u[i]+v[j]\leq A[i][j],\quad i=1\dots n,\ j=1\dots n$$

(Таны харж байгаагаар $u[i]$ нь матрицын $i$ дахь мөрд, $v[j]$ нь $j$ дахь баганад харгалзана).

Потенциалын элементүүдийн нийлбэрийг потенциалын утга $f$ гэж нэрлэе:

$$f=\sum_{i=1}^{n} u[i] + \sum_{j=1}^{n} v[j].$$

Нэг талаас хайж буй шийд $sol$-ийн өртөг дурын потенциалын утгаас бага биш болохыг харахад амархан.

Лемм. $sol\geq f.$

Баталгаа

Бодлогын хайж буй шийд матриц $A$-ийн $n$ нүднээс тогтох тул тэдгээрийн тус бүрийн хувьд $u[i]+v[j]\leq A[i][j]$ байна. $sol$ дахь бүх элемент өөр өөр мөр, баганад байгаа тул сонгосон бүх $A[i][j]$-ээр эдгээр тэнцэтгэл бишийг нийлбэрлэвэл тэнцэтгэл бишийн зүүн талд $f$, баруун талд $sol$ гарна.

Нөгөө талаас энэ тэнцэтгэл бишийг тэнцэтгэл болгон хувиргадаг шийд ба потенциал үргэлж байдаг нь тогтоогддог. Доор тайлбарласан Унгарын алгоритм энэ баримтын конструктив баталгаа болно. Одоохондоо хэрэв ямар нэг шийдийн өртөг ямар нэг потенциалтай тэнцүү бол энэ шийд оновчтой гэдэг баримтад л анхаарлаа хандуулъя.

Ямар нэг потенциалыг тогтооё. Хэрэв $u[i]+v[j]=A[i][j]$ бол ирмэг $(i,j)$-г хатуу гэж нэрлэе.

Хоёр хэсэгт граф ашигласан хуваарилалтын бодлогын өөр нэг томьёололыг сана. Зөвхөн хатуу ирмэгүүдээс тогтох хоёр хэсэгт графыг $H$ гэж тэмдэглэе. Унгарын алгоритм одоогийн потенциалын хувьд граф $H$-ийн хамгийн олон ирмэгтэй тааруулалт $M$-г хөтөлнө. $M$ нь $n$ ирмэг агуулмагц бодлогын шийд нь яг $M$ болно (эцсийн эцэст энэ нь өртөг нь потенциалын утгатай давхцах шийд байх болно).

Алгоритмын тайлбар руу шууд орцгооё.

Алхам 1. Эхэндээ потенциалыг тэг ($i$ бүрийн хувьд $u[i]=v[i]=0$), тааруулалт $M$-г хоосон гэж үзнэ.

Алхам 2. Цаашид алгоритмын алхам бүрд бид потенциалыг өөрчлөхгүйгээр одоогийн тааруулалт $M$-ийн хүчин чадлыг нэгээр нэмэгдүүлэхийг оролдоно (тааруулалтыг хатуу ирмэгүүдийн граф $H$-д хайдгийг сана). Үүний тулд ердийн Хоёр хэсэгт граф дахь хамгийн их тааруулалт олох Куны алгоритм-ыг ашиглана. Алгоритмыг энд эргэн саная. Тааруулалт $M$-ийн бүх ирмэгийг баруун хэсгээс зүүн хэсэг рүү чиглүүлэх ба граф $H$-ийн бусад бүх ирмэгийг эсрэг чиглэлд чиглүүлнэ.

(Тааруулалт хайх нэр томьёоноос) одоогийн тааруулалтын ирмэг оройтой зэргэлдээ байвал тэр оройг ханасан гэж нэрлэдгийг сана. Одоогийн тааруулалтын ямар ч ирмэгтэй зэргэлдээ биш оройг ханаагүй гэж нэрлэнэ. Эхний ирмэг нь тааруулалтад харьяалагдахгүй, дараагийн бүх ирмэгийн хувьд тааруулалтад харьяалагдах нь ээлжилдэг (харьяалагдана/харьяалагдахгүй) сондгой урттай замыг нэмэгдүүлэх зам гэж нэрлэдэг. Зүүн хэсгийн бүх ханаагүй оройноос гүнзгийрүүлэх эсвэл өргөнөөр эхлэх тойролт эхэлнэ. Хэрэв хайлтын үр дүнд баруун хэсгийн ханаагүй орой хүрэх боломжтой байсан бол бид зүүн хэсгээс баруун хэсэг рүү нэмэгдүүлэх зам оллоо гэсэн үг. Хэрэв бид замын сондгой ирмэгүүдийг тааруулалтад оруулж, тэгш ирмэгүүдийг хасвал (өөрөөр хэлбэл эхний ирмэгийг тааруулалтад оруулж, хоёр дахийг хасаж, гурав дахийг оруулах гэх мэт) бид тааруулалтын хүчин чадлыг нэгээр нэмэгдүүлнэ.

Хэрэв нэмэгдүүлэх зам байгаагүй бол одоогийн тааруулалт $M$ нь граф $H$-д максимал байна.

Алхам 3. Хэрэв одоогийн алхамд одоогийн тааруулалтын хүчин чадлыг нэмэгдүүлэх боломжгүй бол дараагийн алхмуудад тааруулалтыг нэмэгдүүлэх илүү олон боломж гарахаар потенциалыг дахин тооцоолно.

Куны алгоритмын сүүлийн тойролтын явцад зочилсон зүүн хэсгийн оройнуудын олонлогийг $Z_1$, баруун хэсгийн зочилсон оройнуудын олонлогийг $Z_2$ гэж тэмдэглэе.

$\Delta$ утгыг тооцоолъё:

$$\Delta = \min_{i\in Z_1,\ j\notin Z_2} A[i][j]-u[i]-v[j].$$

Лемм. $\Delta > 0.$

Баталгаа

$\Delta=0$ гэж үзье. Тэгвэл $i\in Z_1$ ба $j\notin Z_2$ байх хатуу ирмэг $(i,j)$ оршино. Эндээс ирмэг $(i,j)$ баруун хэсгээс зүүн хэсэг рүү чиглэсэн байх ёстой, өөрөөр хэлбэл $(i,j)$ тааруулалт $M$-д орсон байх ёстой нь мөрдөнө. Гэвч энэ нь боломжгүй, учир нь бид j-ээс i рүү ирмэгийн дагуу явахаас өөрөөр ханасан орой $i$ хүрч чадахгүй байсан. Тиймээс $\Delta > 0$.

Одоо потенциалыг дахин тооцоолъё:

бүх орой $i\in Z_1$-ийн хувьд $u[i] \gets u[i]+\Delta$ хий,
бүх орой $j\in Z_2$-ийн хувьд $v[j] \gets v[j]-\Delta$ хий.

Лемм. Үүссэн потенциал зөв потенциал хэвээр байна.

Баталгаа

Дахин тооцооллын дараа бүх $i,j$-ийн хувьд $u[i]+v[j]\leq A[i][j]$ болохыг бид харуулна. $i\in Z_1$ ба $j\in Z_2$ байх $A$-ийн бүх элементийн хувьд $u[i]+v[j]$ нийлбэр өөрчлөгдөхгүй тул тэнцэтгэл биш үнэн хэвээр байна. $i\notin Z_1$ ба $j\in Z_2$ байх бүх элементийн хувьд $u[i]+v[j]$ нийлбэр $\Delta$-аар багасах тул тэнцэтгэл биш үнэн хэвээр байна. $i\in Z_1$ ба $j\notin Z_2$ байх бусад элементийн хувьд нийлбэр нэмэгдэх боловч тэнцэтгэл биш хадгалагдсан хэвээр байна, учир нь $\Delta$ утга нь тодорхойлолтоороо тэнцэтгэл бишийг өөрчлөхгүй байх хамгийн их өсөлт юм.

Лемм. Хатуу ирмэгүүдийн хуучин тааруулалт $M$ зөв хэвээр байна, өөрөөр хэлбэл тааруулалтын бүх ирмэг хатуу хэвээр үлдэнэ.

Баталгаа

Потенциал өөрчлөгдсөний улмаас ямар нэг хатуу ирмэг $(i,j)$ хатуу байхаа болихын тулд $u[i] + v[j] = A[i][j]$ тэнцэтгэл нь $u[i] + v[j] < A[i][j]$ тэнцэтгэл биш болж хувирах шаардлагатай. Гэвч энэ нь зөвхөн $i \notin Z_1$ ба $j \in Z_2$ үед л тохиолдож болно. Гэвч $i \notin Z_1$ гэдэг нь ирмэг $(i,j)$ тааруулалтын ирмэг байж чадахгүй байсныг илэрхийлнэ.

Лемм. Потенциалыг дахин тооцоолох бүрд тойролтоор хүрч болох оройн тоо буюу $|Z_1|+|Z_2|$ чанд утгаараа нэмэгдэнэ.

Баталгаа

Эхлээд дахин тооцооллоос өмнө хүрч болох байсан дурын орой одоо ч хүрч болох хэвээр байгааг анзаар. Үнэндээ хэрэв ямар нэг орой хүрч болох бол зүүн хэсгийн ханаагүй оройноос эхлэн хүрч болох оройнуудаас түүн хүрэх ямар нэг зам байна; $(i,j),\ i\in Z_1,\ j\in Z_2$ хэлбэрийн ирмэгүүдийн хувьд $u[i]+v[j]$ нийлбэр өөрчлөгдөхгүй тул энэ бүхэл зам потенциалыг өөрчилсний дараа хадгалагдана. Хоёрдугаарт дахин тооцооллын дараа дор хаяж нэг шинэ орой хүрч болохыг бид харуулна. Энэ нь $\Delta$-ийн тодорхойлолтоос мөрдөнө: $\Delta$ хамаарч буй ирмэг $(i,j)$ хатуу болох тул орой $j$ нь орой $i$-ээс хүрч болно.

Сүүлийн леммээс болж нэмэгдүүлэх зам олдож, $M$-ийн тааруулалтын хүчин чадал нэмэгдэхээс өмнө $n$-ээс олонгүй удаа потенциалыг дахин тооцоолж болно. Ингэснээр эрт орой хэзээ нэгэн цагт төгс тааруулалт $M^*$-д харгалзах потенциал олдох ба $M^*$ нь бодлогын хариу болно. Алгоритмын complexity-ийн тухай ярих юм бол энэ нь $\mathcal{O}(n^4)$: нийтдээ тааруулалт хамгийн ихдээ $n$ удаа нэмэгдэх ёстой бөгөөд тэдгээрийн өмнө тус бүрд $n$-ээс олонгүй удаа потенциалыг дахин тооцоолох ба тэдгээрийн тус бүр $\mathcal{O}(n^2)$ хугацаанд гүйцэтгэгдэнэ.

Бид $\mathcal{O}(n^4)$ алгоритмын хэрэгжүүлэлтийг энд өгөхгүй, учир нь энэ нь доор тайлбарласан $\mathcal{O}(n^3)$-ын хэрэгжүүлэлтээс богино байхгүй нь тогтоогдох болно.

$\mathcal{O}(n^3)$ алгоритм¶

Одоо ижил алгоритмыг $\mathcal{O}(n^3)$-д (тэгш өнцөгт бодлогын хувьд $n \times m$, $\mathcal{O}(n^2m)$) хэрхэн хэрэгжүүлэхийг сурцгаая.

Гол санаа нь матрицын мөрүүдийг нэг нэгээр нь авч үзэх явдал бөгөөд бүгдийг нэгэн зэрэг биш. Ингэснээр дээр тайлбарласан алгоритм дараах хэлбэртэй болно:

Матриц $A$-ийн дараагийн мөрийг авч үз.
Энэ мөрөөс эхлэх нэмэгдүүлэх зам байхгүй л бол потенциалыг дахин тооцоол.
Нэмэгдүүлэх зам олдмогц түүний дагуу тааруулалтыг тарааж (ингэснээр сүүлийн ирмэгийг тааруулалтад оруулж), 1-р алхмаас дахин эхэл (дараагийн мөрийг авч үзэхийн тулд).

Шаардлагатай complexity-д хүрэхийн тулд матрицын мөр бүрд гүйцэтгэгддэг 2-3-р алхмыг $\mathcal{O}(n^2)$ хугацаанд (тэгш өнцөгт бодлогын хувьд $\mathcal{O}(nm)$-д) хэрэгжүүлэх шаардлагатай.

Үүний тулд дээр баталсан хоёр баримтыг сана:

Потенциал өөрчлөгдөхөд Куны тойролтоор хүрч болох байсан оройнууд хүрч болох хэвээр үлдэнэ.
Нийтдээ нэмэгдүүлэх зам олдохоос өмнө зөвхөн $\mathcal{O}(n)$ удаа потенциалыг дахин тооцоолж болно.

Эндээс шаардлагатай complexity-д хүрэх боломж олгодог дараах гол санаанууд мөрдөнө:

Нэмэгдүүлэх зам байгаа эсэхийг шалгахын тулд потенциалыг дахин тооцоолох бүрд Куны тойролтыг дахин эхлүүлэх шаардлагагүй. Үүний оронд та Куны тойролтыг давталттай хэлбэрээр хийж болно: потенциалыг дахин тооцоолох бүрийн дараа нэмэгдсэн хатуу ирмэгүүдийг харж, хэрэв тэдгээрийн зүүн үзүүр хүрч болох байсан бол баруун үзүүрийг нь ч бас хүрч болох гэж тэмдэглээд, тэдгээрээс тойролтыг үргэлжлүүл.
Энэ санааг цаашид хөгжүүлбэл бид алгоритмыг дараах байдлаар илэрхийлж болно: давталтын алхам бүрд потенциалыг дахин тооцоолно. Дараа нь хүрч болох болсон баганыг тодорхойлно (потенциалыг дахин тооцоолох бүрийн дараа хүрч болох шинэ орой гарч ирдэг тул энэ нь үргэлж байх болно). Хэрэв багана ханаагүй бол нэмэгдүүлэх гинж илэрнэ. Эсрэгээрээ хэрэв багана ханасан бол тааруулалтын мөр ч бас хүрч болох болно.
Потенциалыг хурдан дахин тооцоолохын тулд ($\mathcal{O}(n^2)$ гэнэн хувилбараас хурдан) та багана бүрийн хувьд туслах минимумыг хөтлөх хэрэгтэй:

$minv[j]=\min_{i\in Z_1} A[i][j]-u[i]-v[j].$

Хайж буй $\Delta$ утга тэдгээрээр дараах байдлаар илэрхийлэгддэгийг харахад амархан:

$\Delta=\min_{j\notin Z_2} minv[j].$

Ингэснээр $\Delta$-г олох ажлыг одоо $\mathcal{O}(n)$-д хийж болно.

Зочилсон шинэ мөр гарч ирэх үед массив $minv$-г шинэчлэх шаардлагатай. Үүнийг нэмэгдсэн мөрийн хувьд $\mathcal{O}(n)$-д хийж болно (энэ нь бүх мөрөөр нийлбэрлэвэл $\mathcal{O}(n^2)$ болно). Мөн потенциалыг дахин тооцоолох үед массив $minv$-г шинэчлэх шаардлагатай бөгөөд үүнийг ч мөн $\mathcal{O}(n)$ хугацаанд хийнэ ($minv$ нь зөвхөн хараахан хүрээгүй баганын хувьд өөрчлөгдөнө: тухайлбал $\Delta$-аар багасна).

Ингэснээр алгоритм дараах хэлбэртэй болно: гадаад давталтад бид матрицын мөрүүдийг нэг нэгээр нь авч үзнэ. Мөр бүрийг $\mathcal{O}(n^2)$ хугацаанд боловсруулна, учир нь зөвхөн $\mathcal{O}(n)$ удаа потенциалыг дахин тооцоолж болох ба (тус бүр нь $\mathcal{O}(n)$ хугацаанд) массив $minv$-г $\mathcal{O}(n^2)$ хугацаанд хөтөлнө; Куны алгоритм $\mathcal{O}(n^2)$ хугацаанд ажиллана (учир нь энэ нь тус бүрдээ шинэ баганад зочилдог $\mathcal{O}(n)$ итерацын хэлбэрээр илэрхийлэгддэг).

Үүссэн complexity нь $\mathcal{O}(n^3)$ буюу хэрэв бодлого тэгш өнцөгт бол $\mathcal{O}(n^2m)$ юм.

Implementation of the Hungarian algorithm¶

The implementation below was developed by Andrey Lopatin several years ago. It is distinguished by amazing conciseness: the entire algorithm consists of 30 lines of code.

The implementation finds a solution for the rectangular matrix $A[1\dots n][1\dots m]$, where $n\leq m$. The matrix is 1-based for convenience and code brevity: this implementation introduces a dummy zero row and zero column, which allows us to write many cycles in a general form, without additional checks.

Arrays $u[0 \ldots n]$ and $v[0 \ldots m]$ store potential. Initially, they are set to zero, which is consistent with a matrix of zero rows (Note that it is unimportant for this implementation whether or not the matrix $A$ contains negative numbers).

The array $p[0 \ldots m]$ contains a matching: for each column $j = 1 \ldots m$, it stores the number $p[j]$ of the selected row (or $0$ if nothing has been selected yet). For the convenience of implementation, $p[0]$ is assumed to be equal to the number of the current row.

The array $minv[1 \ldots m]$ contains, for each column $j$, the auxiliary minima necessary for a quick recalculation of the potential, as described above.

The array $way[1 \ldots m]$ contains information about where these minimums are reached so that we can later reconstruct the augmenting path. Note that, to reconstruct the path, it is sufficient to store only column values, since the row numbers can be taken from the matching (i.e., from the array $p$). Thus, $way[j]$, for each column $j$, contains the number of the previous column in the path (or $0$ if there is none).

The algorithm itself is an outer loop through the rows of the matrix, inside which the $i$-th row of the matrix is considered. The first do-while loop runs until a free column $j0$ is found. Each iteration of the loop marks visited a new column with the number $j0$ (calculated at the last iteration; and initially equal to zero - i.e. we start from a dummy column), as well as a new row $i0$ - adjacent to it in the matching (i.e. $p[j0]$; and initially when $j0=0$ the $i$-th row is taken). Due to the appearance of a new visited row $i0$, you need to recalculate the array $minv$ and $\Delta$ accordingly. If $\Delta$ is updated, then the column $j1$ becomes the minimum that has been reached (note that with such an implementation $\Delta$ could turn out to be equal to zero, which means that the potential cannot be changed at the current step: there is already a new reachable column). After that, the potential and the $minv$ array are recalculated. At the end of the "do-while" loop, we found an augmenting path ending in a column $j0$ that can be "unrolled" using the ancestor array $way$.

The constant INF is "infinity", i.e. some number, obviously greater than all possible numbers in the input matrix $A$.

vector<int> u (n+1), v (m+1), p (m+1), way (m+1);
for (int i=1; i<=n; ++i) {
    p[0] = i;
    int j0 = 0;
    vector<int> minv (m+1, INF);
    vector<bool> used (m+1, false);
    do {
        used[j0] = true;
        int i0 = p[j0],  delta = INF,  j1;
        for (int j=1; j<=m; ++j)
            if (!used[j]) {
                int cur = A[i0][j]-u[i0]-v[j];
                if (cur < minv[j])
                    minv[j] = cur,  way[j] = j0;
                if (minv[j] < delta)
                    delta = minv[j],  j1 = j;
            }
        for (int j=0; j<=m; ++j)
            if (used[j])
                u[p[j]] += delta,  v[j] -= delta;
            else
                minv[j] -= delta;
        j0 = j1;
    } while (p[j0] != 0);
    do {
        int j1 = way[j0];
        p[j0] = p[j1];
        j0 = j1;
    } while (j0);
}

To restore the answer in a more familiar form, i.e. finding for each row $i = 1 \ldots n$ the number $ans[i]$ of the column selected in it, can be done as follows:

vector<int> ans (n+1);
for (int j=1; j<=m; ++j)
    ans[p[j]] = j;

The cost of the matching can simply be taken as the potential of the zero column (taken with the opposite sign). Indeed, as you can see from the code, $-v[0]$ contains the sum of all the values of $\Delta$, i.e. total change in potential. Although several values of $u[i]$ and $v[j]$ could change at once, the total change in the potential is exactly equal to $\Delta$, since until there is an augmenting path, the number of reachable rows is exactly one more than the number of the reachable columns (only the current row $i$ does not have a "pair" in the form of a visited column):

int cost = -v[0];

Дараалсан хамгийн богино замын алгоритмтай холбоо¶

Унгарын алгоритмыг хуваарилалтын бодлогод тохируулсан Дараалсан хамгийн богино замын алгоритм гэж үзэж болно. Дэлгэрэнгүй рүү орохгүйгээр тэдгээрийн хоорондох холбооны талаар зөн совинг өгье.

Дараалсан замын алгоритм Жонсоны алгоритмын өөрчилсөн хувилбарыг жинг дахин тогтоох арга техник болгон ашигладаг. Энэ нь дөрвөн алхамд хуваагдана:

Цорго $s$-ээс эхлэн Беллман-Форд алгоритмыг ашиглаж, зангилаа бүрийн хувьд $s$-ээс $v$ хүрэх замын хамгийн бага жин $h(v)$-г ол.

Үндсэн алгоритмын алхам бүрд:

Анхны графын ирмэгүүдийн жинг дараах байдлаар дахин тогтоо: $w(u,v) \gets w(u,v)+h(u)-h(v)$.
Анхны сүлжээний хамгийн богино замуудын дэд графыг олохын тулд Дейкстра-гийн алгоритмыг ашигла.
Дараагийн итерацын хувьд потенциалыг шинэчил.

Энэ тайлбарыг харгалзвал $h(v)$ ба потенциалын хооронд хүчтэй аналоги байгааг бид ажиглаж болно: тэдгээр нь тогтмол шилжилтийн хэмжээгээр ялгаатайгаар тэнцүү болохыг шалгаж болно. Түүнчлэн жинг дахин тогтоосны дараа тэг жинтэй бүх ирмэгийн олонлог нь үндсэн алгоритм урсгалыг нэмэгдүүлэхийг оролддог хамгийн богино замын дэд графыг илэрхийлдэг болохыг харуулж болно. Энэ нь Унгарын алгоритмд ч тохиолддог: бид хатуу ирмэгүүдээс ($A[i][j]-u[i]-v[j]$ хэмжигдэхүүн нь тэг байх ирмэгүүд) тогтох дэд граф үүсгэж, тааруулалтын хэмжээг нэмэгдүүлэхийг оролддог.

4-р алхамд бүх $h(v)$ шинэчлэгдэнэ: бид урсгалын сүлжээг өөрчлөх бүрд эхээс хүрэх зай зөв байхыг баталгаажуулах ёстой (эс бөгөөс дараагийн итерацад Дейкстрагийн алгоритм бүтэлгүйтэж болно). Энэ нь потенциал дээр гүйцэтгэдэг шинэчлэлтэй төстэй сонсогдох боловч энэ тохиолдолд тэдгээр нь ижил хэмжээгээр нэмэгддэггүй.

Потенциалын талаарх ойлголтоо гүнзгийрүүлэхийн тулд энэ өгүүлэл-ийг үз.

Даалгаврын жишээ¶

Хуваарилалтын бодлоготой холбоотой маш тривиалаас эхлээд бага илэрхий даалгавар хүртэлх хэдэн жишээ энд байна:

Хоёр хэсэгт граф өгөгдсөн бол түүн дотроос хамгийн бага жинтэй хамгийн их тааруулалт-ыг олох шаардлагатай (өөрөөр хэлбэл эхлээд тааруулалтын хэмжээг хамгийн их болгож, дараа нь түүний өртгийг хамгийн бага болгоно).
Үүнийг бодохын тулд бид дутуу ирмэгийн оронд "хязгааргүй" тоог тавьж хуваарилалтын бодлогыг зүгээр л байгуулна. Үүний дараа бид бодлогыг Унгарын алгоритмаар бодож, хязгааргүй жинтэй ирмэгүүдийг хариунаас хасна (хэрэв бодлого төгс тааруулалтын хэлбэрээр шийдгүй бол тэдгээр нь хариунд орж болно).
Хоёр хэсэгт граф өгөгдсөн бол түүн дотроос хамгийн их жинтэй хамгийн их тааруулалт-ыг олох шаардлагатай.
Шийд дахин илэрхий, бүх жинг хасах нэгээр үржүүлэх ёстой.
Зураг дээрх хөдөлж буй биетийг илрүүлэх даалгавар: хоёр зураг авсны үр дүнд хоёр багц координат гарсан. Эхний ба хоёр дахь зураг дээрх биетүүдийг харгалзуулах, өөрөөр хэлбэл хоёр дахь зургийн цэг бүрийн хувьд эхний зургийн аль цэгт харгалзаж байсныг тодорхойлох шаардлагатай. Энэ тохиолдолд харьцуулж буй цэгүүдийн хоорондох зайн нийлбэрийг хамгийн бага болгох шаардлагатай (өөрөөр хэлбэл бид биетүүд нийтдээ хамгийн богино замыг туулсан шийдийг хайж байна).
Бодохын тулд бид ирмэгийн жин нь цэгүүдийн хоорондох Евклидийн зай байх хуваарилалтын бодлогыг зүгээр л байгуулж бодно.
Локатораар хөдөлж буй биетийг илрүүлэх даалгавар: биетийн орон зай дахь байрлалыг биш зөвхөн чиглэлийг нь тодорхойлж чадах хоёр локатор байна. Хоёр локатор (өөр өөр цэгт байрлах) ийм $n$ чиглэлийн хэлбэрээр мэдээлэл хүлээн авсан. Биетүүдийн байрлалыг тодорхойлох, өөрөөр хэлбэл биетүүдээс чиглэлийн туяа хүрэх зайн нийлбэр хамгийн бага байхаар биетүүдийн хүлээгдэж буй байрлал ба тэдгээрт харгалзах чиглэлийн хосуудыг тодорхойлох шаардлагатай.
Шийд: дахин хэлэхэд бид зүүн хэсгийн орой нь эхний локатороос гарах $n$ чиглэл, баруун хэсгийн орой нь хоёр дахь локатороос гарах $n$ чиглэл, ирмэгийн жин нь харгалзах туяануудын хоорондох зай байх хуваарилалтын бодлогыг зүгээр л байгуулж бодно.
Чиглэлтэй циклгүй графыг замуудаар бүрхэх: чиглэлтэй циклгүй граф өгөгдсөн бол графын орой бүр яг нэг замд орших байдлаар хамгийн цөөн тооны замыг (тэнцүү бол хамгийн бага нийт жинтэйг) олох шаардлагатай.
Шийд нь өгөгдсөн графаас харгалзах хоёр хэсэгт графыг байгуулж, түүн дотроос хамгийн бага жинтэй хамгийн их тааруулалтыг олох явдал юм. Дэлгэрэнгүйг тусдаа өгүүллээс үз.
Модны будах ном. Навчнаас бусад орой бүр нь яг $k-1$ хүүхэдтэй мод өгөгдсөн. Хоёр зэргэлдээ орой ижил өнгөтэй байхгүй байхаар орой бүрд байгаа $k$ өнгөний нэгийг сонгох шаардлагатай. Түүнчлэн орой бүр ба өнгө бүрийн хувьд энэ оройг энэ өнгөөр будах өртөг мэдэгдэж байгаа бөгөөд нийт өртгийг хамгийн бага болгох шаардлагатай.
Энэ бодлогыг бодохын тулд бид динамик программчлал ашиглана. Тухайлбал $d[v][c]$ утгыг хэрхэн тооцоолохыг сурцгаая, энд $v$ нь оройн дугаар, $c$ нь өнгөний дугаар бөгөөд $d[v][c]$ утга нь өөрөө $v$-д үндэслэсэн дэд мод дахь бүх оройг, мөн орой $v$-г өөрийг нь өнгө $c$-ээр будахад шаардагдах хамгийн бага өртөг юм. Ийм утга $d[v][c]$-г тооцоолохын тулд үлдсэн $k-1$ өнгийг орой $v$-ийн хүүхдүүдийн дунд хуваарилах шаардлагатай бөгөөд үүний тулд хуваарилалтын бодлогыг байгуулж бодох шаардлагатай (үүнд зүүн хэсгийн орой нь өнгө, баруун хэсгийн орой нь хүүхдүүд, ирмэгийн жин нь $d$-ийн харгалзах утга байна).
Ингэснээр $d[v][c]$ утга бүрийг хуваарилалтын бодлогын шийдийг ашиглан тооцоолох ба энэ нь эцэстээ $\mathcal{O}(nk^4)$ асимптотыг өгнө.
Хэрэв хуваарилалтын бодлогод жин нь ирмэг дээр биш орой дээр, түүнчлэн зөвхөн нэг хэсгийн орой дээр байвал Унгарын алгоритм ашиглах шаардлагагүй: оройнуудыг жингээр нь эрэмбэлээд ердийн Куны алгоритм-ыг ажиллуулахад л хангалттай (дэлгэрэнгүйг тусдаа өгүүлэл-ээс үз).
Дараах тусгай тохиолдол-ыг авч үзье. Зүүн хэсгийн орой бүрд ямар нэг тоо $\alpha[i]$, баруун хэсгийн орой бүрд $\beta[j]$ оноогдсон байг. Дурын ирмэг $(i,j)$-ийн жин $\alpha[i]\cdot \beta[j]$-тэй тэнцүү байг ($\alpha[i]$ ба $\beta[j]$ тоонууд мэдэгдэж байна). Хуваарилалтын бодлогыг бод.
Үүнийг Унгарын алгоритмгүйгээр бодохын тулд эхлээд хоёр хэсэг тус бүр хоёр оройтой тохиолдлыг авч үзье. Энэ тохиолдолд таны амархан харж болохоор оройнуудыг урвуу дарааллаар холбох нь дээр: бага $\alpha[i]$-тэй оройг их $\beta[j]$-тэй оройтой холбоно. Энэ дүрмийг дурын тооны оройд амархан ерөнхийлж болно: эхний хэсгийн оройнуудыг $\alpha[i]$ утгын өсөх дарааллаар, хоёр дахь хэсгийг $\beta[j]$ утгын буурах дарааллаар эрэмбэлж, оройнуудыг тэр дарааллаар хос хосоор нь холбох хэрэгтэй. Ингэснээр бид $\mathcal{O}(n\log n)$ complexity-тэй шийд авна.
Потенциалын бодлого. Матриц $A[1 \ldots n][1 \ldots m]$ өгөгдсөн бол дурын $i$ ба $j$-ийн хувьд $u[i] + v[j] \leq a[i][j]$ байх ба массив $u$ ба $v$-ийн элементүүдийн нийлбэр хамгийн их байх хоёр массив $u[1 \ldots n]$ ба $v[1 \ldots m]$-г олох шаардлагатай.
Унгарын алгоритмыг мэдэж байвал энэ бодлогын шийд хэцүү биш байх болно: Унгарын алгоритм бодлогын нөхцөлийг хангах яг ийм потенциал $u, v$-г олдог. Нөгөө талаас Унгарын алгоритмыг мэдэхгүйгээр ийм бодлогыг бодох нь бараг боломжгүй мэт санагдана.

Тэмдэглэл

Энэ даалгаврыг мөн хуваарилалтын бодлогын дуал бодлого гэж нэрлэдэг: хуваарилалтын нийт өртгийг хамгийн бага болгох нь потенциалын нийлбэрийг хамгийн их болгохтой эквивалент юм.

Хуваарилалтын бодлогыг бодох Унгарын алгоритм¶

Хуваарилалтын бодлогын томьёолол¶

Унгарын алгоритм¶

Түүхэн лавлагаа¶

$\mathcal{O}(n^4)$ алгоритм¶

$\mathcal{O}(n^3)$ алгоритм¶

Implementation of the Hungarian algorithm¶

Дараалсан хамгийн богино замын алгоритмтай холбоо¶

Даалгаврын жишээ¶

Ном зүй¶

Дасгал бодлогууд¶