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.

int64_t	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 () 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 () 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 (bool completo=true)
	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, char *ficheiro=NULL)
	Executa testes emp�ricos, em todas as configura��es guardadas, nas inst�ncias selecionadas.

virtual void	TesteEmpiricoGestor (TVector< int > instancias, char *ficheiro=NULL)
	Teste emp�rico com modo mestre-escravo (este � o mestre)

virtual void	TesteEmpiricoTrabalhador (TVector< int > instancias, char *ficheiro=NULL)
	Teste emp�rico com modo mestre-escravo (este � o escravo)

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

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

bool	TempoExcedido ()

bool	IteracoesExcedido ()

int	Parametro (int id) const

int &	Parametro (int id)

bool	ParametroAtivo (int id, TVector< int > *valores=NULL) const

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)

static bool	Debug (ENivelDebug tipo, bool exato, const char *fmt,...)
	Mostra uma informa��o de debug, se o n�vel de debug for suficiente.

static char *	MostraTempo (double segundos)
	Mostra tempo num formato humano.

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

int	custo = 1
	Custo total acumulado desde o estado inicial.

int	heuristica = 0
	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 double	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.

static int	mpiID = 0
	MPI - rank do processo.

static int	mpiCount = 1
	MPI - n�mero de processos.

static int	modoMPI = 0
	Modo MPI.

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) const

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	ExecutaTarefa (TVector< TResultado > &resultados, int inst, int conf)
	Executa uma tarefa num teste emp�rico.

void	InserirRegisto (TVector< TResultado > &resultados, int inst, int conf)
	Insere um novo registo de resultados.

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

void	Registo (TResultado &resultado, int id, int64_t 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.

bool	RelatorioCSV (TVector< TResultado > &resultados, char *ficheiro)
	Gera um relat�rio CSV com os resultados.

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.

void	DebugTabela (ENivelDebug nivel, TVector< int >tabela, const char *tipo="")
	Mostra uma tabela de inteiros, 10 elementos por linha, apenas se o n�vel de debug for igual ou superior.

bool	JuntarCSV (const char *ficheiro)
	Juntar ficheiros CSV gerados por diferentes processos MPI em um �nico ficheiro.

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.

static void	InicializaMPI (int argc, char *argv[])
	Inicializa o ambiente MPI, se aplic�vel.

static void	FinalizaMPI ()
	Finaliza o ambiente MPI, se aplic�vel.

static double	Cronometro (enum ECronometro id=CONT_ALGORITMO, bool inicialiar=false)
	retorna o tempo em segundos desde que o cron�metro foi inicializado

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 111 of file TProcuraConstrutiva.h.

Constructor & Destructor Documentation

◆ TProcuraConstrutiva()

TProcuraConstrutiva::TProcuraConstrutiva ( void )

Definition at line 34 of file TProcuraConstrutiva.cpp.

◆ ~TProcuraConstrutiva()

virtual TProcuraConstrutiva::~TProcuraConstrutiva ( void )

inlinevirtual

Definition at line 115 of file TProcuraConstrutiva.h.

Member Function Documentation

◆ CalculaCaminho()

void TProcuraConstrutiva::CalculaCaminho ( bool completa = true )

protected

Definition at line 208 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 475 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 606 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 565 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`
	)		const

protected

Definition at line 682 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 532 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 674 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 630 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

◆ DebugRamo()

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

protected

Definition at line 557 of file TProcuraConstrutiva.cpp.

Here is the caller graph for this function:

◆ DebugSolucao()

void TProcuraConstrutiva::DebugSolucao ( bool continuar = false )

protected

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ExecucaoTerminada()

void TProcuraConstrutiva::ExecucaoTerminada ( )

overridevirtual

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

Reimplemented from TProcura.

Definition at line 732 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

◆ ExisteHT()

bool TProcuraConstrutiva::ExisteHT ( )

protected

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

Here is the call graph for this function:

◆ Hash()

unsigned int TProcuraConstrutiva::Hash ( )

protected

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

Here is the caller graph for this function:

◆ LimparEstatisticas()

void TProcuraConstrutiva::LimparEstatisticas ( )

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 702 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 848 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 702 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 337 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 622 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 201 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 192 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

◆ SolucaoEncontrada()

int TProcuraConstrutiva::SolucaoEncontrada ( bool continuar = false )

protected

Definition at line 319 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 330 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 900 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 228 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 746 of file TProcuraConstrutiva.h.

◆ custoHT

int TProcuraConstrutiva::custoHT

staticprotected

Definition at line 744 of file TProcuraConstrutiva.h.

◆ elementosHT

uint64_t TProcuraConstrutiva::elementosHT

staticprotected

Definition at line 743 of file TProcuraConstrutiva.h.

◆ estadoCodHT

uint64_t TProcuraConstrutiva::estadoCodHT

staticprotected

Definition at line 745 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