Representa um estado no espaço de estados. More...

#include <TProcuraConstrutiva.h>

Inheritance diagram for TProcuraConstrutiva:

Collaboration diagram for TProcuraConstrutiva:

Public Member Functions
	TProcuraConstrutiva (void)

virtual	~TProcuraConstrutiva (void)

virtual TNo	Duplicar (void)=0
	Cria um objecto que é uma cópia deste.

virtual void	Copiar (TNo objecto)
	Fica com uma cópia do objecto.

virtual void	SolucaoVazia (void)
	Coloca o objecto no estado inicial da procura.

virtual void	Sucessores (TVector< TNo > &sucessores)
	Coloca em sucessores a lista de estados sucessores.

virtual bool	SolucaoCompleta (void)
	Verifica se o estado actual é objectivo (é uma solução completa)

virtual void	TesteManual (const char *nome)
	Inicializa a interação com o utilizador.

virtual const char *	Acao (TNo sucessor)
	Retorna a ação (movimento, passo, jogada, lance, etc.) que gerou o sucessor.

virtual void	Codifica (uint64_t estado[OBJETO_HASHTABLE])
	Codifica o estado para um vetor de inteiros de 64 bits.

virtual int	Heuristica (void)
	Função para calcular quanto falta para o final, o valor da heurística.

virtual void	Debug (void)
	Mostra o estado no ecrã, para debug.

virtual void	ResetParametros ()
	Inicializa os parametros.

virtual bool	Acao (const char *acao)
	Executa a ação (movimento, passo, jogada, lance, etc.) no estado atual.

virtual bool	Parar (void)
	Verifica se a procura deve ser interrompida.

virtual bool	Distinto (TNo estado)
	Verifica se o estado actual distinto do fornecido.

virtual void	MostrarSolucao (void)
	Mostrar solução, seja um caminho ou o próprio estado.

virtual int	ExecutaAlgoritmo ()
	Executa o algoritmo com os parametros atuais.

virtual void	TesteEmpirico (int inicio=-1, int fim=-1, bool mostrarSolucoes=true)
	Executa testes empíricos, em todas as configurações guardadas, nas instâncias selecionadas.

int	LarguraPrimeiro (int limite=0)
	Executa a procura em largura primeiro, algoritmo cego.

int	CustoUniforme (int limite=0)
	Executa a procura por custo uniforme, algoritmo cego.

int	ProfundidadePrimeiro (int nivel=0)
	Executa a procura em profundidade primeiro, algoritmo cego.

int	MelhorPrimeiro (int nivel=0)
	Executa a procura melhor primeiro, algoritmo informado.

int	AStar (int limite=0)
	Executa a procura A*, algoritmo informado.

int	IDAStar (int upperBound=0)
	Executa a procura IDA*, algoritmo informado.

int	BranchAndBound (int upperBound=0)
	Executa o algoritmo Branch-and-Bound, um algoritmo informado.

void	LimparEstatisticas (clock_t &inicio)

void	FinalizarCorrida (clock_t inicio)

int	LowerBound ()

void	NovaLinha (bool tudo=true)

Static Public Member Functions
static void	LibertarVector (TVector< TNo > &vector, int excepto=-1, int maiorQue=-1)

static int	NovoValor (const char *prompt)

Public Attributes
TNo	pai
	Ponteiro para o estado pai, na árvore de procura.

int	custo
	Custo total acumulado desde o estado inicial.

int	heuristica
	Estimativa para o custo até um estado objetivo, se disponível.

Static Public Attributes
static TParametro	instancia = { NULL,1,1,1, NULL, NULL }
	ID da instância atual, a ser utilizado em SolucaoVazia().

static TVector< TParametro >	parametro
	Parâmetros a serem utilizados na configuração atual.

static TVector< TVector< int > >	configuracoes
	Conjuntos de configurações para teste empírico.

static int	geracoes = 0
	Número total de gerações realizadas na procura.

static int	expansoes =0
	Número total de expansões realizadas na procura.

static int	avaliacoes =0
	Número total de avaliações realizadas na procura.

static TVector< TNo >	caminho
	Solução retornada pela procura (os estados devem ser libertados).

static bool	memoriaEsgotada = false
	Flag indicando problemas de memória esgotada.

static TNo	solucao =NULL
	Estado objetivo encontrado, retornado pela procura (deve ser libertado).

static int	lowerBound = 0
	Valor mínimo que a solução pode apresentar, obtido pela procura.

static int	tamanhoCodificado = OBJETO_HASHTABLE
	Número de inteiros de 64 bits utilizados para codificar um objeto (≤ OBJETO_HASHTABLE).

static TVector< unsigned char >	ramo

static int	espacosRamo =2

static clock_t	instanteFinal = 0

Protected Member Functions
void	DebugExpansao (int sucessor, int sucessores, bool duplo=false)

