468,253 Members | 1,278 Online

# implementing data structure

Hi, I need to implement a suitable data structure (in c++) for the following problem.
Each state has x,y,z coordinates and a value function (x^2+y^2+z^2)
Starting with the first state (x1,y1,z1) you can have a control vector (with 10 values 1,2,3...10) .You have to choose one value from the vecror and each desicion brings you a new state which has new unique coordinates and value function (function of the previous coordinates and the control value). And so on, each new state splits to 10 new states exc..
After implementing the data structure, there is a knows algorithm which finds the best route to choose (from the value function of all the states).
How can I implement the data structure?
May 18 '10 #1
3 1553
donbock
2,422 Expert 2GB

You should also consider what resolution is appropriate for the state coordinates. How close do the coordinates of two states have to be before they should be considered to be the same state?

How will you keep the number of states bounded?
May 18 '10 #2
jkmyoung
2,057 Expert 2GB
Can any of the value functions have negative costs? If so, there is the possibility of having no optimal route (an infinite looping route).

The algorithm sounds like a specific version of Dijkstra's algorithm
May 18 '10 #3
All the value functions are positive. The algorithm for finding the best route is dynamic programming, but my problem is not to find the algorithm for finding the best route but to build a suitable database in c++.
About keeping the number of states bounded, I think that stopping the recursive algorithm after X iterations will do the job.
May 19 '10 #4