TProcuraConstrutiva.h

Go to the documentation of this file.

#pragma once
 
#define _CRT_SECURE_NO_WARNINGS
 
#include "../TVector.h"
#include "../TProcura.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
 
class TProcuraConstrutiva;
 
typedef TProcuraConstrutiva* TNo;
 
enum EIndicadoresConstrutiva {
    indCusto = indResultado,      
    indExpansoes = indProcura,    
    indGeracoes,                  
    indLowerBound,                
    indConstrutiva                
};
 
enum EParametrosConstrutiva {
    verAcoes = parametrosProcura, 
    limite,                
    estadosRepetidos,      
    pesoAStar,             
    ruidoHeur,             
    baralharSuc,           
    parametrosConstrutivas 
};
 
 
enum EAlgoritmo {
    larguraPrimeiro = 1, 
    custoUniforme,       
    profundidadePrimeiro,
    melhorPrimeiro,      
    aStar,               
    idAStar,             
    branchAndBound       
};
 
 
enum EEstadosRepetidos { 
    ignorados = 1, 
    ascendentes,   
    gerados        
};
 
 
class TProcuraConstrutiva : public TProcura
{
public:
    TProcuraConstrutiva(void);
    virtual ~TProcuraConstrutiva(void) {}
 
    TNo pai;
    int custo;
    int heuristica;
 
 
 
    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();
 
    int 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(clock_t &inicio) override;
    void ExecucaoTerminada(clock_t inicio) override;
 
    int LowerBound() { return custo + Parametro(pesoAStar) * 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);
    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);
};