void	DebugCorte (int sucessores=-1, bool duplo=false)

void	DebugSolucao (bool continuar=false)

void	DebugChamada (void)

void	DebugPasso (void)

void	DebugSucessores (TVector< TNo > &sucessores)

void	DebugIteracao (int iteracao)

void	DebugEstado (int id=-1, int pai=-1)

void	DebugRamo (char ramo, char folha)

int	ObjetivoAlcancado (int item, TVector< TNo > &lista)

int	ObjetivoAlcancado (TNo estado, bool completa=true)

int	SolucaoEncontrada (bool continuar=false)

void	CalculaCaminho (bool completa=true)

void	VerificaLimites (int limite, int porProcessar, TVector< TNo > &sucessores)

void	CalcularHeuristicas (TVector< TNo > &sucessores, TVector< int > *id=NULL, bool sortLB=false)

int	SolucaoParcial (int i, TVector< TNo > &sucessores)

void	ExplorarSucessores (bool jogo=false)

void	EditarParametros ()

void	EditarConfiguracoes ()

void	MostrarConfiguracoes (int detalhe, int atual=-1)

void	SolicitaInstancia ()

bool	TempoExcedido ()

bool	GeracoesExcedido ()

bool	ExpansoesExcedido ()

bool	AvaliacoesExcedido ()

void	MostrarCaminho ()

void	MostraParametros (int detalhe=1, TVector< int > *idParametros=NULL)

void	MostraRelatorio (TVector< TResultado > &resultados)

int	Dominio (int &variavel, int min=INT_MIN, int max=INT_MAX)

void	ConfiguracaoAtual (TVector< int > &parametros, int operacao)

int	MelhorResultado (TResultado base, TResultado alternativa)

void	CalculaTorneio (TVector< TResultado > &resultados)

void	MostrarTorneio (TVector< TVector< int > > &torneio, bool jogo=false)

void	BarraTorneio (bool nomes)

void	ExtrairConfiguracao (TVector< TResultado > &resultados, TVector< TResultado > &extracao, int configuracao)

unsigned int	Hash ()

void	LimparHT ()

bool	ExisteHT ()

virtual void	SubstituirHT (int indice)

Static Protected Attributes
static uint64_t	elementosHT [TAMANHO_HASHTABLE][OBJETO_HASHTABLE]

static int	custoHT [TAMANHO_HASHTABLE]

static uint64_t	estadoCodHT [OBJETO_HASHTABLE]

static int	colocadosHT = 0

Detailed Description

Representa um estado no espaço de estados.

Esta classe base deve ser redefinida com um problema concreto, permitindo a execução de procuras construtivas.

Para utilizar a classe, é necessário:

Redefinir os métodos de duplicação e cópia de estados (Duplicar() e Copiar()).
Implementar funções essenciais de procura: SolucaoVazia(), SolucaoCompleta(), Sucessores() e Debug().

Permite execução dos algoritmos:

Cegos: LarguraPrimeiro(), CustoUniforme(), ProfundidadePrimeiro()
Informados: MelhorPrimeiro(), AStar(), IDAStar(), BranchAndBound()
Testes e avaliação: TesteManual(), TesteEmpirico()

Observação: Alguns métodos e parâmetros terão efeito apenas se determinados métodos forem redefinidos na subclasse.

Definition at line 192 of file TProcuraConstrutiva.h.

Constructor & Destructor Documentation

◆ TProcuraConstrutiva()

TProcuraConstrutiva::TProcuraConstrutiva ( void )

Definition at line 47 of file TProcuraConstrutiva.cpp.

◆ ~TProcuraConstrutiva()

virtual TProcuraConstrutiva::~TProcuraConstrutiva ( void )

inlinevirtual

Definition at line 196 of file TProcuraConstrutiva.h.

Member Function Documentation

◆ AvaliacoesExcedido()

bool TProcuraConstrutiva::AvaliacoesExcedido ( )

inlineprotected

Definition at line 991 of file TProcuraConstrutiva.h.

Here is the caller graph for this function:

◆ BarraTorneio()

void TProcuraConstrutiva::BarraTorneio ( bool nomes )

protected

Definition at line 1128 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ CalculaCaminho()

void TProcuraConstrutiva::CalculaCaminho ( bool completa = true )

protected

Definition at line 233 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ CalcularHeuristicas()

void TProcuraConstrutiva::CalcularHeuristicas	(	TVector< TNo > &	sucessores,
		TVector< int > *	id = `NULL`,
		bool	sortLB = `false`
	)

protected

Definition at line 500 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ CalculaTorneio()

void TProcuraConstrutiva::CalculaTorneio ( TVector< TResultado > & resultados )

protected

Definition at line 1067 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ConfiguracaoAtual()

