TProcuraConstrutiva.h

Go to the documentation of this file.

#pragma once
 
#define _CRT_SECURE_NO_WARNINGS
 
#include "TVector.h"
#include <stdint.h>
#include <time.h>
#include <limits.h>
 
// número de elementos na hashtable com perdas
#define TAMANHO_HASHTABLE 1000000
// tamanho máximo de um objecto, em unidades de 64 bits
#define OBJETO_HASHTABLE 5
// código para número não lido (não deve ser utilizado num parâmetro)
#define NAO_LIDO -1000000
 
class TProcuraConstrutiva;
 
typedef TProcuraConstrutiva* TNo;
 
enum EParametrosConstrutiva {
    algoritmo = 0,         
    nivelDebug,            
    verAcoes,              
    seed,                  
    limiteTempo,           
    limiteGeracoes,        
    limiteExpansoes,       
    limiteAvaliacoes,      
    limite,                
    estadosRepetidos,      
    pesoAStar,             
    ruidoHeur,             
    baralharSuc,           
    parametrosConstrutivas 
};
 
 
enum EAlgoritmo {
    larguraPrimeiro = 1, 
    custoUniforme,       
    profundidadePrimeiro,
    melhorPrimeiro,      
    aStar,               
    idAStar,             
    branchAndBound       
};
 
enum ENivelDebug {
    nada = 0,  
    atividade, 
    passos,    
    detalhe,   
    completo   
};
 
enum EEstadosRepetidos { 
    ignorados = 1, 
    ascendentes,   
    gerados        
};
 
enum EOperacao { gravar = 0, ler };
 
typedef struct SParametro { 
    const char* nome;
    int valor;
    int min;
    int max; 
    const char* descricao; 
    const char** nomeValores;
} TParametro;
 
 
typedef struct SResultado {
    int instancia, custo, expansoes, geracoes, avaliacoes, configuracao; 
    clock_t tempo; 
} TResultado;
 
class TProcuraConstrutiva
{
public:
    TProcuraConstrutiva(void);
    virtual ~TProcuraConstrutiva(void) {}
 
    TNo pai;
    int custo;
    int heuristica;
 
 
 
    virtual TNo Duplicar(void) = 0;
 
    virtual void Copiar(TNo objecto) { }
 
    virtual void SolucaoVazia(void) { custo = 0; }
 
    virtual void Sucessores(TVector<TNo>& sucessores);
 
    virtual bool SolucaoCompleta(void) { return false; }
 
    virtual void TesteManual(const char* nome);
 
 
    virtual const char* Acao(TNo sucessor) { return "ação inválida"; }
 
    virtual void Codifica(uint64_t estado[OBJETO_HASHTABLE]);
 
    virtual int Heuristica(void);
 
    virtual void Debug(void);
 
    virtual void ResetParametros();
 
 
 
    virtual bool Acao(const char* acao);
 
    virtual bool Parar(void) {
        return TempoExcedido() || ExpansoesExcedido() || GeracoesExcedido() || AvaliacoesExcedido() || memoriaEsgotada;
    }
 
    virtual bool Distinto(TNo estado) { return true; }
 
    virtual void MostrarSolucao(void) { MostrarCaminho(); }
 
    virtual int ExecutaAlgoritmo();
 
    virtual void TesteEmpirico(int inicio = -1, int fim = -1, bool mostrarSolucoes = true);
 
 
 
    int LarguraPrimeiro(int limite = 0);
 
 
    int CustoUniforme(int limite = 0);
 
    int ProfundidadePrimeiro(int nivel = 0);
 
 
    int MelhorPrimeiro(int nivel = 0);
 
    int AStar(int limite = 0);
 
    int IDAStar(int upperBound = 0);
 
    int BranchAndBound(int upperBound = 0);
 
 
    static TParametro instancia;
    static TVector<TParametro> parametro;
    static TVector<TVector<int>> configuracoes;
    static int geracoes;
    static int expansoes;
    static int avaliacoes;
    static TVector<TNo> caminho;
    static bool memoriaEsgotada;
    static TNo solucao;
    static int lowerBound;
    static int tamanhoCodificado;
 
    static TVector<unsigned char> ramo;
    static int espacosRamo;
    static clock_t instanteFinal;
 
 
    // LimparEstatisticas: Chamar antes da corrida
    void LimparEstatisticas(clock_t &inicio);
    // FinalizarCorrida: Chamar após a corrida
    void FinalizarCorrida(clock_t inicio);
 
    int LowerBound() { return custo + parametro[pesoAStar].valor * heuristica / 100; } // f(n) = g(n) + W h(n)
    static void LibertarVector(TVector<TNo>& vector, int excepto = -1, int maiorQue = -1);
 
    // Chamar sempre que se quer uma nova linha com a árvore em baixo
    void NovaLinha(bool tudo = true);
 
    // ler um número, ou retorna NAO_LIDO
    static int NovoValor(const char* prompt); 
 
protected:
 
    // Métodos para visualizar a procura
 
    // Método para ser chamado antes de analisar cada sucessor
    void DebugExpansao(int sucessor, int sucessores, bool duplo = false);
    // Método para ser chamado quando não há sucessores ou há um corte de profundidade
    void DebugCorte(int sucessores = -1, bool duplo = false);
    // Encontrou uma solução
    void DebugSolucao(bool continuar = false);
    // Informação de debug na chamada ao método recursivo
    void DebugChamada(void);
    // Passo no algoritmo em largura
    void DebugPasso(void);
    // Mostrar sucessores
    void DebugSucessores(TVector<TNo>& sucessores);
    // uma nova iteração de um algoritmo iterativo
    void DebugIteracao(int iteracao);
    // informação geral sobre o estado 
    void DebugEstado(int id = -1, int pai = -1);
    void DebugRamo(char ramo, char folha);
 
