TProcura
Biblioteca em C++ para testes paramétricos de algoritmos, e coleção de algoritmos de procura e otimização
Loading...
Searching...
No Matches
TProcuraConstrutiva Class Referenceabstract

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)
 
virtual bool Validar (TVector< TString > solucao)
 Verifica a validade de uma solução para a instância atual.
 
void ResetParametros () override
 Redefinição. Ver TProcura::ResetParametros().
 
virtual TString Acao (TNo sucessor)
 Retorna a ação (movimento, passo, jogada, lance, etc.) que gerou o sucessor.
 
virtual void Codifica (TBits &estado)
 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 (TString 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.
 
TVector< TStringSolucao ()
 retorna uma solução no formato do TResultado, para ser gravada em ficheiro de soluções, ou visualizada (pode ser utilizada para mostrar a solução, ou para gravar a solução num formato mais legível)
 
int ExecutaAlgoritmo ()
 Executa o algoritmo com os parâmetros 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
 Chamar 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 Gravar (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 (TString nome)
 Inicializa a interação com o utilizador.
 
virtual void TesteValidacao (TVector< int > instancias, TVector< int > impossiveis, TVector< int > referencias, TString fichSolucoes, TString fichResultados="")
 Executa testes de validação, executando cada solução na instância respetiva, e verificando a sua validade bem como características.
 
virtual void RelatorioValidacao (TVector< TResultado > resultados, TVector< int > referencias)
 
virtual void TesteEmpirico (TVector< int > instancias, TString ficheiro="")
 Executa testes empíricos, em todas as configurações guardadas, nas instâncias selecionadas.
 
virtual void TesteEmpiricoGestor (TVector< int > instancias, TString ficheiro="")
 Teste empírico com modo mestre-escravo (este é o mestre)
 
virtual void TesteEmpiricoTrabalhador (TVector< int > instancias, TString ficheiro="")
 Teste empírico com modo mestre-escravo (este é o escravo)
 
virtual void main (int argc, char *argv[], TString nome)
 Inicializa a interação com o utilizador.
 
virtual TVector< int64_tCodificarSolucao ()
 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
 
intParametro (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 (TString prompt)
 
static TString NovoTexto (TString 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 TString MostraTempo (double segundos)
 Mostra tempo num formato humano.
 
static void MostraCaixa (TVector< TString > titulo, ECaixaParte parte, TVector< int > largura, bool aberta=true, int identacao=0)
 
static void MostraCaixa (TString titulo, ECaixaParte parte, int largura=70, bool aberta=true, int identacao=0, const char *icon="")
 
static void MostraCaixa (TVector< TString > textos, int largura=70, bool aberta=true, int identacao=0)
 
static void Mensagem (TString titulo, const char *fmt,...)
 
static void MostraConjunto (TVector< int > valores, const char *etiqueta)
 
static void DebugHSL (float h=-1, float s=1.0, float l=0.2, bool fundo=true)
 Muda a cor (fundo/letra) com HSL.
 

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.
 
int debugID = 0
 ID do estado, para efeitos de debug.
 

Static Public Attributes

static TVector< TNocaminho
 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 expansoes = 0
 Número de expansões efetuadas.
 
static int geracoes = 0
 Número de estados gerados.
 
static int custoAcao = 0
 custo da última ação realizada (Acao(TString))
 
static TVector< const char * > ramo
 
static constexpr const charRAMO_ESTADO = " ├■"
 
static constexpr const charRAMO_ESTADO2 = " ├□"
 
static constexpr const charRAMO_ESTADO_FIM = " └■"
 
static constexpr const charRAMO_ESTADO2_FIM = " └□"
 
static constexpr const charRAMO_NOVO = " ├─"
 
static constexpr const charRAMO_FIM = " └─"
 
static constexpr const charRAMO_CONTINUA = " │ "
 
static constexpr const charRAMO_VAZIO = " "
 
- Static Public Attributes inherited from TProcura
static TParametro instancia = { "",1,1,1 }
 ID da instância atual, a ser utilizado em SolucaoVazia().
 
static TString ficheiroInstancia = ""
 prefixo do nome ficheiro de uma instância - editado pelo utilizador Caso não seja nulo, utilizar como prefixo, concatenando com ID da instância, para obter o ficheiro 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
 
static TString ficheiroGravar = ""
 prefixo do nome do ficheiro para gravar a instância para ficheiro (terá sido gerada)
 
static TVector< TParametroparametro
 Parâmetros a serem utilizados na configuração atual.
 
static TVector< TIndicadorindicador
 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< intindAtivo
 
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.
 
static int gravarSolucao = 0
 Gravar solução CSV (todas as ações)
 

Protected Member Functions

void DebugExpansao (int sucessor, int sucessores, bool minimizar=true)
 
void DebugCorte (int sucessores=-1, bool duplo=false)
 
void DebugSolucao (bool continuar=false)
 
void DebugChamada (bool noFolha)
 
void DebugPasso (CListaNo *lista=NULL)
 
void DebugSucessores (TVector< TNo > &sucessores)
 
void DebugIteracao (int iteracao, const char *simbolo)
 
void DebugEstado (bool novaLinha=true) const
 
void DebugRamo (const char *ramo, const char *folha)
 
void DebugFolha (bool fimLinha, const char *fmt,...)
 
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, int iAux=-1, TVector< int > *id=NULL)
 
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, TString titulo="")
 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< TResultadoExtrairConfiguracao (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< intSolicitaInstancias ()
 Solicita ao utilizador uma lista de instâncias.
 
bool RelatorioCSV (TVector< TResultado > &resultados, TString ficheiro, bool parametros=true)
 Gera um relatório CSV com os resultados.
 
void InserirConfiguracoes (TString 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 (TString programa)
 Mostra ajuda de utilização do programa.
 
void DebugTabela (ENivelDebug nivel, TVector< int >tabela, TString tipo="", TString prefixo="", int modoCor=0, bool duplaColuna=false)
 Mostra uma tabela de inteiros, 10 elementos por linha, apenas se o nível de debug for igual ou superior.
 
bool JuntarCSV (TString ficheiro)
 Juntar ficheiros CSV gerados por diferentes processos MPI em um único ficheiro.
 
void TesteInicio (TVector< int > &instancias, TVector< int > &configAtual)
 arranque de teste, auxiliar aos Testes Empíricos
 
void TesteFim ()
 

Static Protected Attributes

static TBits elementosHT [TAMANHO_HASHTABLE]
 
static int custoHT [TAMANHO_HASHTABLE]
 
static TBits estadoCodHT
 
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 inicializar=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:

Permite execução dos algoritmos:

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

Definition at line 110 of file TProcuraConstrutiva.h.

Constructor & Destructor Documentation

◆ TProcuraConstrutiva()

TProcuraConstrutiva::TProcuraConstrutiva ( void  )

Definition at line 31 of file TProcuraConstrutiva.cpp.

◆ ~TProcuraConstrutiva()

virtual TProcuraConstrutiva::~TProcuraConstrutiva ( void  )
inlinevirtual

Definition at line 114 of file TProcuraConstrutiva.h.

Member Function Documentation

◆ CalculaCaminho()

void TProcuraConstrutiva::CalculaCaminho ( bool  completa = true)
protected

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ DebugChamada()

void TProcuraConstrutiva::DebugChamada ( bool  noFolha)
protected

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

Here is the call graph for this function:
Here is the caller graph for this function:

◆ DebugEstado()

void TProcuraConstrutiva::DebugEstado ( bool  novaLinha = true) const
protected

Definition at line 797 of file TProcuraConstrutiva.cpp.

Here is the caller graph for this function:

◆ DebugExpansao()

void TProcuraConstrutiva::DebugExpansao ( int  sucessor,
int  sucessores,
bool  minimizar = true 
)
protected

Definition at line 633 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ DebugFolha()

void TProcuraConstrutiva::DebugFolha ( bool  fimLinha,
const char fmt,
  ... 
)
inlineprotected

Definition at line 744 of file TProcuraConstrutiva.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ DebugIteracao()

void TProcuraConstrutiva::DebugIteracao ( int  iteracao,
const char simbolo 
)
protected

Definition at line 790 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ DebugPasso()

void TProcuraConstrutiva::DebugPasso ( CListaNo lista = NULL)
protected

Definition at line 715 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

◆ DebugRamo()

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

Definition at line 641 of file TProcuraConstrutiva.cpp.

◆ DebugSolucao()

void TProcuraConstrutiva::DebugSolucao ( bool  continuar = false)
protected

Definition at line 665 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 747 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 861 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

◆ ExisteHT()

bool TProcuraConstrutiva::ExisteHT ( )
protected

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

Here is the call graph for this function:

◆ Hash()

unsigned int TProcuraConstrutiva::Hash ( )
protected

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

Here is the caller graph for this function:

◆ LimparEstatisticas()

void TProcuraConstrutiva::LimparEstatisticas ( )
overridevirtual

Chamar 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 824 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 967 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 716 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 398 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 707 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 238 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 229 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

◆ SolucaoEncontrada()

int TProcuraConstrutiva::SolucaoEncontrada ( bool  continuar = false)
protected

Definition at line 358 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,
int  iAux = -1,
TVector< int > *  id = NULL 
)
protected

Definition at line 370 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 1013 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 265 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 775 of file TProcuraConstrutiva.h.

◆ custoHT

int TProcuraConstrutiva::custoHT
staticprotected

Definition at line 773 of file TProcuraConstrutiva.h.

◆ elementosHT

TBits TProcuraConstrutiva::elementosHT
staticprotected

Definition at line 772 of file TProcuraConstrutiva.h.

◆ estadoCodHT

TBits TProcuraConstrutiva::estadoCodHT
staticprotected

Definition at line 774 of file TProcuraConstrutiva.h.


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