A* search extension

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.

Another way to do that (and simplify user code) is to extend the
'source' parameter notion from a single vertex to a set of vertices (in
order to initialize the open vertices list).

What do you think?

Regards,

  Guillaume

Hi Guillaume,

  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
variation you proposed finds the best paths from _all_ the available
sources, and you then just find the best among them and discard the
extra information obtained; thus it is certainly an overkill.

Another way to do that (and simplify user code) is to extend the
'source' parameter notion from a single vertex to a set of vertices (in
order to initialize the open vertices list).

You mean essentially to incorporate the "dummy vertex" approach into the
function itself?

Although it could be done, I usually avoid making functions more
complicated than necessary. The task of finding the best path from one
of many candidate sources can be easily solved (for all the search
algorithms) by including a dummy vertex like you did. If this is
implemented for astar, it should also, for completeness, be implemented
in the other search functions as well, since it would be equally useful
there. I'm just not sure if it is worthwhile to modify all these
functions to cover a special case which can be easily solved by the
user. Furthermore I do not like the idea of search functions modifying
the graph, without being explicit about it.

But I will keep this in mind. If I think of a nice way of implementing
this, I will do so. Of course, you may suggest an approach, or even
better, a patch! :slight_smile:

Cheers,
Tiago

Tiago,

I totally understand your reasons for choosing not to change the current
interface at this time being, and respect your decision.

Regards,

        Guillaume