    // metodos internos
    int ObjetivoAlcancado(int item, TVector<TNo>& lista);
    int ObjetivoAlcancado(TNo estado, bool completa = true);
    int SolucaoEncontrada(bool continuar = false);
    void CalculaCaminho(bool completa = true); // coloca o caminho desde o estado objetivo
    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 ExplorarSucessores(bool jogo=false);
    void EditarParametros();
    void EditarConfiguracoes();
    void MostrarConfiguracoes(int detalhe, int atual = -1);
    void SolicitaInstancia();
    bool TempoExcedido() { return instanteFinal < clock(); }
    bool GeracoesExcedido() {
        return parametro[limiteGeracoes].valor > 0 && parametro[limiteGeracoes].valor < geracoes;
    }
    bool ExpansoesExcedido() {
        return parametro[limiteExpansoes].valor > 0 && parametro[limiteExpansoes].valor < expansoes;
    }
    bool AvaliacoesExcedido() {
        return parametro[limiteAvaliacoes].valor > 0 && parametro[limiteAvaliacoes].valor < avaliacoes;
    }
    void MostrarCaminho();
    void MostraParametros(int detalhe = 1, TVector<int>* idParametros = NULL);
    void MostraRelatorio(TVector<TResultado>& resultados);
    int Dominio(int& variavel, int min = INT_MIN, int max = INT_MAX);
    void ConfiguracaoAtual(TVector<int>& parametros, int operacao); // gravar (ou ler) a configuração atual
    int MelhorResultado(TResultado base, TResultado alternativa);
    void CalculaTorneio(TVector<TResultado>& resultados);
    void MostrarTorneio(TVector<TVector<int>>& torneio, bool jogo=false);
    void BarraTorneio(bool nomes);
    void ExtrairConfiguracao(TVector<TResultado>& resultados, TVector<TResultado>& extracao, int configuracao);
 
    // variáveis da hashtable com perdas, se existir uma colisão, substitui
    static uint64_t elementosHT[TAMANHO_HASHTABLE][OBJETO_HASHTABLE]; // hashtable
    static int custoHT[TAMANHO_HASHTABLE]; // hashtable / custo do estado que foi gerado
    static uint64_t estadoCodHT[OBJETO_HASHTABLE]; // elemento codificado
    static int colocadosHT; // número de elementos colocados na HT
    unsigned int Hash(); // retorna um valor hash do estado atual, após codificado
    void LimparHT();
    // caso o estado não exista, retorna falso e insere para que não seja gerado novamente
    // caso exista um elemento, mas gerado com um custo mais alto, considerar que não existe ainda
    // se existe retorna true 
    bool ExisteHT();
    virtual void SubstituirHT(int indice);
};
 
// estrutura para índice a fazer a função de lista (em vetor), de modo a reduzir custos de inserção ordenada 
// utilizado em CListaNo
typedef struct SIndice {
    TNo estado; // elemento na lista
    int prox; // próximo elemento da lista, pela ordem mantida (de custo)
    int proxDistinto; // próximo elemento da lista com custo distinto
} TIndice;
 
// classe para manter lista ordenada de estados (CustoUniforme e AStar)
class CListaNo {
private:
    int limite; // tamanho da lista, se !=0 --- tamanho vai até ao dobro, após o qual é limpa para metade dos elementos
    TVector<TIndice> indice; // índice com a estrutura de lista
    TVector<int> livre; // índices da lista apagados, que estão livres e podem ser utilizados
    bool completa; // se verdade, nunca foi limpa, pelo que a lista é completa
public:
    CListaNo(int limite = 0) : 
        limite(limite), 
        indice(2*limite), 
        livre(limite), 
        completa(true), 
        atual(0) {}
    ~CListaNo();
 
    // elemento a ser processado 
    // (anteriores a este, excepto o primeiro, podem ser apagados, quando há falta de espaço)
    int atual; 
 
    bool Completa() { return completa; }
 
    // retorna o valor de um elemento
    int Valor(int i) {
        TNo estado;
        if ((estado = Estado(i)) != NULL)
            return estado->LowerBound();
        return INT_MAX;
    }
 
    // retorna o próximo elemento, ou -1 se não há mais
    int Proximo(int i = -1) { 
        if (i < 0)
            return indice[atual].prox;
        if(i>=0 && i<indice.Count())
            return indice[i].prox; 
        return -1;
    }
    // este passo é crítico para poder inserir rapido numa lista ordenada com muitos elementos iguais
    int ProximoDistinto(int i = -1) {
        if (i < 0)
            return indice[atual].proxDistinto;
        if (i >= 0 && i < indice.Count())
            return indice[i].proxDistinto;
        return -1;
    }
    // retorna o estado deste elemento
    TNo Estado(int i = -1) {
        if (i < 0)
            return indice[atual].estado;
        if (i >= 0 && i < indice.Count())
            return indice[i].estado;
        return NULL;
    }
    
    int Inserir(TNo elemento, int id = 0); // insere por ordem de LB, retorna o primeiro elemento com o mesmo valor
    void Inserir(TVector<TNo>& elementos); // inserir todos os elementos por ordem (não alterar atual)
 
private:
    int NovoElemento(TNo elemento); // retorna o índice onde foi inserido
    void LibertarLista();
    void LibertarSeguinte(int id);
 
};