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;
 
class TProcuraConstrutiva;
class CListaNo;
 
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;
    int debugID = 0;
 
 
 
    virtual TNo Duplicar(void) = 0;
 
    virtual void Copiar(TNo objecto) {}
 
    void Inicializar(void) override { TProcura::Inicializar(); custo = 0; ramo = {}; }
 
    virtual void Sucessores(TVector<TNo>& sucessores);
 
    virtual bool SolucaoCompleta(void) { return false; }
 
 
    virtual bool Validar(TVector<TString> solucao);
 
    void ResetParametros() override;
 
 
    virtual TString Acao(TNo sucessor) { return "ação inválida"; }
 
    virtual void Codifica(TBits &estado);
 
    virtual int Heuristica(void);
 
 
 
    virtual bool Acao(TString acao);
 
 
 
    virtual bool Distinto(TNo estado) { return true; }
 
    void MostrarSolucao(void) { MostrarCaminho(); }
 
    TVector<TString> Solucao();
 
    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 expansoes;
    static int geracoes;
    static int custoAcao;
 
    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 = "   ";
 
 
    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 minimizar = true);
    // 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(bool noFolha);
    // Passo no algoritmo em largura
    void DebugPasso(CListaNo* lista = NULL);
    // Mostrar sucessores
    void DebugSucessores(TVector<TNo>& sucessores);
    // uma nova iteração de um algoritmo iterativo
    void DebugIteracao(int iteracao, const char* simbolo);
    // informação geral sobre o estado 
    void DebugEstado(bool novaLinha = true) const;
    void DebugRamo(const char* ramo, const char* folha);
    void DebugFolha(bool fimLinha, const char* fmt, ...) {
        if (Parametro(NIVEL_DEBUG) >= COMPLETO) {
            if (fimLinha)
                ramo.Last() = " └─";
            NovaLinha();
        }
        else
            Debug(PASSOS, false, " ─── ");
        if (Parametro(NIVEL_DEBUG) >= PASSOS) {
            va_list args;
            va_start(args, fmt);
            vprintf(fmt, args);
            va_end(args);
        }
    }
 
    // 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, int iAux = -1, TVector<int>* id = NULL);
    void Explorar();
    void MostrarCaminho();
 
    // variáveis da hashtable com perdas, se existir uma colisão, substitui
    static TBits elementosHT[TAMANHO_HASHTABLE]; // hashtable
    static int custoHT[TAMANHO_HASHTABLE]; // hashtable / custo do estado que foi gerado
    static TBits estadoCodHT; // 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);
};