You're going to have some serious trouble in school my friend.

You're not understanding the problem as it was given to you. By your first sentence, you're supposed to find a solution the Tower of Hanoi problem using BFS, DFS, and IDS algorithms.

You apparently took that to mean, implement the recursive solution as shown on wikipedia's entry for Tower of Hanoi and then you're somehow trying to figure out how to include the different algorithms into it.

As far as I can tell, here is what you're supposed to do.

Assume you have no knowledge of the way to solve the problem. You only know that you have 3 pegs, you can only move one disc at a time, and you cannot move a larger disc onto a smaller disc.

Now, implement the Breadth-First Search algorithm to find the solution.

So, how would you do that? The question is trying to get you to implement each algorithm to find the solution.

For BFS, how does the algorithm work? Well, you start with the root node. Then, you build the child nodes of that root node and link them as neighbors. So, to start, you have two moves that you can make...move the top disc to the middle, or to the opposite end. So, look at the first child. Does that solve it? If not, look at the next child. Does that solve it?

If none of the children solve it, look at the first child and add in it's children. Look at them. Wikipedia has a good animation to show the steps to take (Animated_BFS.gif[^])

So, implement this algorithm to solve the problem. The BFS doesn't know anything about the tree until it builds the children. You don't build the whole tree and then search through it. That's why it's called an uninformed search.

I'll do it for you...if you pay me. $60 per hour of my time sounds reasonable.

[Added]

Just to add to this, a Breadth-First Search is crazy memory intensive if you are trying to re-create the path. For example, if there are 6 disks on the tree, the solution takes (2^6)-1 moves to solve or 63 moves to solve. That means that with a BFS search, there would be 63 different levels...not including the root.

It's a ridiculous number of nodes at the 63rd level and if you want to be able to follow the path, you have to keep track of everything. Just as an example for any number of disks.

At the beginning, there are 2 moves.

After the 1st move, there are 6 moves.

After the 2nd move, there are 18 moves.

It works out to 0.9643e^(1.0995((2^x)-1) where x is the number of disks. With 6 disks, that's a total of 1.14*10^30 moves to keep track of. I ran out of memory trying to solve a problem with only 4 disks.

So, good luck with that.

11,492,962 members (58,150 online)

Email

Password

Sign in using