Particao.h

Go to the documentation of this file.

#pragma once
 
#include "../TProcuraMelhorativa.h"
#include "../TCodificacaoBinaria.h"
 
//  CParticao class
//  Author: José Coelho 
//  Last revision: 2025-01-30
//  Description:
//    Implementa o problema da particao. Este problema consiste em dividir
//    um conjunto de numeros naturais em duas partes cuja soma dos numeros em cada
//    parte seja igual.
class CParticao :
    public TProcuraMelhorativa
{
public:
    CParticao(void);
    ~CParticao(void);
 
    // estrutura de dados (números a colocar, números colocados em cada lado, e total de cada lado)
    TVector<int> numeros, esquerda, direita;
    int totalEsquerda=0, totalDireita=0;
    TVector<bool> solCompleta; // codificação de uma solução, na abordagem melhoriativa: vetor binário
    // na abordagem melhorativa, assume-se que os números estão em "numeros" e não são deslocados para esquerd/direita
 
    // Metodos virtuais redefinidos
    TPonto Duplicar(void) {
        CParticao* clone = new CParticao;
        if (clone != NULL)
            clone->Copiar(this);
        else
            memoriaEsgotada = true;
        return clone;
    }
 
    void Copiar(TPonto objeto) {
        TProcuraMelhorativa::Copiar(objeto);
        numeros = ((CParticao*)objeto)->numeros;
        esquerda = ((CParticao*)objeto)->esquerda;
        direita = ((CParticao*)objeto)->direita;
        totalEsquerda = ((CParticao*)objeto)->totalEsquerda;
        totalDireita = ((CParticao*)objeto)->totalDireita;
        solCompleta = ((CParticao*)objeto)->solCompleta;
    }
    void Inicializar(void);
    void Debug(bool completo = true) override;
    void MostrarSolucao(void) { Debug(); }
    void TesteManual(const char* nome);
 
    // métodos melhorativos
    void NovaSolucao(void);
    int Avaliar(void);
    void Vizinhanca(TVector<TPonto>& vizinhos);
    void Mutar(void);
    void Cruzamento(TPonto a, TPonto b);
    int Distancia(TPonto a);
};
 
class CParticaoCB :
    public TCodificacaoBinaria
{
public:
    CParticaoCB() {}
    ~CParticaoCB() {}
 
    // dados da instância, em variáveis estáticas
    static TVector<int> numeros; // número de elementos a particionar
 
    int Avaliar(void);
 
    void ResetParametros() {
        TCodificacaoBinaria::ResetParametros();
        instancia = { "", 10,2,1000};
    }
 
    TPonto Duplicar(void) {
        CParticaoCB* clone = new CParticaoCB;
        if (clone != NULL)
            clone->Copiar(this);
        else
            memoriaEsgotada = true;
        return clone;
    }
    void Inicializar(void);
    void Debug(bool completo) override;
};