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.

void	Inicializar (void) override
	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)

void	ResetParametros () override
	Redefinição. Ver TProcura::ResetParametros().

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 bool	Acao (const char *acao)
	Executa a ação (movimento, passo, jogada, lance, etc.) no estado atual.

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

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

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

int	Indicador (int id) override
	Redefinição. Ver TProcura::Indicador().

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) override
	Chapar antes da execu��o do algoritmo. Limpa valores estat�sticos, e fixa o instante limite de tempo para a execu��o.

void	ExecucaoTerminada (clock_t inicio) override
	Chamar ap�s a execu��o do algoritmo. Grava o tempo consumido.

int	LowerBound ()

void	NovaLinha (bool tudo=true)

Public Member Functions inherited from TProcura
	TProcura (void)

virtual	~TProcura (void)

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

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

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

virtual void	TesteEmpirico (TVector< int > instancias, bool mostrarSolucoes=true, char *ficheiro=NULL)
	Executa testes emp�ricos, em todas as configura��es guardadas, nas inst�ncias selecionadas.

virtual void	main (int argc, char argv[], const char nome)
	Inicializa a intera��o com o utilizador.

virtual TVector< int >	CodificarSolucao ()
	retorna um vetor de inteiros com a codifcia��o da solu��o (esta codifica��o ser� adicionada aos indicadores, no ficheiro CSV de resultados)

bool	TempoExcedido ()

bool	IteracoesExcedido ()

int	Parametro (int id)

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

Static Public Member Functions inherited from TProcura
static int	NovoValor (const char *prompt)

