## Copyright (C) 2006 Bill Denney

##

## This file is part of Octave.

##

## Octave is free software; you can redistribute it and/or modify it

## under the terms of the GNU General Public License as published by

## the Free Software Foundation; either version 2, or (at your option)

## any later version.

##

## Octave is distributed in the hope that it will be useful, but

## WITHOUT ANY WARRANTY; without even the implied warranty of

## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

## General Public License for more details.

##

## You should have received a copy of the GNU General Public License

## along with Octave; see the file COPYING.  If not, write to the Free

## Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA

## 02110-1301, USA.



## -*- texinfo -*-

## @deftypefn {Function File} address@hidden = astar(@var{distfxn},

## @var{connfxn}, @var{startpaths}, @var{extra})

## This function performs an A* search to find the minimum path through

## a graph.

##

## See the script astar_example.m for an example of its use.

##

## @itemize @bullet

## @item

## distfcn -- This function handle should return three values (in this

## order):

##

## @itemize

## @item

## The actual distance of the current path.

##

## @item

## The estimated distance of the rest of the  path.  It MUST return 0

## when the final node is reached, and it MUST return less than or equal

## to the distance to the final node.  In the limit that it always

## returns 0, this will become Dijkstra's algorithm.

##

## @item

## 1 if the path is complete, 0 if it is not complete but the goal is

## potentially reachable, and -1 if it is not complete and the goal is

## not reachable.

## @end itemize

##

## @item

## connfcn -- Returns the connections from the end of the current path.

##

## @item

## startpaths -- The starting paths to take (a cell array, give only one

## point for the shortest distance problem, or give all points for the

## travelling salesman type problems).

##

## @item

## extra -- Any number of extra arguements to give to distfcn and

## connfcn.

## @end itemize

##

## @itemize @bullet

## @item

## bestpath -- The optimal path through the graph.  If the returned

## value is empty, then there is no possible path from the original

## path(s) to the goal.

## @end itemize

##

## The functions are called with the form

## @code{function(path, address@hidden:@})}

## @end deftypefn

##

## @seealso{samin}



## Author: Bill Denney



function [paths] = astar(distfxn, connfxn, paths, varargin)





%%%%%

%% Check input

%%%%%



if (~ isa(distfxn, "function handle"))

  error("astar: distfxn must be a function handle");

endif

if (~ isa(connfxn, "function handle"))

  error("astar: connfxn must be a function handle");

endif

if (~ iscell(paths))

  error("astar: paths must be a cell array");

endif



%%%%%

%% Do Stuff

%%%%%



% Setup all paths

for i = 1:length(paths)

    [tmp, pathdist(i), completed(i)] = distfxn(paths{i}, varargin{:});

    depths(i) = length(paths{i});

endfor



%% eliminate dead end paths

keepers = find(completed >= 0);

completed = completed(keepers);

pathdist = pathdist(keepers);

paths = paths(keepers);

depths = depths(keepers);



%% sort the remaining paths

[pathdist, idx] = sort(pathdist);

paths = paths(idx);

completed = completed(idx);

depths = depths(idx);



% finish immediately if the graph has been completed

solved = completed(1);

maxdepth = 0;

while (~ solved)

    curpath = paths{1};



    paths = paths(2:end);

    pathdist = pathdist(2:end);

    completed = completed(2:end);

    depths = depths(2:end);



    connections = connfxn(curpath, varargin{:});

    

    for i = 1:length(connections)

      paths{end+1} = [curpath connections(i)];

      [actdist, estdist, completed(end+1)] = distfxn(paths{end}, varargin{:});

      pathdist(end+1) =  estdist + actdist;

      depths(end+1) = length(paths{end});

    endfor



    %% eliminate dead end paths

    keepers = find(completed >= 0);

    completed = completed(keepers);

    pathdist = pathdist(keepers);

    paths = paths(keepers);

    depths = depths(keepers);

    %% verify that path choices still exist

    if isempty(paths)

      paths = [];

      return;

    endif

      



    %% sort the remaining paths

    [pathdist, idx] = sort(pathdist);

    paths = paths(idx);

    completed = completed(idx);

    if (completed(1) == 1)

      solved = 1;

    endif

endwhile



paths = paths{1};