PathFind::IDAStar Class Reference

#include <idastar.h>

Inheritance diagram for PathFind::IDAStar:

[legend]Collaboration diagram for PathFind::IDAStar:

[legend]List of all members.

---

Detailed Description

IDA* search algorithm.

Short desciption of IDA*:

Each iteration is a depth-first search that keeps track of the cost f = g + h of each node generated. If a node is generated whose cost exceeds the threshold for that iteration, its path is cut off and the search backtracks. The cost threshold is initialized to the heuristic of the initial state and is increased in each iteration to the total cost of the lowest-cost node that was pruned during the previous iteration. The algorithm terminates when a goal state is reached whose total cost does not exceed the current threshold.

Statistics (see Search::createStatistics and Search::getStatistics):

• "aborted"
• "cpu_time"
• "path_cost"
• "path_length"
• "branching_factor"
• "nodes_expanded"
• "nodes_visited"
• "iterations"

Definition at line 43 of file idastar.h.

Public Types
enum	Caching { NO_CACHING, f_CACHING, F_CACHING }
	Caching strategy for f-values. More...
Public Member Functions
	IDAStar (Caching caching=NO_CACHING)
StatisticsCollection	createStatistics ()
	Create a StatisticsCollection.
bool	findPath (const Environment &env, int start, int target)
	Find a path.
const vector< int > &	getPath () const
const StatisticsCollection &	getStatistics () const
	Get statistics of last search.
const vector< char > &	getVisitedNodes () const
	Get a vector with char labels for each visited node.
long long int	getNodesLimit () const
void	setNodesLimit (long long int nodesLimit)
	Set nodes limit for search engine.
Public Attributes
long long int	m_nodesLimit
Private Member Functions
void	addCache (int nodeId, int f, int g, int iteration)
bool	checkCache (int nodeId, int f, int g, int iteration, int &f_min)
	Check in cache.
void	findPathIdaStar (int start)
void	markVisitedNode (int nodeId, int iteration)
bool	searchPathIdaStar (int iteration, int node, int lastNode, int depth, int g, int &f_min)
Private Attributes
bool	m_abortSearch
int	m_target
int	m_fLimit
Caching	m_caching
const Environment *	m_env
long long int	m_nodesExpanded
long long int	m_nodesVisited
vector< char >	m_visitedNodes
vector< CacheNode >	m_cache
vector< int >	m_path
vector< vector< Environment::Successor > >	m_successorStack
StatisticsCollection	m_statistics
Statistics &	m_branchingFactor

---

Member Enumeration Documentation

enum PathFind::IDAStar::Caching

Caching strategy for f-values. Enumeration values: NO_CACHING  No caching. f_CACHING  Local caching (f-caching). F_CACHING  Caching of backed up f-values (F-caching). Definition at line 48 of file idastar.h.

---

Constructor & Destructor Documentation

IDAStar::IDAStar (  Caching  caching = NO_CACHING  )

Definition at line 21 of file idastar.cpp.

---

Member Function Documentation

void PathFind::IDAStar::addCache (  int  nodeId, int  f, int  g, int  iteration )  [inline, private]

Definition at line 116 of file idastar.h. Referenced by searchPathIdaStar().

bool IDAStar::checkCache (  int  nodeId, int  f, int  g, int  iteration, int &  f_min )  [private]

Check in cache. Check in cache if node has be visited before via a shorter path. Definition at line 28 of file idastar.cpp. References F_CACHING, m_cache, m_caching, and m_fLimit. Referenced by searchPathIdaStar().

StatisticsCollection IDAStar::createStatistics (   )  [virtual]

Create a StatisticsCollection. Contains Statistics instances for all values tracked. Useful for keeping accumulated statistics by creating the collection and merging the statistics of a search as returned by getStatistics(). Implements PathFind::Search. Definition at line 54 of file idastar.cpp. References PathFind::StatisticsCollection::create().

bool IDAStar::findPath (  const Environment &  env, int  start, int  target )  [virtual]

Find a path. Returns: false, if search was aborted due to node limit. Implements PathFind::Search. Definition at line 68 of file idastar.cpp. References PathFind::Statistics::add(), PathFind::StatisticsCollection::clear(), findPathIdaStar(), PathFind::StatisticsCollection::get(), PathFind::Environment::isValidNodeId(), m_abortSearch, m_cache, m_caching, m_env, m_nodesExpanded, m_nodesVisited, m_path, m_statistics, m_target, m_visitedNodes, and NO_CACHING.

void IDAStar::findPathIdaStar (  int  start  )  [private]

Definition at line 98 of file idastar.cpp. References PathFind::Statistics::add(), PathFind::StatisticsCollection::get(), PathFind::Environment::getHeuristic(), PathFind::Environment::getMaxCost(), PathFind::Environment::getMinCost(), PathFind::Environment::getNumberNodes(), m_env, m_fLimit, m_path, m_statistics, m_successorStack, m_target, and searchPathIdaStar(). Referenced by findPath().

