Class to solve simple dynamic programming problems. More...
#include <mbl_dyn_prog.h>
Public Member Functions | |
| mbl_dyn_prog () | |
| Dflt ctor. | |
| virtual | ~mbl_dyn_prog () |
| Destructor. | |
| double | solve (vcl_vector< int > &x, const vnl_matrix< double > &W, const vnl_vector< double > &pair_cost, int first_state=-1) |
| Solve the dynamic programming problem with costs W. | |
| double | solve_loop (vcl_vector< int > &x, const vnl_matrix< double > &W, const vnl_vector< double > &pair_cost) |
| Solve the loop dynamic programming problem with costs W. | |
| short | version_no () const |
| Version number for I/O. | |
| virtual vcl_string | is_a () const |
| Name of the class. | |
| virtual void | print_summary (vcl_ostream &os) const |
| Print class to os. | |
| virtual void | b_write (vsl_b_ostream &bfs) const |
| Save class to binary file stream. | |
| virtual void | b_read (vsl_b_istream &bfs) |
| Load class from binary file stream. | |
Private Member Functions | |
| void | construct_path (vcl_vector< int > &x, int end_state) |
| Construct path from links_, assuming it ends at end_state. | |
| void | running_costs (const vnl_matrix< double > &W, const vnl_vector< double > &pair_cost, int first_state) |
| Compute running costs for DP problem with costs W. | |
Private Attributes | |
| vbl_array_2d< int > | links_ |
| After search, links_(i,j) shows the best prior state. | |
| vnl_vector< double > | running_cost_ |
| Workspace for running cost. | |
| vnl_vector< double > | next_cost_ |
| Workspace for previous running cost. | |
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))
Definition at line 25 of file mbl_dyn_prog.h.
| mbl_dyn_prog::mbl_dyn_prog | ( | ) |
Dflt ctor.
Definition at line 18 of file mbl_dyn_prog.cxx.
| mbl_dyn_prog::~mbl_dyn_prog | ( | ) | [virtual] |
Destructor.
Definition at line 26 of file mbl_dyn_prog.cxx.
| void mbl_dyn_prog::b_read | ( | vsl_b_istream & | bfs | ) | [virtual] |
Load class from binary file stream.
Definition at line 237 of file mbl_dyn_prog.cxx.
| void mbl_dyn_prog::b_write | ( | vsl_b_ostream & | bfs | ) | const [virtual] |
Save class to binary file stream.
Definition at line 226 of file mbl_dyn_prog.cxx.
| void mbl_dyn_prog::construct_path | ( | vcl_vector< int > & | x, |
| int | end_state | ||
| ) | [private] |
Construct path from links_, assuming it ends at end_state.
Definition at line 32 of file mbl_dyn_prog.cxx.
| vcl_string mbl_dyn_prog::is_a | ( | ) | const [virtual] |
Name of the class.
Definition at line 207 of file mbl_dyn_prog.cxx.
| void mbl_dyn_prog::print_summary | ( | vcl_ostream & | os | ) | const [virtual] |
Print class to os.
Definition at line 217 of file mbl_dyn_prog.cxx.
| void mbl_dyn_prog::running_costs | ( | const vnl_matrix< double > & | W, |
| const vnl_vector< double > & | pair_cost, | ||
| int | first_state | ||
| ) | [private] |
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
Definition at line 51 of file mbl_dyn_prog.cxx.
| double mbl_dyn_prog::solve | ( | vcl_vector< int > & | x, |
| const vnl_matrix< double > & | W, | ||
| const vnl_vector< double > & | pair_cost, | ||
| int | first_state = -1 |
||
| ) |
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
| x | Optimal path |
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
| x | Optimal path |
Definition at line 128 of file mbl_dyn_prog.cxx.
| double mbl_dyn_prog::solve_loop | ( | vcl_vector< int > & | x, |
| const vnl_matrix< double > & | W, | ||
| const vnl_vector< double > & | pair_cost | ||
| ) |
Solve the loop dynamic programming problem with costs W.
Solve the DP problem including constraint between first and last.
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.
| x | Optimal path |
Cost of moving from state i to state j is move_cost[j-i] (move_cost[i] must be valid for i in range [1-n_states,n_states-1]) Includes cost between x[0] and x[n-1] to ensure loop closure.
| x | Optimal path |
Definition at line 157 of file mbl_dyn_prog.cxx.
| short mbl_dyn_prog::version_no | ( | ) | const |
Version number for I/O.
Definition at line 198 of file mbl_dyn_prog.cxx.
vbl_array_2d<int> mbl_dyn_prog::links_ [private] |
After search, links_(i,j) shows the best prior state.
(ie at i) leading to state j at time i+1
Definition at line 29 of file mbl_dyn_prog.h.
vnl_vector<double> mbl_dyn_prog::next_cost_ [private] |
Workspace for previous running cost.
Definition at line 36 of file mbl_dyn_prog.h.
vnl_vector<double> mbl_dyn_prog::running_cost_ [private] |
Workspace for running cost.
After search gives cost to get to each state in last row
Definition at line 33 of file mbl_dyn_prog.h.
1.7.5.1