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)
  • If the proper criteria for picking the optimal solution is not marginal differences in cost, then what is the proper criteria? – Robert Harvey Oct 16 '14 at 22:08
  • Thats a good question @robertharvey... I suppose the criteria is marginal cost differences that in the end add up to more significant cost differences. But in doing so there are many other alternative solutions being dragged along that are essentially the same. The criteria then is to eliminate the bad options and go with any of the "acceptable/similar" options but not all acceptable/similar options. – Riaan Schutte Oct 16 '14 at 22:19
  • Then you have to find some inexpensive criteria that preemptively eliminates most candidates before you apply the more costly search method. – Robert Harvey Oct 16 '14 at 22:21
  • Sure.. And this criteria would then, in essence, do the grouping i mentioned in my question? – Riaan Schutte Oct 16 '14 at 22:24
  • You mean your bullet two? I suppose. You could use the criteria to return the "best fit" one. – Robert Harvey Oct 16 '14 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.