long long int PathFind::Search::getNodesLimit (   )  const [inline, inherited]

Definition at line 48 of file search.h. References PathFind::Search::m_nodesLimit.

const vector<int>& PathFind::IDAStar::getPath (   )  const [inline, virtual]

Implements PathFind::Search. Definition at line 65 of file idastar.h. References m_path.

const StatisticsCollection & IDAStar::getStatistics (   )  const [virtual]

Get statistics of last search. Implements PathFind::Search. Definition at line 125 of file idastar.cpp. References m_statistics.

const vector<char>& PathFind::IDAStar::getVisitedNodes (   )  const [inline, virtual]

Get a vector with char labels for each visited node. Space char means not visited, otherwise the char can have different values and meanings depending on the concrete search engine. Implements PathFind::Search. Definition at line 72 of file idastar.h. References m_visitedNodes.

void IDAStar::markVisitedNode (  int  nodeId, int  iteration )  [private]

Definition at line 130 of file idastar.cpp. References PathFind::getVisitedNodeLabel(), and m_visitedNodes. Referenced by searchPathIdaStar().

bool IDAStar::searchPathIdaStar (  int  iteration, int  node, int  lastNode, int  depth, int  g, int &  f_min )  [private]

Definition at line 137 of file idastar.cpp. References PathFind::Statistics::add(), addCache(), checkCache(), F_CACHING, PathFind::StatisticsCollection::get(), PathFind::Environment::getHeuristic(), PathFind::Environment::getSuccessors(), m_abortSearch, m_branchingFactor, m_cache, m_caching, PathFind::Environment::Successor::m_cost, m_env, m_fLimit, m_nodesExpanded, PathFind::Search::m_nodesLimit, m_nodesVisited, m_path, m_statistics, m_successorStack, PathFind::Environment::Successor::m_target, m_target, markVisitedNode(), and NO_CACHING. Referenced by findPathIdaStar().

void PathFind::Search::setNodesLimit (  long long int  nodesLimit  )  [inline, inherited]

Set nodes limit for search engine. The default is -1 and means unlimited search. The nodes limit is a hint only, the search engine may ignore it. Reimplemented in PathFind::AStar< MARKER, CLOSED >. Definition at line 71 of file search.h. References PathFind::Search::m_nodesLimit.

---

Member Data Documentation

bool PathFind::IDAStar::m_abortSearch [private]

Definition at line 90 of file idastar.h. Referenced by findPath(), and searchPathIdaStar().

Statistics& PathFind::IDAStar::m_branchingFactor [private]

Definition at line 114 of file idastar.h. Referenced by searchPathIdaStar().

vector<CacheNode> PathFind::IDAStar::m_cache [private]

Definition at line 106 of file idastar.h. Referenced by checkCache(), findPath(), and searchPathIdaStar().

Caching PathFind::IDAStar::m_caching [private]

Definition at line 96 of file idastar.h. Referenced by checkCache(), findPath(), and searchPathIdaStar().

const Environment* PathFind::IDAStar::m_env [private]

Definition at line 98 of file idastar.h. Referenced by findPath(), findPathIdaStar(), and searchPathIdaStar().

int PathFind::IDAStar::m_fLimit [private]

Definition at line 94 of file idastar.h. Referenced by checkCache(), findPathIdaStar(), and searchPathIdaStar().

long long int PathFind::IDAStar::m_nodesExpanded [private]

Definition at line 100 of file idastar.h. Referenced by findPath(), and searchPathIdaStar().

long long int PathFind::Search::m_nodesLimit [inherited]

Definition at line 78 of file search.h. Referenced by PathFind::Search::getNodesLimit(), PathFind::Search::Search(), searchPathIdaStar(), PathFind::Search::setNodesLimit(), and PathFind::AStar< MARKER, CLOSED >::setNodesLimit().

long long int PathFind::IDAStar::m_nodesVisited [private]

Definition at line 102 of file idastar.h. Referenced by findPath(), and searchPathIdaStar().

vector<int> PathFind::IDAStar::m_path [private]

Definition at line 108 of file idastar.h. Referenced by findPath(), findPathIdaStar(), getPath(), and searchPathIdaStar().

StatisticsCollection PathFind::IDAStar::m_statistics [private]

Definition at line 112 of file idastar.h. Referenced by findPath(), findPathIdaStar(), getStatistics(), and searchPathIdaStar().

vector<vector<Environment::Successor> > PathFind::IDAStar::m_successorStack [private]

Definition at line 110 of file idastar.h. Referenced by findPathIdaStar(), and searchPathIdaStar().

int PathFind::IDAStar::m_target [private]

Definition at line 92 of file idastar.h. Referenced by findPath(), findPathIdaStar(), and searchPathIdaStar().

vector<char> PathFind::IDAStar::m_visitedNodes [private]

Definition at line 104 of file idastar.h. Referenced by findPath(), getVisitedNodes(), and markVisitedNode().

---

The documentation for this class was generated from the following files:

• idastar.h
• idastar.cpp

---