Learning About the Graph Construct using Games, Part II - Back to the water problem
(Page 5 of 5 )
We have now described both algorithms, so let's return to the problem at hand. I hope you haven't forgotten our problem was actually to find the steps needed to divide eight liters of water into two fours. All that we have explained was just background to get us back into the problem we are solving!
In the previous part we described how to construct the graph. All that remained was to find the shortest path from the "8","0","0" node to the "4","4","0" node.
Since we are not interested in all the pairs for the shortest path, it would be much easier to use Dijkstra's algorithm to find the single source shortest path starting at the "8","0","0" node.
Here is the source code we need to add to the previous part:
First, we added the three arrays required by the algorithm:
int[] distance;
boolean[] found;
int[] prev;
Next, this is the function that chooses the node that was not visited, and having the smallest distance:
int choose()
{
int min=10000000;
int minPos=-1;
for(int i=0;i<data.size();i++)
{
if(distance[i]<min&&!found[i])
{
min=distance[i];
minPos=i;
}
}
return minPos;
}
This is not a very hard function. All it does is find the node with the smallest distance that has not been visited before.
Next, here is the function that actually finds the shortest path. This is the actual implementation of Dijkstra's algorithm.
void findPath()
{
distance=new int[data.size()];
found=new boolean[data.size()];
prev=new int[data.size()];
//prepare 3 arrays
for(int i=0;i<data.size();i++)
distance[i]=1000000;
//node 0 is the one we will start from
//so, prepare distances of nodes directly connected to it
node2 t=((node)(data.elementAt(0))).links;
while(t!=null)
{
distance[t.id]=1;
t=t.next;
}
distance[0]=0;
found[0]=true;
//do the real work
for(int i=0;i<data.size()-2;i++)
{ //find nearest node
int u=choose();
found[u]=true;
//see if we can improve distances to other nodes
for(int w=0;w<data.size();w++)
{
if(!found[w])
{
if(distance[u]+getCost(u,w)<distance[w])
{
distance[w]=distance[u]+getCost(u,w);
prev[w]=u;
}
}
}
}
}
This function is pretty straightforward too. It just performs the algorithm we mentioned step by step.
Finally, here is a function to display the actual steps needed. As noted earlier, Dijkstra's algorithm finds, for every node, the node previous to it. This function, therefore, prints the path in reverse order! It is extremely easy to modify it to print the path in the correct order (you can add a vector of Tuples, add the solution steps to it, then print it backward); this is left as an exercise.
void print
{
int ourTarget=0;
//find the index of the "4", "4","0" node
for(int w=0;w<data.size();w++)
{
if(((node)(data.elementAt(w))).data.a==4&&((node)(data.elementAt(w))).data.b==4)
ourTarget=w;
}
while(ourTarget!=0)
{
System.out.print("Step: "+(((node)(data.elementAt(ourTarget))).data.a)+" "+(((node)(data.elementAt(ourTarget))).data.b)+" "+(((node)(data.elementAt(ourTarget))).data.c)+"->");
ourTarget=prev[ourTarget];
}
//print last step
System.out.print("Step "+(((node)(data.elementAt(ourTarget))).data.a)+" "+(((node)(data.elementAt(ourTarget))).data.b)+" "+(((node)(data.elementAt(ourTarget))).data.c)+"->");
}
Whew, we have done something great. We have finally solved the problem at hand! And not just that: this category of problems is over! We can solve any variations with minimal changes. For example, a famous variation was to do the same problem but with jugs of capacities 12, 9 and 7 liters; we needed to divide 12 liters into two sixes. It is very easy to make this modification now, isn't it?
Oh, and if you don't have the time to actually run the program, here is the solution. It takes only 7 steps to solve this problem:
Initial capacities: 8,0,0
Jug 1à Jug 2: 3,5,0
Jug 2à Jug 3: 3,2,3
Jug 3à Jug 1: 6,2,0
Jug 2à Jug 3: 6,0,2
Jug 1à Jug 2: 1,5,2
Jug 2à Jug 3: 1,4,3
Jug 3à Jug 1: 4,4,0
And, that concludes part two of this three part series. What is to come in the next part? We are going to handle a totally new game, and see what we can do. We are going to be talking about Euler tours, simple paths and simple loops.
Remember, if you have any questions, suggestions, or comments, you can always drop me an email at msaad@themagicseal.com, I would like to hear from you.
Good Luck!
| DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware. |
