TProcuraConstrutiva.h

Go to the documentation of this file.

#pragma once
 
#include "../TVector.h"
#include "../TProcura.h"
 
// número de elementos na hashtable com perdas
constexpr int TAMANHO_HASHTABLE = 1000000;
// tamanho máximo de um objecto, em unidades de 64 bits
constexpr int OBJETO_HASHTABLE = 5;
 
class TProcuraConstrutiva;
 
typedef TProcuraConstrutiva* TNo;
 
enum EIndicadoresConstrutiva {
    IND_CUSTO = IND_RESULTADO,    
    IND_EXPANSOES = IND_PROCURA,    
    IND_GERACOES,                  
    IND_LOWER_BOUND,                  
    IND_CONSTRUTIVA                
};
 
enum EParametrosConstrutiva {
    VER_ACOES = PARAMETROS_PROCURA, 
    LIMITE,                
    ESTADOS_REPETIDOS,      
    PESO_ASTAR,             
    RUIDO_HEURISTICA,             
    BARALHAR_SUCESSORES,           
    PARAMETROS_CONSTRUTIVA 
};
 
 
enum EAlgoritmo {
    LARGURA_PRIMEIRO = 1, 
    CUSTO_UNIFORME,       
    PROFUNDIDADE_PRIMEIRO,
    MELHOR_PRIMEIRO,      
    A_STAR,               
    IDA_STAR,             
    BRANCH_AND_BOUND       
};
 
 
enum EEstadosRepetidos { 
    IGNORADOS = 1, 
    ASCENDENTES,   
    GERADOS        
};
 
 
class TProcuraConstrutiva : public TProcura
{
public:
    TProcuraConstrutiva(void);
    virtual ~TProcuraConstrutiva(void) {}
 
    TNo pai = NULL;
    int custo = 1;
    int heuristica = 0;
 
 
 
    virtual TNo Duplicar(void) = 0;
 
    virtual void Copiar(TNo objecto) { }
 
    void Inicializar(void) override { TProcura::Inicializar(); custo = 0; }
 
    virtual void Sucessores(TVector<TNo>& sucessores);
 
    virtual bool SolucaoCompleta(void) { return false; }
 
    void ResetParametros() override;
 
 
    virtual const char* Acao(TNo sucessor) { return "ação inválida"; }
 
    virtual void Codifica(uint64_t estado[OBJETO_HASHTABLE]);
 
    virtual int Heuristica(void);
 
 
 
    virtual bool Acao(const char* acao);
 
 
 
    virtual bool Distinto(TNo estado) { return true; }
 
    void MostrarSolucao(void) { MostrarCaminho(); }
 
    int ExecutaAlgoritmo();
 
    int64_t Indicador(int id) override;
 
 
 
 
    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 TVector<TNo> caminho;
    static TNo solucao;
    static int lowerBound;
    static int tamanhoCodificado;
    static int expansoes;
    static int geracoes;
 
    static TVector<unsigned char> ramo;
    static int espacosRamo;
 
 
    void LimparEstatisticas() override;
    void ExecucaoTerminada() override;
 
    int LowerBound() { return custo + Parametro(PESO_ASTAR) * 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);
 
 
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) const;
    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 Explorar();
    void MostrarCaminho();
 
    // 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);
};