gsearch.h

一个非常有用的开源代码

/*
	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"

// 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 GAction
{
protected:
	int m_nAction;
	GAction* m_pPrev;
	unsigned int m_nRefs;

	~GAction()
	{
		if(m_pPrev)
			m_pPrev->Release(); // todo: this could overflow the stack with recursion
	}
public:
	GAction(int nAction, GAction* pPrev)
	 : m_nAction(nAction), m_nRefs(0)
	{
		m_pPrev = pPrev;
		if(pPrev)
			pPrev->AddRef();
	}

	void AddRef()
	{
		m_nRefs++;
	}

	void Release()
	{
		if(--m_nRefs == 0)
			delete(this);
	}
};


class GActionPath
{
protected:
	double m_dError;
	double* m_pState;
	GAction* m_pLastAction;
	int m_nPathLen;

public:
	GActionPath(double* pState, int nStateSize) : m_dError(1e30), m_pLastAction(NULL), m_nPathLen(0)
	{
		m_pState = new double[nStateSize];
		memcpy(m_pState, pState, sizeof(double) * nStateSize);
	}

	~GActionPath()
	{
		if(m_pLastAction)
			m_pLastAction->Release();
		delete[] m_pState;
	}

	double GetError() { return m_dError; }
	double* AddAction(double dError, int nAction, double* pNewState);
};


// This tells the search algorithm how bad a particular vector in the search space is
class GActionPathCritic
{
protected:
	GPointerArray m_paths;
	int m_nActionCount;
	int m_nVectorSize;
	GActionPath* m_pBestPath;
	double m_dBestError;

public:
	// nVectorSize is the number of dimensions in the search space
	GActionPathCritic(double* pStartState, int nVectorSize, int nActionCount);

	virtual ~GActionPathCritic();

	// Computes the change in state caused by the given action
	virtual void DoAction(GActionPath* pPath, int nAction, double* pState) = 0;

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

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

	GActionPath* GetPath(int n) { return (GActionPath*)m_paths.GetPointer(n); }

	// Compute the error of the given action which results in the given state vector
	double CritiqueAction(GActionPath* pPath, int nAction, double* pNewState);

	// Returns the best path that was yet passed to the Critique method
	GActionPath* GetBestPath() { return m_pBestPath; }

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

protected:
	// Computes the error of the given path which ends in the given state vector
	virtual double ComputeError(GActionPath* pPath, int nAction, double* pNewState) = 0;
};



// This is the base class of all search algorithms that can
// only perform a discreet set of actions (as opposed to jumping
// to anywhere in the search space), and seek an optimal
// path of actions in order to minimize error.
class GActionPathSearch
{
protected:
	GActionPathCritic* m_pCritic;

public:
	GActionPathSearch(GActionPathCritic* pCritic)
	{
		m_pCritic = pCritic;
	}

	virtual ~GActionPathSearch() {}

	// 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;
};


#endif // __GSEARCH_H__