Re: A* search extension

Hi Guillaume,

On 04/21/2012 11:19 AM, Guillaume Lemaître wrote:
>   Hi Tiago,
> 
> In my opinion, the astar_search function contract could be extended to
> accept a set of source vertices instead of a single one, without any
> loss of generality.
> 
> In my particular need, I search the best path reaching a goal,
> considering various start points. The trivial way to do that is:
> 
> for each eligible start point:
>   run astar_search with this start point as 'source'
>   memorize best path if better than ever
> 
> But, the astar_search algorithm, particularly when associated to a
> AStarVisitor that build the graph locally to the examined vertices,
> tends to limit the combinatorial explosion of searching. So that
> iterating over eligible start points is necessarily sub-optimal.
>
> So, currently, I introduce a pseudo-vertex as the source point, which
> links to all my real eligible source points for no additional cost, and
> benefit from the automatic scope restriction from astar_search which may
> directly select the best start point by itself.

This seems to me to be the appropriate solution.

Note that the task being solved is to find the best path to the target
vertex from _either one_ of the available source vertices. The first