void TProcuraConstrutiva::ConfiguracaoAtual	(	TVector< int > &	parametros,
		int	operacao
	)

protected

Definition at line 865 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ DebugChamada()

void TProcuraConstrutiva::DebugChamada ( void )

protected

Definition at line 637 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ DebugCorte()

void TProcuraConstrutiva::DebugCorte	(	int	sucessores = `-1`,
		bool	duplo = `false`
	)

protected

Definition at line 598 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ DebugEstado()

void TProcuraConstrutiva::DebugEstado	(	int	id = `-1`,
		int	pai = `-1`
	)

protected

Definition at line 718 of file TProcuraConstrutiva.cpp.

Here is the caller graph for this function:

◆ DebugExpansao()

void TProcuraConstrutiva::DebugExpansao	(	int	sucessor,
		int	sucessores,
		bool	duplo = `false`
	)

protected

Definition at line 565 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ DebugIteracao()

void TProcuraConstrutiva::DebugIteracao ( int iteracao )

protected

Definition at line 705 of file TProcuraConstrutiva.cpp.

Here is the caller graph for this function:

◆ DebugPasso()

void TProcuraConstrutiva::DebugPasso ( void )

protected

Definition at line 661 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ DebugRamo()

void TProcuraConstrutiva::DebugRamo	(	char	ramo,
		char	folha
	)

protected

Definition at line 590 of file TProcuraConstrutiva.cpp.

Here is the caller graph for this function:

◆ DebugSolucao()

void TProcuraConstrutiva::DebugSolucao ( bool continuar = false )

protected

Definition at line 620 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ DebugSucessores()

void TProcuraConstrutiva::DebugSucessores ( TVector< TNo > & sucessores )

protected

Definition at line 673 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Dominio()

int TProcuraConstrutiva::Dominio	(	int &	variavel,
		int	min = `INT_MIN`,
		int	max = `INT_MAX`
	)

protected

Definition at line 1376 of file TProcuraConstrutiva.cpp.

Here is the caller graph for this function:

◆ EditarConfiguracoes()

void TProcuraConstrutiva::EditarConfiguracoes ( )

protected

Definition at line 878 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ EditarParametros()

void TProcuraConstrutiva::EditarParametros ( )

protected

Definition at line 833 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ExisteHT()

bool TProcuraConstrutiva::ExisteHT ( )

protected

Definition at line 1338 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ExpansoesExcedido()

bool TProcuraConstrutiva::ExpansoesExcedido ( )

inlineprotected

Definition at line 988 of file TProcuraConstrutiva.h.

Here is the caller graph for this function:

◆ ExplorarSucessores()

void TProcuraConstrutiva::ExplorarSucessores ( bool jogo = false )

protected

Definition at line 1194 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ExtrairConfiguracao()

void TProcuraConstrutiva::ExtrairConfiguracao	(	TVector< TResultado > &	resultados,
		TVector< TResultado > &	extracao,
		int	configuracao
	)

protected

Definition at line 1119 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ FinalizarCorrida()

void TProcuraConstrutiva::FinalizarCorrida ( clock_t inicio )

Definition at line 1155 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ GeracoesExcedido()

bool TProcuraConstrutiva::GeracoesExcedido ( )

inlineprotected

Definition at line 985 of file TProcuraConstrutiva.h.

Here is the caller graph for this function:

◆ Hash()

unsigned int TProcuraConstrutiva::Hash ( )

protected

Definition at line 1289 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ LibertarVector()

void TProcuraConstrutiva::LibertarVector	(	TVector< TNo > &	vector,
		int	excepto = `-1`,
		int	maiorQue = `-1`
	)

static

Definition at line 168 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ LimparEstatisticas()

void TProcuraConstrutiva::LimparEstatisticas ( clock_t & inicio )

Definition at line 739 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ LimparHT()

void TProcuraConstrutiva::LimparHT ( )

protected

Definition at line 1308 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ LowerBound()

int TProcuraConstrutiva::LowerBound ( )

inline

Definition at line 940 of file TProcuraConstrutiva.h.

Here is the caller graph for this function:

◆ MelhorResultado()

int TProcuraConstrutiva::MelhorResultado	(	TResultado	base,
		TResultado	alternativa
	)

protected

Definition at line 1139 of file TProcuraConstrutiva.cpp.

Here is the caller graph for this function:

◆ MostraParametros()

void TProcuraConstrutiva::MostraParametros	(	int	detalhe = `1`,
		TVector< int > *	idParametros = `NULL`
	)

protected

Definition at line 803 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ MostrarCaminho()

void TProcuraConstrutiva::MostrarCaminho ( )

protected

Definition at line 362 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ MostrarConfiguracoes()

void TProcuraConstrutiva::MostrarConfiguracoes	(	int	detalhe,
		int	atual = `-1`
	)

protected

