The fastest algorithm for TipOver Solver using tree

[Tsuk]

I am making a tipover solver in C.
I'm trying to solve it by creating a tree with all the possible paths and then process all the tree with a level search algorithm, looking for the shortest path. This implementation is pretty easy to do but takes more processing time than I was expecting. So now I'm thinking about do it with a variation of the A* algorithm. Do you think it will run faster? Or the problem is in looking to all the possible paths?

[jkmyoung]

Assuming there is a solution, it should run faster.
My question is: How are you determining which tip is optimal?

I think it would be easier to work backwards, and only allow tips which joined up with the end crate structure.

[Dormilich]

that reminds me of the binary heap (which can be used to find a shortest path)

[Motoma]

Hi!
I'm an engineer student and in my most recent programing class it was proposed to create a tipover solver in C.
I'm trying to solve it by creating a tree with all the possible paths and then process all the tree with a level search algorithm, looking for the shortest path. This implementation is pretty easy to do but takes more processing time than I was expecting. So now I'm thinking about do it with a variation of the A* algorithm. Do you think it will run faster? Or the problem is in looking to all the possible paths?

I don't know if this is the right place to ask this but is the only site I know :)


Thanks !

If I were to attack it, I would use a breadth first search to generate the paths. You stop when you reach a solution.

If the lengths matter, I would apply Djikstra using the above technique.

[Tsuk]

that reminds me of the binary heap (which can be used to find a shortest path)

I'd think about it, but it can't be binary because there are 4 possible paths for each node... right?

Thanks for you'r help.

[Tsuk]

If I were to attack it, I would use a breadth first search to generate the paths. You stop when you reach a solution.

If the lengths matter, I would apply Djikstra using the above technique.

I'm thinking about do it that way, but I'm not seeing how I'm going to create a the tree. If I want to use BFS, the tree will be "Breadth created" or it only mathers after create the tree?
I was thinking about another way to do it. It was a depth search with the help of a counter that saves the number of levels. For example: I start filling the tree till it gets the end. The counter saves the number of levels. Then it goes to another branch and starts filling it. If it reaches the end before the saved number of levels, that number becomes the reference. If it gets equal or bigger than the already saved number of levels that branch is no longer the shortest path.
It looks like a good way to solve it, but in the worst case all the possible paths are visited...
What do you tink?

And thanks for you'r help.

[Dormilich]

I'd think about it, but it can't be binary because there are 4 possible paths for each node... right?

no, the binary comes from the structure of the tree (a node has max. 2 child nodes) binary heap

I think it’s A* based (if I remember right)

[Tsuk]

no, the binary comes from the structure of the tree (a node has max. 2 child nodes) binary heap

I think it’s A* based (if I remember right)

Exactly, it only allows 2 "childs", but I'll need 4 "childs", one for each direction. Or its possible to apply the heap condition with 4 "childs"?
Theoretically I think is possible, I'm just not seeing how to implement it.

[Dormilich]

then you’re misunderstandin g the Binary Heap. It is used to effectively find the biggest/smallest value in a set (the larger the set, the more effective the Binary Heap).

do you have a strategy to find the solution?

[Tsuk]

then you’re misunderstandin g the Binary Heap. It is used to effectively find the biggest/smallest value in a set (the larger the set, the more effective the Binary Heap).

do you have a strategy to find the solution?

I know that the binary heap does that, my doubt is how to use it for this particular problem.
At the moment, my strategy is to find all the possible paths till the program hits the final box, using a kind of tree(every node has 4 son nodes, and is double linked to be possible to reach the father using the son). Than I use Breadth Search First to look for the shortest path.
But I still think that are another more efficient way to do it, I just can't figured out !
Just one more thing, to see if a path is possible and than insert it on the tree i'm using an matrix that is working like a "game board". Thats a good strategy, right?

[jkmyoung]

Only 4 child nodes?
..Whoa: What exactly do you mean by breadth first search?
What constitutes your depth? Have you ordered the stacks in some way?

[Tsuk]

So I've finally done my program. It gave me a lot of work, but it ends up working just fine!

Just for the ones who wanna know how I've done it:


So it starts by creating a vector with the boxes. Than the program looks for the closest box that has a possible knock (most of the boards has a start position in one of those). While it looks for that box it saves the path and when it finds the box he creates a tree node with a pointer to that path. So my tree node structure has a counter(to know the number of moves till that node),a pointer to the path, a pointer to the father node and a coordinate(of the actual box with the respective height). To create the tree in level (BFS) each node goes to a queue and only goes to the tree after being checked for knocks(childs). When it find the end box the first time, it checks the counter of the actual node, the counter of the brothers (in level) and if any of the brothers counters is under the one who find the end. If it verifies that, the algorithm keeps filling the tree till the counter reaches the counter of the first found end. If it finds the end before that, that node corresponds to the smaller path, if not, the first found path is the smaller one.
This explanation is far way simpler than the real complexity of the algorithm, but It gives you an idea (I hope).
Thanks for all you'r help.
See you soon for new questions/answers.