468,253 Members | 1,278 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,253 developers. It's quick & easy.

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
Each instance of the structure holds all the data associated with a single state. The state variables are the coordinates and the control vector -- you need fields for these. If your map contains loops then it might improve your execution speed if you additionally had fields for the value and the links to the ten next states. When you compute the links to the ten next states you will need to determine if each next state already exists or if you will have to create it. It may be helpful if you provide a supplemental link in the state structure to assist with that determination. Your route algorithm may require additional fields (for example, if it colors each state).

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

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

4 posts views Thread by puzzlecracker | last post: by
6 posts views Thread by herrcho | last post: by
reply views Thread by dawn | last post: by
3 posts views Thread by Tommy Vercetti | last post: by
4 posts views Thread by aaragon | last post: by
13 posts views Thread by tim.lino | last post: by
2 posts views Thread by nomad | last post: by
reply views Thread by NPC403 | last post: by
reply views Thread by kermitthefrogpy | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.