|
TProcura
Biblioteca em C++ para testes paramétricos de algoritmos, e coleção de algoritmos de procura e otimização
|
Representa um estado no espaço de estados. More...
#include <TProcuraConstrutiva.h>
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< TString > | Solucao () |
| 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_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 |
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< 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 | 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 char * | RAMO_ESTADO = " ├■" |
| static constexpr const char * | RAMO_ESTADO2 = " ├□" |
| static constexpr const char * | RAMO_ESTADO_FIM = " └■" |
| static constexpr const char * | RAMO_ESTADO2_FIM = " └□" |
| static constexpr const char * | RAMO_NOVO = " ├─" |
| static constexpr const char * | RAMO_FIM = " └─" |
| static constexpr const char * | RAMO_CONTINUA = " │ " |
| static constexpr const char * | RAMO_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< 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. | |
| 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 > ¶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, 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 | |
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.
| TProcuraConstrutiva::TProcuraConstrutiva | ( | void | ) |
Definition at line 31 of file TProcuraConstrutiva.cpp.
Definition at line 114 of file TProcuraConstrutiva.h.
Definition at line 245 of file TProcuraConstrutiva.cpp.
|
protected |
Definition at line 576 of file TProcuraConstrutiva.cpp.
Definition at line 685 of file TProcuraConstrutiva.cpp.
Definition at line 648 of file TProcuraConstrutiva.cpp.
|
protected |
Definition at line 633 of file TProcuraConstrutiva.cpp.
Definition at line 744 of file TProcuraConstrutiva.h.
Definition at line 790 of file TProcuraConstrutiva.cpp.
Definition at line 641 of file TProcuraConstrutiva.cpp.
Definition at line 665 of file TProcuraConstrutiva.cpp.
Definition at line 747 of file TProcuraConstrutiva.cpp.
|
overridevirtual |
Chamar após a execução do algoritmo. Grava o tempo consumido.
Reimplemented from TProcura.
Definition at line 861 of file TProcuraConstrutiva.cpp.
|
protected |
Definition at line 993 of file TProcuraConstrutiva.cpp.
|
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.
Definition at line 962 of file TProcuraConstrutiva.cpp.
|
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.
|
protected |
Definition at line 967 of file TProcuraConstrutiva.cpp.
|
inline |
Definition at line 716 of file TProcuraConstrutiva.h.
|
protected |
Definition at line 398 of file TProcuraConstrutiva.cpp.
Definition at line 707 of file TProcuraConstrutiva.cpp.
Definition at line 238 of file TProcuraConstrutiva.cpp.
Definition at line 358 of file TProcuraConstrutiva.cpp.
|
protected |
Definition at line 370 of file TProcuraConstrutiva.cpp.
Reimplemented in TProcuraAdversa.
Definition at line 1013 of file TProcuraConstrutiva.cpp.
|
protected |
Definition at line 265 of file TProcuraConstrutiva.cpp.
|
staticprotected |
Definition at line 775 of file TProcuraConstrutiva.h.
|
staticprotected |
Definition at line 773 of file TProcuraConstrutiva.h.
|
staticprotected |
Definition at line 772 of file TProcuraConstrutiva.h.
|
staticprotected |
Definition at line 774 of file TProcuraConstrutiva.h.