I need an algorithm to find the best path

Question

Hi all,

I need an algorithm to find the best solution of a path finding problem. The problem can be stated as:

• At the starting point I can proceed along multiple different paths.
• At each step there are another multiple possible choices where to proceed.
• There are two operations possible at each step:
  • A boundary condition that determine if a path is acceptable or not.
  • A condition that determine if the path has reached the final destination and can be selected as the best one.
• At each step a number of paths can be eliminated, letting only the "good" paths to grow.

I hope this sufficiently describes my problem, and also a possible brute force solution.

My question is: is the brute force is the best/only solution to the problem, and I need some hint also about the best coding structure of the algorithm. Thanks all.

Answer 1

did you try breadth-first search? (BFS) that is if length is a criteria for best path you will also have to modify the algorithm to disregard "unacceptable paths"

Answer 2

Take a look at A*, and use the length as boundary condition.

http://en.wikipedia.org/wiki/A%2a_search_algorithm

Answer 3

You are looking for some kind of state space search algorithm. Without knowing more about the particular problem, it is difficult to recommend one over another.

If your space is open-ended (infinite tree search), or nearly so (chess, for example), you want an algorithm that prunes unpromising paths, as well as selects promising ones. The alpha-beta algorithm (used by many OLD chess programs) comes immediately to mind.

The A* algorithm can give good results. The key to getting good results out of A* is choosing a good heuristic (weighting function) to evaluate the current node and the various successor nodes, to select the most promising path. Simple path length is probably not good enough.

Elaine Rich's AI textbook (oldie but goodie) spent a fair amount of time on various search algorithms. Full Disclosure: I was one of the guinea pigs for the text, during my undergraduate days at UT Austin.

Answer 4

If your problem is exactly as you describe it, you have two choices: depth-first search, and breadth first search.

Depth first search considers a possible path, pursues it all the way to the end (or as far as it is acceptable), and only then is it compared with other paths.

Breadth first search is probably more appropriate, at each junction you consider all possible next steps and use some score to rank the order in which each possible step is taken. This allows you to prioritise your search and find good solutions faster, (but to prove you have found the best solution it takes just as long as depth-first searching, and is less easy to parallelise).

However, your problem may also be suitable for Dijkstra's algorithm depending on the details of your problem. If it is, that is a much better approach!

This would also be a good starting point to develop your own algorithm that performs much better than iterative searching (if such an algorithm is actually possible, which it may not be!)

Answer 5

A* plus floodfill and dynamic programming. It is hard to implement, and too hard to describe in a simple post and too valuable to just give away so sorry I can't provide more but searching on flood fill and dynamic programming will put you on the path if you want to go that route.