gsearch.h

来自「一个由Mike Gashler完成的机器学习方面的includes neural」· C头文件 代码 · 共 181 行

/*
	Copyright (C) 2006, Mike Gashler

	This library is free software; you can redistribute it and/or
	modify it under the terms of the GNU Lesser General Public
	License as published by the Free Software Foundation; either
	version 2.1 of the License, or (at your option) any later version.

	see http://www.gnu.org/copyleft/lesser.html
*/

#ifndef __GSEARCH_H__
#define __GSEARCH_H__

#include "GArray.h"

class GActionPath;
class GAction;


// This tells the search algorithm how bad a particular vector in the search space is
class GRealVectorCritic
{
protected:
	int m_nVectorSize;
	double m_dBestError;
	double* m_pBestYet;

public:
	// nVectorSize is the number of dimensions in the search space
	GRealVectorCritic(int nVectorSize);

	virtual ~GRealVectorCritic();

	// Compute the error of the given vector
	double Critique(double* pVector);

	// Returns the best vector that was ever passed to the Critique method
	double* GetBestYet() { return m_pBestYet; }

	// Returns the error computed for the best vector ever passed
	// to the Critique method
	double GetBestError() { return m_dBestError; }

	// Returns the dimensionality of the vector
	int GetVectorSize() { return m_nVectorSize; }

protected:
	// Computes the error of the given vector with respect to the search space
	virtual double ComputeError(double* pVector) = 0;
};



// This is the base class of all search algorithms
// that can jump to any vector in the search space and
// seek the vector that minimizes error. The GRealVectorCritic
// will keep track of the best vector yet found, so ask it when
// you want the results.
class GRealVectorSearch
{
protected:
	GRealVectorCritic* m_pCritic;

public:
	GRealVectorSearch(GRealVectorCritic* pCritic);
	virtual ~GRealVectorSearch();

	// Call this method in a loop to perform the search. There
	// is no built-in stopping criteria. In other words, these
	// search algorithms will keep searching for better vectors
	// forever if you let them, so you need to use the critic
	// to determine when to stop yourself.
	virtual void Iterate() = 0;
};




class GActionPathState
{
friend class GActionPath;
public:
	GActionPathState() {}
	virtual ~GActionPathState() {}

protected:
	// Performs the specified action on the state. (so pState holds
	// both input and output data.) This method is protected because
	// you should call GActionPath::DoAction, and it will call this method.
	virtual void PerformAction(int nAction) = 0;

	// Creates a deep copy of this state object
	virtual GActionPathState* Copy() = 0;

protected:
	// Evaluate the error of the given path. Many search algorithms
	// (like GAStarSearch) rely heavily on the heuristic to make the search effective.
	// For example, if you don't penalize redundant paths to the same state, the search
	// space becomes exponential and therefore impossible to search. So a good critic
	// must keep track of which states have already been visited, severely penalize longer
	// paths to a state that has already been visited by a shorter path, and will carefully
	// balance between path length and distance from the goal in producing the error value.
	virtual double CritiquePath(int nPathLen, GAction* pLastAction) = 0;
};




class GActionPath
{
protected:
	GActionPathState* m_pHeadState;
	GAction* m_pLastAction;
	int m_nPathLen;

public:
	// Takes ownership of pState
	GActionPath(GActionPathState* pState);
	~GActionPath();

	// Makes a copy of this path
	GActionPath* Fork();

	// Returns the number of actions in the path
	int GetLength() { return m_nPathLen; }

	// Gets the first nCount actions of the specified path
	void GetPath(int nCount, int* pOutBuf);

	// Returns the head-state of the path
	GActionPathState* GetState() { return m_pHeadState; }

	// Adds the specified action to the path and modifies the head state accordingly
	void DoAction(int nAction);

	// Computes the error of this path
	double Critique();
};




// This is the base class of search algorithms that can
// only perform a discreet set of actions (as opposed to jumping
// to anywhere in the search space), and seeks to minimize the
// error of a path of actions
class GActionPathSearch
{
protected:
	int m_nActionCount;

public:
	// Takes ownership of pStartState
	GActionPathSearch(GActionPathState* pStartState, int nActionCount)
	{
		GAssert(nActionCount > 1, "not enough actions for a meaningful search");
		m_nActionCount = nActionCount;
	}

	virtual ~GActionPathSearch()
	{
	}

	// Returns the number of possible actions
	inline int GetActionCount() { return m_nActionCount; }

	// Call this in a loop to do the searching. If it returns
	// true, then it's done so don't call it anymore.
	virtual bool Iterate() = 0;

	// Returns the best known path so far
	virtual GActionPath* GetBestPath() = 0;

	// Returns the error of the best known path
	virtual double GetBestPathError() = 0;
};


#endif // __GSEARCH_H__