Content deleted Content added
| (9 intermediate revisions by 5 users not shown) | |||
Line 2:
The '''Hungarian method''' is a [[combinatorial optimization]] [[algorithm]] that solves the [[assignment problem]] in [[polynomial time]] and which anticipated later [[Duality (optimization)|primal–dual methods]]. It was developed and published in 1955 by [[Harold Kuhn]], who gave it the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians, [[Dénes Kőnig]] and [[Jenő Egerváry]].<ref name="kuhn1955">Harold W. Kuhn, "The Hungarian Method for the assignment problem", ''[[Naval Research Logistics Quarterly]]'', '''2''': 83–97, 1955. Kuhn's original publication.</ref><ref name="kuhn1956">Harold W. Kuhn, "Variants of the Hungarian method for assignment problems", ''Naval Research Logistics Quarterly'', '''3''': 253–258, 1956.</ref> However, in 2006 it was discovered that [[Carl Gustav Jacobi]] had solved the assignment problem in the 19th century, and the solution had been published posthumously in 1890 in Latin.<ref>{{Cite web|url=http://www.lix.polytechnique.fr/~ollivier/JACOBI/presentationlEngl.htm|archive-url = https://web.archive.org/web/20151016182619/http://www.lix.polytechnique.fr/~ollivier/JACOBI/presentationlEngl.htm|archive-date = 16 October 2015|title = Presentation}}</ref>
[[James Munkres]] reviewed the algorithm in 1957 and observed that it is [[
==The problem==
Line 148:
*/
import std;
template <typename T, typename U>
using Pair = std::pair<T, U>;
template <typename T>
using Vector = std::vector<T>;
template <typename T>
using NumericLimits = std::numeric_limits<T>;
/**
* @brief Checks if b < a
*
* Sets a = min(a, b)
* @param a The first parameter to check
* @param b The second parameter to check
* @tparam The type to perform the check on
* @return true if b < a
*/
template <
constexpr bool ckmin(T return b < a ? a = b, } /**
* @brief Performs the Hungarian algorithm.
*
* Given J jobs and W workers (J <= W), computes the minimum cost to assign each
* prefix of jobs to distinct workers.
Line 172 ⟶ 188:
* to assign the first (j+1) jobs to distinct workers
*/
template <typename T>
const int J = (int)size(C), W = (int)size(C[0]);▼
const int J = static_cast<int>(C.size());
const int W = static_cast<int>(C[0].size());
assert(J <= W);
// job[w] = job assigned to w-th worker, or -1 if no job assigned
// note: a W-th worker was added for convenience
Vector<T> yt(W + 1); // potentials // -yt[W] will equal the sum of all deltas
const T inf =
for (int
int
job[
// min reduced cost over edges from Z to worker w
while (job[
const int j = job[
T delta = inf;
int
for (int w = 0; w < W; ++w) {
if (!
if (ckmin(
if (ckmin(delta,
wNext = w;
}
}
// delta will always be nonnegative,
// except possibly during the first time this loop runs
// if any entries of C[
for (int w = 0; w <= W; ++w) {
if (
yt[w] -= delta;
} else {
minTo[w] -= delta;
}▼
}
}
// update assignments along alternating path
for (int w;
job[wCur] = job[w = prev[wCur]];
answers.push_back(-yt[W]);
}
Line 218 ⟶ 243:
/**
* @brief Performs a sanity check for the Hungarian algorithm.
*
* Sanity check: https://en.wikipedia.org/wiki/Hungarian_algorithm#Example
* First job (5):
Line 229 ⟶ 256:
* wash windows: Bob -> 3
*/
void
assert((hungarian(costs) ==
}
/**
void cordon_bleu() {▼
*/
int N, M;▼
vector<pair<int, int>> bottles(N), couriers(M);▼
Vector<Pair<int, int>> B(N);
for (auto &c : couriers) cin >> c.first >> c.second;▼
cin >> rest.first >> rest.second;▼
for (const Pair<int, int>& c: couriers)
Pair<int, int> rest;
▲ std::cin >> rest.first >> rest.second;
Vector<Vector<int>> costs(N, Vector<int>(N + M - 1));
auto dist = [&](const Pair<int, int>& x, const Pair<int, int>& y) -> int {
return std::abs(x.first - y.first) + std::abs(x.second - y.second);
};
for (int b = 0; b < N; ++b) {
for (int c = 0; c < M; ++c)
costs[b][c] = dist(couriers[c], bottles[b]) + dist(bottles[b], rest);
▲ }
▲ for (int _ = 0; _ < N - 1; ++_) { // restaurant -> bottle -> restaurant
costs[b][_ + M] = 2 * dist(bottles[b], rest);
}
}
/**
* @brief Entry point into the program.
*
* @return The return code of the program.
*/
int main() {
}
</syntaxhighlight>
Line 290 ⟶ 326:
<syntaxhighlight lang="cpp" line="1">
template <typename T>
▲ const int J = (int)size(C), W = (int)size(C[0]);
const int W = static_cast<int>(C[0].size());
assert(J <= W);
// job[w] = job assigned to w-th worker, or -1 if no job assigned
// note: a W-th worker was added for convenience
T
const T inf =
// assign
for (int
int
job[
dist[W] = 0;
while (job[
T
vis[
int
// consider extending shortest path by
for (int w = 0; w < W; ++w) {
if (!vis[w]) {
// sum of reduced edge weights
T edge = C[job[
if (
edge -= C[job[
assert(edge >= 0); // consequence of Johnson potentials
}
if (ckmin(dist[w], dist[
if (ckmin(minDist, dist[w]))
wNext = w;
}
}
}
for (int w = 0; w < W; ++w) { // update potentials
ckmin(dist[w], dist[
h[w] += dist[w];
}
ans_cur += h[
for (int w;
answers.push_back(ansCur);
}
return answers;
Line 529 ⟶ 570:
If the number of starred zeros is {{mvar|n}} (or in the general case <math>min(n,m)</math>, where {{mvar|n}} is the number of people and {{mvar|m}} is the number of jobs), the algorithm terminates. See the [[#Result|Result]] subsection below on how to interpret the results.
Otherwise, find the lowest uncovered value. Subtract this from every
This is equivalent to subtracting a number from all rows which are not covered and adding the same number to all columns which are covered. These operations do not change optimal assignments.
| |||