TProcura
Biblioteca em C++ para testes paramétricos de algoritmos, e coleção de algoritmos de procura e otimização
|
#include <TCodificacaoPermutacao.h>
Public Member Functions | |
TCodificacaoPermutacao () | |
~TCodificacaoPermutacao () | |
int | Avaliar (void)=0 |
TPonto | Duplicar (void)=0 |
Cria um objecto que é uma cópia deste. | |
void | Inicializar (void)=0 |
Coloca o objecto no estado inicial da procura. | |
void | Debug (bool completo=true) override |
Mostra o estado no ecrã, para debug. | |
void | Copiar (TPonto objecto) |
Fica com uma cópia do objecto. | |
void | NovaSolucao (void) |
bool | Acao (const char *acao) |
void | ResetParametros () |
Inicializa os parametros, indicadores e instâncias. | |
void | Vizinhanca (TVector< TPonto > &vizinhos) |
void | Mutar (void) |
void | Cruzamento (TPonto a, TPonto b) |
int | Distancia (TPonto a) |
virtual void | Debug (bool completo=true) |
Mostra o estado no ecrã, para debug. | |
![]() | |
TProcuraMelhorativa (void) | |
~TProcuraMelhorativa (void) | |
bool | Acao (const char *acao) |
void | ResetParametros () override |
Inicializa os parametros, indicadores e instâncias. | |
bool | Parar (void) |
Verifica se a procura deve ser interrompida. | |
int | EscaladaDoMonte () |
int | AlgoritmoGenetico () |
int | AlgoritmoEvolutivo () |
void | DebugMelhorEncontrado (TPonto ponto) |
int64_t | Indicador (int id) override |
Redefinição. Ver TProcura::Indicador(). | |
void | Inicializar (void) |
Inicializar a instância. No final, chamar NovaSolucao() para inicializar o estado. | |
void | LimparEstatisticas () |
Chapar antes da execução do algoritmo. Limpa valores estatísticos, e fixa o instante limite de tempo para a execução. | |
![]() | |
TProcura (void) | |
virtual | ~TProcura (void) |
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 void | ExecucaoTerminada () |
Chamar após a execução do algoritmo. Grava o tempo consumido. | |
virtual void | MostrarSolucao () |
definir para visualizar a solução | |
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 bool | Debug (ENivelDebug tipo, bool exato, const char *fmt,...) |
Mostra uma informação de debug, se o nível de debug for suficiente. | |
![]() | |
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 | |
TVector< int > | estado |
![]() | |
int | custo = -1 |
Custo total, atualizada após Avaliar() | |
Static Public Attributes | |
static int | nElementos = 0 |
![]() | |
static int | lowerBound = 0 |
Lower Bound, se existir. | |
static int | geracoes = 0 |
Número de estados gerados. | |
static int | epocas = 0 |
Número de épocas decorridas num algoritmo evolutivo. Uma época é uma geração única. | |
![]() | |
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. | |
Additional Inherited Members | |
![]() | |
void | Selecao (int &pai, int &mae, TVector< int > &pesos, int total) |
void | OrdemValor (TVector< TPonto > &populacao, TVector< int > &id) |
void | CalcularAvaliacoes (TVector< TPonto > &vizinhos, int &melhorValor, int &melhorIndice) |
void | VerificaMelhor (TPonto &melhor, TPonto atual) |
bool | VerificaMelhor (TPonto atual) |
int | MelhorCusto (TVector< TPonto > &populacao, bool inverter=false) |
TPonto | MelhorAtual (TPonto &atual, TVector< TPonto > &vizinhos, int indice) |
void | ObterExtremos (TVector< TPonto > &populacao, int &minCusto, int &maxCusto) |
void | Explorar () override |
definir para explorar manualmente os dados (não definido em TProcura, apenas em TProcuraConstrutiva) | |
void | LibertarVector (TVector< TPonto > &vector, int excepto=-1) |
int | ExecutaAlgoritmo () |
Executa o algoritmo com os parametros atuais. | |
void | DebugInicioEM (int ID, TPonto solucao) |
void | DebugOptimoLocal (TPonto solucao) |
void | DebugPassoEM (TPonto solucao) |
void | DebugPassoAG (int pop, int min, int max) |
void | DebugCruzamentoAG (int gPai, int gMae, int gFilho, int mutou) |
TVector< TPonto > | CompletarPopulacaoAE (TVector< TPonto > &populacao) |
TVector< TPonto > | SelecionarPaisAE (TVector< TPonto > &populacao) |
TVector< TPonto > | ReproduzirAE (TVector< TPonto > &pais, TVector< TPonto > &populacao) |
TVector< TPonto > | SelecionarSobreviventesAE (TVector< TPonto > &populacao, TVector< TPonto > &descendentes) |
TVector< TPonto > | AplicarDiversidadeAE (TVector< TPonto > &populacao) |
void | DebugGeracaoAE (int epoca, TVector< TPonto > &populacao) |
void | DebugPopulacaoAE (TVector< TPonto > &populacao, const char *titulo) |
void | DiversidadeAE (TVector< TPonto > &populacao, int &minDist, int &maxDist, int &avgDist, int &melhorPior) |
![]() | |
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 > ¶metros, int operacao) |
Grava ou lê a configuração atual. | |
int | NovaConfiguracao (TVector< int > ¶metros) |
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 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 | |
Definition at line 23 of file TCodificacaoPermutacao.h.
|
inline |
Definition at line 27 of file TCodificacaoPermutacao.h.
|
inline |
Definition at line 28 of file TCodificacaoPermutacao.h.
Reimplemented from TProcuraMelhorativa.
Implemented in COitoDamasCP.
Fica com uma cópia do objecto.
Este método tem de ser criado na subclasse, de modo a um estado poder ficar igual a outro. As variáveis de estado, devem ser todas copiadas.
Deve garantir que as variáveis copiadas sejam suficientes para reconstruir o estado corretamente. No entanto, uma instância pode ter dados que não mudam em cada estado. Essas variáveis não precisam de estar no estado, e podem ser alocadas de forma estática na subclasse, não sendo necessário copiar nesta função.
A não ser que exista uma estrutura de dados completa, o modelo de código em baixo pode ser facilmente reproduzido para qualquer subclasse.
Reimplemented from TProcuraMelhorativa.
Definition at line 9 of file TCodificacaoPermutacao.cpp.
Reimplemented from TProcuraMelhorativa.
Definition at line 52 of file TCodificacaoPermutacao.cpp.
Mostra o estado no ecrã, para debug.
Esta função deverá mostrar claramente o estado atual, em texto mas da forma mais confortável possível. O formato texto destina-se principalmente a quem implementa o problema, e não utilizadores finais. É importante poder explorar o espaço de estados, para verificar a correta implementação dos sucessores, como também possa ver a árvore de procura dos algoritmos, para árvores pequenas, e assim detectar bugs.
NovaLinha()
pode imprimir caracteres que representam os ramos da árvore de procura, criando uma visualização textual que simula a estrutura da procura.Parametro(NIVEL_DEBUG)
. Um nível menor pode mostrar informações mais sucintas, enquanto um nível maior pode detalhar todas as variáveis do estado.Reimplemented from TProcura.
Definition at line 283 of file TProcura.cpp.
Mostra o estado no ecrã, para debug.
Esta função deverá mostrar claramente o estado atual, em texto mas da forma mais confortável possível. O formato texto destina-se principalmente a quem implementa o problema, e não utilizadores finais. É importante poder explorar o espaço de estados, para verificar a correta implementação dos sucessores, como também possa ver a árvore de procura dos algoritmos, para árvores pequenas, e assim detectar bugs.
NovaLinha()
pode imprimir caracteres que representam os ramos da árvore de procura, criando uma visualização textual que simula a estrutura da procura.Parametro(NIVEL_DEBUG)
. Um nível menor pode mostrar informações mais sucintas, enquanto um nível maior pode detalhar todas as variáveis do estado.Reimplemented from TProcura.
Definition at line 22 of file TCodificacaoPermutacao.cpp.
Mostra uma informação de debug, se o nível de debug for suficiente.
tipo | Nível de detalhe necessário para exibir a mensagem. |
exato | Se true, só imprime se o nível de debug for exatamente igual a tipo . Se false, imprime se for >= tipo . |
fmt | Formato da mensagem, como no printf. |
Definition at line 550 of file TProcura.h.
Reimplemented from TProcuraMelhorativa.
Definition at line 308 of file TCodificacaoPermutacao.cpp.
Cria um objecto que é uma cópia deste.
Este método tem de ser criado na subclasse, de modo a criar uma cópia do mesmo tipo. O código da subclasse geralmente segue um padrão e pode utilizar o modelo abaixo, aproveitando o método Copiar(). É especialmente útil na função de Sucessores(), na geração de um novo estado.
Implements TProcuraMelhorativa.
Implemented in COitoDamasCP.
Coloca o objecto no estado inicial da procura.
Este método inicializa as variáveis de estado no estado inicial vazio. Representa o estado inicial antes de qualquer ação ser realizada na procura. Caso existam dados de instância, deve neste método carregar a instância. A primeira instrução deverá chamar o método da superclasse, conforme modelo em baixo.
Reimplemented from TProcura.
Implemented in COitoDamasCP.
Reimplemented from TProcuraMelhorativa.
Definition at line 271 of file TCodificacaoPermutacao.cpp.
Reimplemented from TProcuraMelhorativa.
Definition at line 14 of file TCodificacaoPermutacao.cpp.
|
virtual |
Inicializa os parametros, indicadores e instâncias.
Nesta função, a primeira instrução deverá ser a chamada da função da superclasse, para que sejam criados os parametros da superclasse antes de qualquer outra instrução.
Cada problema pode ter um algoritmo e configurações padrão que funcionam bem na maioria dos casos. Nesta função, podem ser definidos estes valores de omissão.
Novos parâmetros podem ser adicionados conforme necessário para atender às particularidades do problema. Estes parametros podem depois ser selecionados ou incluídos num teste empírico, de modo a averiguar em fase de testes, qual a melhor configuração, evitando escolhas arbitrárias ou não fundamentadas.
Nesta função deve ser redefinida a variável com informação dos IDs das instâncias disponíveis. Essa variável é do tipo TParametro, mas não está na lista de parametros, devendo ser inicializada aqui.
Existindo novos indicadores, devem ser adicionados aqui, e redefinida a função Indicador() para calcular o valor.
parametrosConstrutivos
, garantindo que novas adições na superclasse sejam automaticamente refletidas aqui.Exemplo com a alteração do valor de omissão de um parametro, e adição de dois novos parametros.
Reimplemented from TProcura.
Definition at line 27 of file TCodificacaoPermutacao.cpp.
Reimplemented from TProcuraMelhorativa.
Definition at line 228 of file TCodificacaoPermutacao.cpp.
Definition at line 30 of file TCodificacaoPermutacao.h.
|
static |
Definition at line 31 of file TCodificacaoPermutacao.h.