blob: bbdb0abfb36035ce91efae9f0e09cd7d8ea331c1 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
// Copyright (C) 2011 Davis E. King (davis@dlib.net)
// License: Boost Software License See LICENSE.txt for the full license.
#undef DLIB_MAX_COST_ASSIgNMENT_ABSTRACT_Hh_
#ifdef DLIB_MAX_COST_ASSIgNMENT_ABSTRACT_Hh_
#include "../matrix.h"
#include <vector>
namespace dlib
{
// ----------------------------------------------------------------------------------------
template <typename EXP>
typename EXP::type assignment_cost (
const matrix_exp<EXP>& cost,
const std::vector<long>& assignment
);
/*!
requires
- cost.nr() == cost.nc()
- for all valid i:
- 0 <= assignment[i] < cost.nr()
ensures
- Interprets cost as a cost assignment matrix. That is, cost(i,j)
represents the cost of assigning i to j.
- Interprets assignment as a particular set of assignments. That is,
i is assigned to assignment[i].
- returns the cost of the given assignment. That is, returns
a number which is:
sum over i: cost(i,assignment[i])
!*/
// ----------------------------------------------------------------------------------------
template <typename EXP>
std::vector<long> max_cost_assignment (
const matrix_exp<EXP>& cost
);
/*!
requires
- EXP::type == some integer type (e.g. int)
(i.e. cost must contain integers rather than floats or doubles)
- cost.nr() == cost.nc()
ensures
- Finds and returns the solution to the following optimization problem:
Maximize: f(A) == assignment_cost(cost, A)
Subject to the following constraints:
- The elements of A are unique. That is, there aren't any
elements of A which are equal.
- A.size() == cost.nr()
- This function implements the O(N^3) version of the Hungarian algorithm
where N is the number of rows in the cost matrix.
!*/
// ----------------------------------------------------------------------------------------
}
#endif // DLIB_MAX_COST_ASSIgNMENT_ABSTRACT_Hh_
|
