c++ - 割り当て問題を解決するための分岐限定アルゴリズム

Question

C++ での代入問題に対して Branch and Bound Algorithm を開始しましたが、適切な解決策が見つかりません。まずは課題問題例： 課題課題

各人に 1 つの仕事を割り当てることができます。アイデアは、すべての仕事が最も迅速に完了するように、各仕事を 1 人に割り当てることです。

これまでの私のコードは次のとおりです。

#include "Matrix.h"
// Program to solve Job Assignment problem
// using Branch and Bound

#include <limits.h>
#include <vector>
#include <algorithm>



using namespace std;

template<class T>

NUM getCost(Matrix& matrix, size_t x, size_t y, vector<bool>& colUsed);

void run(Matrix& matrix, vector<size_t>& assignedJobs);



int main()
{
    Matrix matrix;
    matrix.setMatrix(N);
    matrix.print();

    vector<size_t> assignedJobs;

    run(matrix, assignedJobs);
    cout << assignedJobs[0];
    /*
    cout << "size:E " << v.size() << endl;
    for (vector<NUM>::iterator i = v.begin(); i != v.end(); i++)
    {
        cout << *i << endl;
    }
    */
    return 0;
}

// remember to use x only LOCALLY!!!
NUM getCost(Matrix& matrix, size_t x, size_t y, vector<bool>& colUsed)
{
    // pathCost
    NUM pathCost = matrix.matrix[x++][y];

    for (size_t col = 0; col < matrix.size(); col++)
    {
        if (!colUsed.at(col))
        {
            NUM min =
            #if defined NUM_INT
                        INT_MAX;
            #endif
            #if defined NUM_DBL
                        DBL_MAX;
            #endif
            size_t row = x;
            for (; row < matrix.size(); row++)
            {
                if (min > matrix.matrix[row][col])
                {
                    min = matrix.matrix[row][col];
                }
            }
            pathCost += min;
        }

    }
    return pathCost;
}

void run(Matrix& matrix, vector<size_t>& assignedJobs)
{
    // array of used columns
    vector<bool> colUsed;
    for (size_t i = 0; i < matrix.size(); i++)
    {
        colUsed.push_back(false);
    }

    for (size_t row = 0; row < matrix.size(); row++)
    {
        size_t col = 0;
        // bombona
        while (colUsed.at(col++)); col--;
        // choose the best job for the current worker
        vector<NUM> jobs;
        // get all the job costs from which to choose the smallest
        // row++
        jobs.push_back(getCost(matrix, col, row, colUsed));
        // iterator at the position of the smallest element of jobs
        vector<NUM>::iterator i_min = min_element(jobs.begin(), jobs.end());
        // index of the smallest element in jobs
        size_t index = (size_t)distance(jobs.begin(), i_min);

        colUsed.at(index) = true;
        assignedJobs.push_back(index);
    }
}

私は軌道から外れているかもしれないことを知っています。最初は下限を使用しませんでした。実際、このアルゴリズムが正確にどのように機能するか少し混乱しています。そのため、アルゴリズムの段階的なウォークスルーでも役立ちます。