static char *	NovoTexto (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 TVector< TNo >	caminho
	Solução retornada pela procura (os estados devem ser libertados).

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 int	expansoes = 0
	Número de expansões efetuadas.

static int	geracoes = 0
	Número de estados gerados.

static TVector< unsigned char >	ramo

static int	espacosRamo = 2

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

static char	ficheiroInstancia [256] = "instancia_"
	nome do ficheiro de uma inst�ncia - editado pelo utilizador (utilizar como prefixo, concatenando com ID da inst�ncia) pode ser utilizado para gravar a inst�ncia num novo formato, colocando um indicador ativo que � chamado ap�s a execu��o (pode gravar a solu��o para ficheiro tamb�m, mas essa � mais facilmente gravada em CVS codificada em inteiros, onde fica associada � configura��o utilizada para a gerar)

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

static TVector< TIndicador >	indicador
	Indicadores que podem ser calculados ap�s a execu��o, quer com informa��o da inst�ncia, quer com resultado da �ltima corrida.

static TVector< int >	indAtivo

static TVector< TVector< int > >	configuracoes
	Conjuntos de configura��es para teste emp�rico.

static int	resultado = 0
	Resultado retornado pelo algoritmo na �ltima execu��o.

static int	tempo = 0
	tempo consumido na �ltima execu��o.

static int	iteracoes = 0
	N�mero total de itera��es realizadas na �ltima execu��o.

static clock_t	instanteFinal = 0
	Instante final (deadline) da corrida atual.

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

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	Explorar ()
	definir para explorar manualmente os dados (n�o definido em TProcura, apenas em TProcuraConstrutiva)

void	MostrarCaminho ()

unsigned int	Hash ()

void	LimparHT ()

bool	ExisteHT ()

virtual void	SubstituirHT (int indice)

Protected Member Functions inherited from TProcura
void	InserirRegisto (TVector< TResultado > &resultados, int inst, int conf)
	Insere um novo registo de resultados.

int	Registo (TResultado &resultado, int id)
	Procura um registo com determinado id.

void	Registo (TResultado &resultado, int id, int valor)
	Atualiza o valor de um registo.

void	MostraParametros (int detalhe=1, TVector< int > *idParametros=NULL)
	Mostra os par�metros atuais.

void	MostraIndicadores ()
	Mostra os indicadores definidos.

void	MostrarConfiguracoes (int detalhe, int atual=-1)
	Mostra as configura��es dispon�veis.

bool	EditarIndicadores ()
	Permite ao utilizador editar os indicadores a utilizar.

void	EditarParametros ()
	Permite ao utilizador editar os par�metros.

void	EditarConfiguracoes ()
	Permite ao utilizador editar as configura��es.

void	MostraRelatorio (TVector< TResultado > &resultados, bool ultimo=false)
	Mostra um relat�rio dos resultados.

void	ConfiguracaoAtual (TVector< int > &parametros, int operacao)
	Grava ou l� a configura��o atual.

int	NovaConfiguracao (TVector< int > &parametros)
	Adiciona uma nova configura��o se ainda n�o existir.

int	MelhorResultado (TResultado base, TResultado alternativa)
	Compara dois resultados para determinar o melhor.

void	CalculaTorneio (TVector< TResultado > &resultados)
	Calcula o torneio entre v�rias configura��es.

void	MostrarTorneio (TVector< TVector< int > > &torneio, bool jogo=false)
	Mostra os resultados do torneio.

void	BarraTorneio (bool nomes)
	Mostra a barra de progresso ou nomes do torneio.

TVector< TResultado >	ExtrairConfiguracao (TVector< TResultado > &resultados, int configuracao)
	Extrai resultados de uma determinada configura��o.

void	SolicitaInstancia ()
	Solicita ao utilizador o ID da inst�ncia a utilizar, permitindo alterar tamb�m o prefixo do ficheiro.

TVector< int >	SolicitaInstancias ()
	Solicita ao utilizador uma lista de inst�ncias.

void	RelatorioCSV (TVector< TResultado > &resultados, FILE *f)
	Gera um relat�rio CSV com os resultados.

TVector< int >	ExtraiLista (char *str)
	Extrai uma lista de inteiros a partir de uma string.

void	InserirConfiguracoes (char *str, TVector< int > &base)
	Insere configura��es a partir de uma string.

void	InserirConfiguracoes (TVector< int > &base, TVector< int > &produto, TVector< TVector< int > > &valores)
	Insere configura��es gerando o produto cartesiano de valores.

void	AjudaUtilizacao (const char *programa)
	Mostra ajuda de utiliza��o do programa.

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

Additional Inherited Members
Static Protected Member Functions inherited from TProcura
static int	Dominio (int &variavel, int min=INT_MIN, int max=INT_MAX)
	Limita o dom�nio de um par�metro inteiro.

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() — definidos em TProcura

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

Definition at line 113 of file TProcuraConstrutiva.h.

Constructor & Destructor Documentation

◆ TProcuraConstrutiva()

TProcuraConstrutiva::TProcuraConstrutiva ( void )

Definition at line 35 of file TProcuraConstrutiva.cpp.

◆ ~TProcuraConstrutiva()

virtual TProcuraConstrutiva::~TProcuraConstrutiva ( void )

inlinevirtual

Definition at line 117 of file TProcuraConstrutiva.h.

Member Function Documentation

◆ CalculaCaminho()

void TProcuraConstrutiva::CalculaCaminho ( bool completa = true )

protected

Definition at line 209 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 476 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 607 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 566 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 688 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 533 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 675 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ DebugPasso()

void TProcuraConstrutiva::DebugPasso ( void )

protected

Definition at line 631 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

◆ DebugRamo()

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

protected

Definition at line 558 of file TProcuraConstrutiva.cpp.

Here is the caller graph for this function:

◆ DebugSolucao()

void TProcuraConstrutiva::DebugSolucao ( bool continuar = false )

protected

Definition at line 589 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 643 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ExecucaoTerminada()

void TProcuraConstrutiva::ExecucaoTerminada ( clock_t inicio )

overridevirtual

Chamar ap�s a execu��o do algoritmo. Grava o tempo consumido.

Reimplemented from TProcura.

Definition at line 738 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

◆ ExisteHT()

bool TProcuraConstrutiva::ExisteHT ( )

protected

Definition at line 885 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Explorar()

void TProcuraConstrutiva::Explorar ( )

protectedvirtual

definir para explorar manualmente os dados (n�o definido em TProcura, apenas em TProcuraConstrutiva)

Reimplemented from TProcura.

Definition at line 749 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

◆ Hash()

unsigned int TProcuraConstrutiva::Hash ( )

protected

Definition at line 835 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 144 of file TProcuraConstrutiva.cpp.

Here is the caller graph for this function:

◆ LimparEstatisticas()

void TProcuraConstrutiva::LimparEstatisticas ( clock_t & inicio )

overridevirtual

Chapar antes da execu��o do algoritmo. Limpa valores estat�sticos, e fixa o instante limite de tempo para a execu��o.

Reimplemented from TProcura.

Definition at line 708 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 854 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 704 of file TProcuraConstrutiva.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ MostrarCaminho()

void TProcuraConstrutiva::MostrarCaminho ( )

protected

Definition at line 338 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 623 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ObjetivoAlcancado() [1/2]

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

protected

Definition at line 202 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 193 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

◆ SolucaoEncontrada()

int TProcuraConstrutiva::SolucaoEncontrada ( bool continuar = false )

protected

Definition at line 320 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 331 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 906 of file TProcuraConstrutiva.cpp.

Here is the caller graph for this function:

◆ VerificaLimites()

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

protected

Definition at line 229 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 748 of file TProcuraConstrutiva.h.

◆ custoHT

int TProcuraConstrutiva::custoHT

staticprotected

Definition at line 746 of file TProcuraConstrutiva.h.

◆ elementosHT

uint64_t TProcuraConstrutiva::elementosHT

staticprotected

Definition at line 745 of file TProcuraConstrutiva.h.

◆ estadoCodHT

uint64_t TProcuraConstrutiva::estadoCodHT

staticprotected

Definition at line 747 of file TProcuraConstrutiva.h.

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

Construtiva/TProcuraConstrutiva.h
Construtiva/TProcuraConstrutiva.cpp

Public Member Functions

Static Public Member Functions

Public Attributes

Static Public Attributes

Protected Member Functions

Static Protected Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ TProcuraConstrutiva()

◆ ~TProcuraConstrutiva()

Member Function Documentation

◆ CalculaCaminho()

◆ CalcularHeuristicas()

◆ DebugChamada()

◆ DebugCorte()

◆ DebugEstado()

◆ DebugExpansao()

◆ DebugIteracao()

◆ DebugPasso()

◆ DebugRamo()

◆ DebugSolucao()

◆ DebugSucessores()

◆ ExecucaoTerminada()

◆ ExisteHT()

◆ Explorar()

◆ Hash()

◆ LibertarVector()

◆ LimparEstatisticas()

◆ LimparHT()

◆ LowerBound()

◆ MostrarCaminho()

◆ NovaLinha()

◆ ObjetivoAlcancado() [1/2]

◆ ObjetivoAlcancado() [2/2]

◆ SolucaoEncontrada()

◆ SolucaoParcial()

◆ SubstituirHT()

◆ VerificaLimites()

Member Data Documentation

◆ colocadosHT

◆ custoHT

◆ elementosHT

◆ estadoCodHT