Definition at line 909 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ MostraRelatorio()

void TProcuraConstrutiva::MostraRelatorio ( TVector< TResultado > & resultados )

protected

Definition at line 1019 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ MostrarTorneio()

void TProcuraConstrutiva::MostrarTorneio	(	TVector< TVector< int > > &	torneio,
		bool	jogo = `false`
	)

protected

Definition at line 1089 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ NovaLinha()

void TProcuraConstrutiva::NovaLinha ( bool tudo = true )

Definition at line 653 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ NovoValor()

int TProcuraConstrutiva::NovoValor ( const char * prompt )

static

Definition at line 1169 of file TProcuraConstrutiva.cpp.

Here is the caller graph for this function:

◆ ObjetivoAlcancado() [1/2]

int TProcuraConstrutiva::ObjetivoAlcancado	(	int	item,
		TVector< TNo > &	lista
	)

protected

Definition at line 226 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ObjetivoAlcancado() [2/2]

int TProcuraConstrutiva::ObjetivoAlcancado	(	TNo	estado,
		bool	completa = `true`
	)

protected

Definition at line 217 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

◆ SolicitaInstancia()

void TProcuraConstrutiva::SolicitaInstancia ( )

protected

Definition at line 1178 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ SolucaoEncontrada()

int TProcuraConstrutiva::SolucaoEncontrada ( bool continuar = false )

protected

Definition at line 344 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ SolucaoParcial()

int TProcuraConstrutiva::SolucaoParcial	(	int	i,
		TVector< TNo > &	sucessores
	)

protected

Definition at line 355 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ SubstituirHT()

void TProcuraConstrutiva::SubstituirHT ( int indice )

protectedvirtual

Reimplemented in TProcuraAdversa.

Definition at line 1359 of file TProcuraConstrutiva.cpp.

Here is the caller graph for this function:

◆ TempoExcedido()

bool TProcuraConstrutiva::TempoExcedido ( )

inlineprotected

Definition at line 984 of file TProcuraConstrutiva.h.

Here is the caller graph for this function:

◆ VerificaLimites()

void TProcuraConstrutiva::VerificaLimites	(	int	limite,
		int	porProcessar,
		TVector< TNo > &	sucessores
	)

protected

Definition at line 253 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

◆ colocadosHT

int TProcuraConstrutiva::colocadosHT = 0

staticprotected

Definition at line 1009 of file TProcuraConstrutiva.h.

◆ custoHT

int TProcuraConstrutiva::custoHT

staticprotected

Definition at line 1007 of file TProcuraConstrutiva.h.

◆ elementosHT

uint64_t TProcuraConstrutiva::elementosHT

staticprotected

Definition at line 1006 of file TProcuraConstrutiva.h.

◆ estadoCodHT

uint64_t TProcuraConstrutiva::estadoCodHT

staticprotected

Definition at line 1008 of file TProcuraConstrutiva.h.

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

TProcuraConstrutiva/TProcuraConstrutiva.h
TProcuraConstrutiva/TProcuraConstrutiva.cpp

Public Member Functions

Static Public Member Functions

Public Attributes

Static Public Attributes

Protected Member Functions

Static Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ TProcuraConstrutiva()

◆ ~TProcuraConstrutiva()

Member Function Documentation

◆ AvaliacoesExcedido()

◆ BarraTorneio()

◆ CalculaCaminho()

◆ CalcularHeuristicas()

◆ CalculaTorneio()

◆ ConfiguracaoAtual()

◆ DebugChamada()

◆ DebugCorte()

◆ DebugEstado()

◆ DebugExpansao()

◆ DebugIteracao()

◆ DebugPasso()

◆ DebugRamo()

◆ DebugSolucao()

◆ DebugSucessores()

◆ Dominio()

◆ EditarConfiguracoes()

◆ EditarParametros()

◆ ExisteHT()

◆ ExpansoesExcedido()

◆ ExplorarSucessores()

◆ ExtrairConfiguracao()

◆ FinalizarCorrida()

◆ GeracoesExcedido()

◆ Hash()

◆ LibertarVector()

◆ LimparEstatisticas()

◆ LimparHT()

◆ LowerBound()

◆ MelhorResultado()

◆ MostraParametros()

◆ MostrarCaminho()

◆ MostrarConfiguracoes()

◆ MostraRelatorio()

◆ MostrarTorneio()

◆ NovaLinha()

◆ NovoValor()

◆ ObjetivoAlcancado() [1/2]

◆ ObjetivoAlcancado() [2/2]

◆ SolicitaInstancia()

◆ SolucaoEncontrada()

◆ SolucaoParcial()

◆ SubstituirHT()

◆ TempoExcedido()

◆ VerificaLimites()

Member Data Documentation

◆ colocadosHT

◆ custoHT

◆ elementosHT

◆ estadoCodHT