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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
#ifndef mbl_dyn_prog_h_
#define mbl_dyn_prog_h_
//:
// \file
// \brief Class to solve simple dynamic programming problems
// \author Tim Cootes
#include <vcl_string.h>
#include <vcl_iosfwd.h>
#include <vsl/vsl_fwd.h>
#include <vnl/vnl_matrix.h>
#include <vcl_vector.h>
#include <vbl/vbl_array_2d.h>
#include <vnl/vnl_vector.h>
//: Class to solve simple dynamic programming problems
// Assume n values x(i) to be chosen, x(i) in [0,k-1], i=0..n-1
// Cost of each is W(i,x(i))
// Total cost = sum_i W(i,x(i)) + C_i(x(i),x(i-1))
// The algorithm finds the path (x(0),x(1)..x(n-1)) through which minimises
// the total cost, with a variety of different ways of defining C_i(x(i),x(i-1))
//
class mbl_dyn_prog {
private:
//: After search, links_(i,j) shows the best prior state
// (ie at i) leading to state j at time i+1
vbl_array_2d<int> links_;
//: Workspace for running cost.
// After search gives cost to get to each state in last row
vnl_vector<double> running_cost_;
//: Workspace for previous running cost.
vnl_vector<double> next_cost_;
//: Construct path from links_, assuming it ends at end_state
void construct_path(vcl_vector<int>& x, int end_state);
//: Compute running costs for DP problem with costs W
// Pair cost term: C_i(x1,x2) = c(|x1-x2|)
// Size of c indicates maximum displacement between neighbouring
// states.
// If first_state>=0 then the first is constrained to that index value
void running_costs(const vnl_matrix<double>& W,
const vnl_vector<double>& pair_cost,
int first_state);
public:
//: Dflt ctor
mbl_dyn_prog();
//: Destructor
virtual ~mbl_dyn_prog();
//: Solve the dynamic programming problem with costs W
// Pair cost term: C_i(x1,x2) = pair_cost(|x1-x2|)
// Size of c indicates maximum displacement between neighbouring
// states.
// If first_state>=0 then the first is constrained to that index value
// \retval x Optimal path
// \return Total cost of given path
double solve(vcl_vector<int>& x,
const vnl_matrix<double>& W,
const vnl_vector<double>& pair_cost,
int first_state=-1);
//: Solve the loop dynamic programming problem with costs W
// Pair cost term: C_i(x1,x2) = pair_cost(|x1-x2|)
// Size of c indicates maximum displacement between neighbouring
// states.
// As solve(x,W,c), but includes constraint between first and
// last states.
// \retval x Optimal path
// \return Total cost of given path
double solve_loop(vcl_vector<int>& x,
const vnl_matrix<double>& W,
const vnl_vector<double>& pair_cost);
//: Version number for I/O
short version_no() const;
//: Name of the class
virtual vcl_string is_a() const;
//: Print class to os
virtual void print_summary(vcl_ostream& os) const;
//: Save class to binary file stream
virtual void b_write(vsl_b_ostream& bfs) const;
//: Load class from binary file stream
virtual void b_read(vsl_b_istream& bfs);
};
//: Binary file stream output operator for class reference
void vsl_b_write(vsl_b_ostream& bfs, const mbl_dyn_prog& b);
//: Binary file stream input operator for class reference
void vsl_b_read(vsl_b_istream& bfs, mbl_dyn_prog& b);
//: Stream output operator for class reference
vcl_ostream& operator<<(vcl_ostream& os,const mbl_dyn_prog& b);
//=======================================================================
#endif
|
