Алгоритм ветвления и ограничения для решения задач назначения

Я начал делать Branch and Bound Algorithm для задачи присваивания в C ++, и я не могу найти правильное решение. В первую очередь пример задачи присваивания:
Задача назначения

Итак, каждый человек может быть назначен на одну работу, и идея состоит в том, чтобы назначить каждую работу одному человеку, чтобы все работы выполнялись максимально быстро.

Вот мой код до сих пор:

#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);
}
}

Я знаю, что могу быть не в курсе. Я не использовал нижнюю границу в начале, я немного запутался, как именно работает этот алгоритм. Так что даже пошаговое прохождение алгоритма будет полезно.

1

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector