Interactive Programming Education Platform

Logic Practice

This implementation of the Hungarian Algorithm in C++ efficiently addresses the assignment dilemma by assigning tasks to resources to optimize gains or reduce costs. The best assignment is identified through a cost matrix and a sequence of operations, including adjustments, row and column reductions, and zero labeling. This method is particularly suitable for resource allocation and scheduling tasks, as it ensures a favorable O(n^3) time complexity for an n×n matrix. Within the C++ implementation, the matrix and task assignments are methodically managed using data structures like 2D arrays or vectors.

Key features of the Hungarian algorithm:

Several key features of the Hungarian algorithm in C++ are as follows:

✅ The cost of allocating a task to a resource is represented by each element of the cost matrix, which resolves the assignment problem.
✅ Assures the best possible outcome.
✅ For n × n cost matrix, it operates in O(n 3 ) time complexity.
✅ Works with both square and rectangular matrices by adding dummy rows or columns as necessary to the matrix's padding.

Basic Steps of the Hungarian algorithm:

✅ Row reduction: Row reduction is calculated by deducting the row's smallest value from each of its members.
✅ Column Reduction: Take the smallest value from each column and subtract it from all of its constituents.
✅ Zero Marking: Use a minimum of lines to cover all rows and columns with zero elements. When the number of lines is equal to the size of the matrix, the best possible assignment is chosen.
✅ Adjusting the matrix: The matrix can be adjusted by repeating marking and adjusting the uncovered components if the number of lines is fewer than the matrix size.
✅ Assignment: Use the elements with a zero to determine the best assignments.
✅ Use a minimum of lines to cover all rows and columns with zero elements.
✅ When the number of lines is equal to the size of the matrix, the best possible assignment is chosen.

Hungarian algorithm in C++:

The implementation of Hungarian algorithm involves:

✅ The cost matrix can be shown using a 2D array or vector.
✅ The steps listed above are carried out iteratively using nested loops.
✅ Using auxiliary data structures to keep an eye on assigned rows, columns, and assignments.

Example code:

Example


#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;
// Function to perform the Hungarian Algorithm
vector<int> hungarianAlgorithm(vector<vector<int>>& costMatrix) {
    int n = costMatrix.size();
    vector<int> assignment(n, -1);
    vector<int> u(n, 0), v(n, 0), p(n, 0), way(n, 0);
    for (int i = 1; i <= n; ++i) {
        vector<int> minv(n + 1, numeric_limits<int>::max());
        vector<bool> used(n + 1, false);
        int j0 = 0;
        p[0] = i;
        do {
            used[j0] = true;
            int i0 = p[j0], delta = numeric_limits<int>::max(), j1 = 0;
            for (int j = 1; j <= n; ++j) {
                if (!used[j]) {
                    int cur = costMatrix[i0 - 1][j - 1] - 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 <= n; ++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);
    }
    for (int j = 1; j <= n; ++j) {
        assignment[p[j] - 1] = j - 1;
    }
    return assignment;
}
// Main function
int main() {
    vector<vector<int>> costMatrix = {
        {4, 2, 5},
        {3, 8, 2},
        {6, 1, 9}
    };
    vector<int> result = hungarianAlgorithm(costMatrix);
    cout << "Optimal Assignment:\n";
    for (int i = 0; i < result.size(); ++i) {
        cout << "Task " << i + 1 << " -> Worker " << result[i] + 1 << endl;
    }
    return 0;
}

Output:

Output


Optimal Assignment:
Task 1 -> Worker 1
Task 2 -> Worker 3
Task 3 -> Worker 2

Explanation:

✅ In this example, the HungarianAlgorithm function uses the dual optimization technique.
✅ The u and v store the dual variables for rows and columns.
✅ P and way track the augmented path.
✅ The result is the optimal assignment, assigning each task to the most cost-effective worker.

Conclusion:

In summary, operations research, resource allocation, and task scheduling heavily rely on the Hungarian Algorithm, a dependable and efficient resolution for the assignment dilemma. Its methodical approach offers optimal resolutions, and its polynomial time complexity of O(n^3) ensures adaptability for reasonably large datasets. By being implemented in C++, the algorithm can cater to various problem sizes and adapt to specific needs. Employing dynamic data structures like arrays and vectors, it becomes a valuable instrument for real-world applications. This algorithm is crucial in combinatorial optimization and serves as a beneficial resource for developers aiming to cut costs or boost profits.

Hungarian Algorithm In C++