I have an A* algorithm with a heuristic to best guide the best path. The problem is that each node can have up to 240 children and each subsequent child also…

So doing a breadth first approach is going to get me nowhere unless the heuristic is very accurate. The problem is when each child node’s cost and estimate is very much the same as most of the sibling nodes (so a good 100/240 are about the same). In other words there really are 2000+ ways of solving this problem with roughly the same total cost.

I cannot afford the algorithm to go through each option to find the “best” solution as there isn’t much benefit as the difference in cost between all the good options is but 1-5 seconds which is not worth the savings in this project.

So what is the best way to resolve such problems in general.

Some options i’ve tried/know of. (any others?)

• Limiting the number of children in the ‘frontiers’ list (not ideal)
• Grouping all similar child nodes to only return one child node (haven’t tried this yet)