Representa um estado do problema da partição. More...

#include <Particao.h>

Inheritance diagram for CParticao:

Collaboration diagram for CParticao:

Public Member Functions
	CParticao (void)

	~CParticao (void)

TProcuraConstrutiva *	Duplicar (void)
	Cria um objecto que é uma cópia deste.

void	Copiar (TProcuraConstrutiva *objecto)

void	Inicializar (void)
	Coloca o objecto no estado inicial da procura.

void	Sucessores (TVector< TNo > &sucessores)
	Coloca em sucessores a lista de estados sucessores.

bool	SolucaoCompleta (void)
	Verifica se o estado actual é objectivo (é uma solução completa)

void	Debug (void)
	Mostra o estado no ecr�, para debug.

void	MostrarSolucao (void)
	definir para visualizar a solu��o

const char *	Acao (TProcuraConstrutiva *sucessor)

void	Codifica (uint64_t estado[OBJETO_HASHTABLE])
	Codifica o estado para um vetor de inteiros de 64 bits.

void	ResetParametros ()
	Inicializa os parametros, indicadores e inst�ncias.

	CParticao (void)

	~CParticao (void)

TPonto	Duplicar (void)
	Cria um objecto que é uma cópia deste.

void	Copiar (TPonto objecto)
	Fica com uma cópia do objecto.

void	Inicializar (void)
	Coloca o objecto no estado inicial da procura.

void	Debug (void)
	Mostra o estado no ecr�, para debug.

void	MostrarSolucao (void)
	definir para visualizar a solu��o

void	TesteManual (const char *nome)
	Inicializa a intera��o com o utilizador.

void	NovaSolucao (void)

int	Avaliar (void)

void	Vizinhanca (TVector< TPonto > &vizinhos)

void	Mutar (void)

void	Cruzamento (TPonto a, TPonto b)

int	Distancia (TPonto a)

Public Member Functions inherited from TProcuraConstrutiva
	TProcuraConstrutiva (void)

virtual	~TProcuraConstrutiva (void)

virtual void	Copiar (TNo objecto)
	Fica com uma cópia do objecto.

void	Inicializar (void) override
	Coloca o objecto no estado inicial da procura.

void	ResetParametros () override
	Redefinição. Ver TProcura::ResetParametros().

virtual const char *	Acao (TNo sucessor)
	Retorna a ação (movimento, passo, jogada, lance, etc.) que gerou o sucessor.

virtual int	Heuristica (void)
	Função para calcular quanto falta para o final, o valor da heurística.

virtual bool	Acao (const char *acao)
	Executa a ação (movimento, passo, jogada, lance, etc.) no estado atual.

virtual bool	Distinto (TNo estado)
	Verifica se o estado actual distinto do fornecido.

void	MostrarSolucao (void)
	Mostrar solução, seja um caminho ou o próprio estado.

int	ExecutaAlgoritmo ()
	Executa o algoritmo com os parametros atuais.

int	Indicador (int id) override
	Redefinição. Ver TProcura::Indicador().

int	LarguraPrimeiro (int limite=0)
	Executa a procura em largura primeiro, algoritmo cego.

int	CustoUniforme (int limite=0)
	Executa a procura por custo uniforme, algoritmo cego.

int	ProfundidadePrimeiro (int nivel=0)
	Executa a procura em profundidade primeiro, algoritmo cego.

int	MelhorPrimeiro (int nivel=0)
	Executa a procura melhor primeiro, algoritmo informado.

int	AStar (int limite=0)
	Executa a procura A*, algoritmo informado.

int	IDAStar (int upperBound=0)
	Executa a procura IDA*, algoritmo informado.

int	BranchAndBound (int upperBound=0)
	Executa o algoritmo Branch-and-Bound, um algoritmo informado.

void	LimparEstatisticas (clock_t &inicio) override
	Chapar antes da execu��o do algoritmo. Limpa valores estat�sticos, e fixa o instante limite de tempo para a execu��o.

void	ExecucaoTerminada (clock_t inicio) override
	Chamar ap�s a execu��o do algoritmo. Grava o tempo consumido.

int	LowerBound ()

void	NovaLinha (bool tudo=true)

Public Member Functions inherited from TProcura
	TProcura (void)

virtual	~TProcura (void)

virtual bool	Parar (void)
	Verifica se a procura deve ser interrompida.

virtual void	TesteEmpirico (TVector< int > instancias, bool mostrarSolucoes=true, char *ficheiro=NULL)
	Executa testes emp�ricos, em todas as configura��es guardadas, nas inst�ncias selecionadas.

virtual void	main (int argc, char argv[], const char nome)
	Inicializa a intera��o com o utilizador.

virtual TVector< int >	CodificarSolucao ()
	retorna um vetor de inteiros com a codifcia��o da solu��o (esta codifica��o ser� adicionada aos indicadores, no ficheiro CSV de resultados)

bool	TempoExcedido ()

bool	IteracoesExcedido ()

int	Parametro (int id)

Public Member Functions inherited from TProcuraMelhorativa
	TProcuraMelhorativa (void)

	~TProcuraMelhorativa (void)

bool	Acao (const char *acao)

void	ResetParametros () override
	Inicializa os parametros, indicadores e inst�ncias.

int	EscaladaDoMonte ()

int	AlgoritmoGenetico ()

void	TesteManualX (const char *nome)
	provavelmente apagar

void	DebugMelhorEncontrado (TPonto ponto)
	provavalmente apagar

int	Indicador (int id) override
	Redefinição. Ver TProcura::Indicador().

void	LimparEstatisticas (clock_t &inicio)
	Chapar antes da execu��o do algoritmo. Limpa valores estat�sticos, e fixa o instante limite de tempo para a execu��o.

Public Attributes
TVector< int >	numeros

TVector< int >	esquerda

TVector< int >	direita

int	totalEsquerda

int	totalDireita

TVector< bool >	solCompleta

Public Attributes inherited from TProcuraConstrutiva
TNo	pai
	Ponteiro para o estado pai, na árvore de procura.

int	custo
	Custo total acumulado desde o estado inicial.

int	heuristica
	Estimativa para o custo até um estado objetivo, se disponível.

Public Attributes inherited from TProcuraMelhorativa
int	custo
	Custo total, atualizada após Avaliar()

int	geracoes
	Número de estados gerados.

int	epocas
	Número de épocas decorridas num algoritmo evolutivo. Uma época é uma geração única.

Additional Inherited Members
Static Public Member Functions inherited from TProcuraConstrutiva
static void	LibertarVector (TVector< TNo > &vector, int excepto=-1, int maiorQue=-1)

Static Public Member Functions inherited from TProcura
static int	NovoValor (const char *prompt)

static char *	NovoTexto (const char *prompt)

Static Public Attributes inherited from TProcuraConstrutiva
static TVector< TNo >	caminho
	Solução retornada pela procura (os estados devem ser libertados).

static TNo	solucao = NULL
	Estado objetivo encontrado, retornado pela procura (deve ser libertado).

static int	lowerBound = 0
	Valor mínimo que a solução pode apresentar, obtido pela procura.

static int	tamanhoCodificado = OBJETO_HASHTABLE
	Número de inteiros de 64 bits utilizados para codificar um objeto (≤ OBJETO_HASHTABLE).

static int	expansoes = 0
	Número de expansões efetuadas.

static int	geracoes = 0
	Número de estados gerados.

static TVector< unsigned char >	ramo

static int	espacosRamo = 2

Static Public Attributes inherited from TProcura
static TParametro	instancia = { NULL,1,1,1, NULL, NULL }
	ID da inst�ncia atual, a ser utilizado em SolucaoVazia().

static char	ficheiroInstancia [256] = "instancia_"
	nome do ficheiro de uma inst�ncia - editado pelo utilizador (utilizar como prefixo, concatenando com ID da inst�ncia) pode ser utilizado para gravar a inst�ncia num novo formato, colocando um indicador ativo que � chamado ap�s a execu��o (pode gravar a solu��o para ficheiro tamb�m, mas essa � mais facilmente gravada em CVS codificada em inteiros, onde fica associada � configura��o utilizada para a gerar)

static TVector< TParametro >	parametro
	Par�metros a serem utilizados na configura��o atual.

static TVector< TIndicador >	indicador
	Indicadores que podem ser calculados ap�s a execu��o, quer com informa��o da inst�ncia, quer com resultado da �ltima corrida.

static TVector< int >	indAtivo

static TVector< TVector< int > >	configuracoes
	Conjuntos de configura��es para teste emp�rico.

static int	resultado = 0
	Resultado retornado pelo algoritmo na �ltima execu��o.

static int	tempo = 0
	tempo consumido na �ltima execu��o.

static int	iteracoes = 0
	N�mero total de itera��es realizadas na �ltima execu��o.

static clock_t	instanteFinal = 0
	Instante final (deadline) da corrida atual.

static bool	memoriaEsgotada = false
	Flag indicando problemas de mem�ria esgotada.

Protected Member Functions inherited from TProcuraConstrutiva
void	DebugExpansao (int sucessor, int sucessores, bool duplo=false)

void	DebugCorte (int sucessores=-1, bool duplo=false)

void	DebugSolucao (bool continuar=false)

void	DebugChamada (void)

void	DebugPasso (void)

void	DebugSucessores (TVector< TNo > &sucessores)

void	DebugIteracao (int iteracao)

void	DebugEstado (int id=-1, int pai=-1)

void	DebugRamo (char ramo, char folha)

int	ObjetivoAlcancado (int item, TVector< TNo > &lista)

int	ObjetivoAlcancado (TNo estado, bool completa=true)

int	SolucaoEncontrada (bool continuar=false)

void	CalculaCaminho (bool completa=true)

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 ()
	definir para explorar manualmente os dados (n�o definido em TProcura, apenas em TProcuraConstrutiva)

void	MostrarCaminho ()

unsigned int	Hash ()

void	LimparHT ()

bool	ExisteHT ()

virtual void	SubstituirHT (int indice)

Protected Member Functions inherited from TProcura
void	InserirRegisto (TVector< TResultado > &resultados, int inst, int conf)
	Insere um novo registo de resultados.

int	Registo (TResultado &resultado, int id)
	Procura um registo com determinado id.

void	Registo (TResultado &resultado, int id, int valor)
	Atualiza o valor de um registo.

void	MostraParametros (int detalhe=1, TVector< int > *idParametros=NULL)
	Mostra os par�metros atuais.

void	MostraIndicadores ()
	Mostra os indicadores definidos.

void	MostrarConfiguracoes (int detalhe, int atual=-1)
	Mostra as configura��es dispon�veis.

bool	EditarIndicadores ()
	Permite ao utilizador editar os indicadores a utilizar.

void	EditarParametros ()
	Permite ao utilizador editar os par�metros.

void	EditarConfiguracoes ()
	Permite ao utilizador editar as configura��es.

void	MostraRelatorio (TVector< TResultado > &resultados, bool ultimo=false)
	Mostra um relat�rio dos resultados.

void	ConfiguracaoAtual (TVector< int > &parametros, int operacao)
	Grava ou l� a configura��o atual.

int	NovaConfiguracao (TVector< int > &parametros)
	Adiciona uma nova configura��o se ainda n�o existir.

int	MelhorResultado (TResultado base, TResultado alternativa)
	Compara dois resultados para determinar o melhor.

void	CalculaTorneio (TVector< TResultado > &resultados)
	Calcula o torneio entre v�rias configura��es.

void	MostrarTorneio (TVector< TVector< int > > &torneio, bool jogo=false)
	Mostra os resultados do torneio.

void	BarraTorneio (bool nomes)
	Mostra a barra de progresso ou nomes do torneio.

TVector< TResultado >	ExtrairConfiguracao (TVector< TResultado > &resultados, int configuracao)
	Extrai resultados de uma determinada configura��o.

void	SolicitaInstancia ()
	Solicita ao utilizador o ID da inst�ncia a utilizar, permitindo alterar tamb�m o prefixo do ficheiro.

TVector< int >	SolicitaInstancias ()
	Solicita ao utilizador uma lista de inst�ncias.

void	RelatorioCSV (TVector< TResultado > &resultados, FILE *f)
	Gera um relat�rio CSV com os resultados.

TVector< int >	ExtraiLista (char *str)
	Extrai uma lista de inteiros a partir de uma string.

void	InserirConfiguracoes (char *str, TVector< int > &base)
	Insere configura��es a partir de uma string.

void	InserirConfiguracoes (TVector< int > &base, TVector< int > &produto, TVector< TVector< int > > &valores)
	Insere configura��es gerando o produto cartesiano de valores.

void	AjudaUtilizacao (const char *programa)
	Mostra ajuda de utiliza��o do programa.

Protected Member Functions inherited from TProcuraMelhorativa
void	Selecao (int &pai, int &mae, TVector< int > &pesos, int total)

void	OrdemValor (TVector< TPonto > &populacao, TVector< int > &id)

void	CalcularAvaliacoes (TVector< TPonto > &vizinhos, int &melhorValor, int &melhorIndice)

void	VerificaMelhor (TPonto &melhor, TPonto atual)

TPonto	MelhorAtual (TPonto &atual, TVector< TPonto > &vizinhos, int indice)

void	ObterExtremos (TVector< TPonto > &populacao, int &minCusto, int &maxCusto)

void	Explorar () override
	definir para explorar manualmente os dados (n�o definido em TProcura, apenas em TProcuraConstrutiva)

void	LibertarVector (TVector< TPonto > &vector, int excepto=-1)

int	ExecutaAlgoritmo ()
	Executa o algoritmo com os parametros atuais.

void	DebugVizinhos (TVector< TPonto > &vizinhos)

void	DebugInicioEM (int ID, TPonto solucao)

void	DebugOptimoLocal (TPonto solucao)

void	DebugPassoEM (TPonto solucao)

void	DebugPassoAG (int pop, int min, int max)

void	DebugCruzamentoAG (int gPai, int gMae, int gFilho, int mutou)

Static Protected Member Functions inherited from TProcura
static int	Dominio (int &variavel, int min=INT_MIN, int max=INT_MAX)
	Limita o dom�nio de um par�metro inteiro.

Static Protected Attributes inherited from TProcuraConstrutiva
static uint64_t	elementosHT [TAMANHO_HASHTABLE][OBJETO_HASHTABLE]

static int	custoHT [TAMANHO_HASHTABLE]

static uint64_t	estadoCodHT [OBJETO_HASHTABLE]

static int	colocadosHT = 0

Detailed Description

Representa um estado do problema da partição.

Este problema consiste em dividir um conjunto de numeros naturais em duas partes cuja soma dos numeros em cada parte seja igual.

Definition at line 11 of file Particao.h.

Constructor & Destructor Documentation

◆ CParticao() [1/2]

CParticao::CParticao ( void )

Definition at line 5 of file Particao.cpp.

Here is the caller graph for this function:

◆ ~CParticao() [1/2]

CParticao::~CParticao ( void )

Definition at line 9 of file Particao.cpp.

◆ CParticao() [2/2]

CParticao::CParticao ( void )

◆ ~CParticao() [2/2]

CParticao::~CParticao ( void )

Member Function Documentation

◆ Acao()

const char * CParticao::Acao ( TProcuraConstrutiva * sucessor )

Definition at line 75 of file Particao.cpp.

◆ Avaliar()

int CParticao::Avaliar ( void )

virtual

Reimplemented from TProcuraMelhorativa.

Definition at line 121 of file Particao.cpp.

Here is the call graph for this function:

◆ Codifica()

void CParticao::Codifica ( uint64_t estado[OBJETO_HASHTABLE] )

virtual

Codifica o estado para um vetor de inteiros de 64 bits.

Note: Redefinição opcional. Necessário para identificação de estados repetidos por hashtable.

As variáveis de estado devem ser compactadas no vetor de inteiros de 64 bits. Todos os estados codificados têm de ser distintos de 0. Estados distintos, têm de ficar com codificações distintas.

Em diversos problemas, um mesmo estado pode ter múltiplas representações equivalentes. Por exemplo, se um conjunto de inteiros for um estado, este pode ser representado em vetor. No entanto a ordem é irrelevante, dado que é um conjunto. Assim não faz sentido guardar vários estados que sejam representações do mesmo estado. Há que normalizar o estado antes de o guardar, de modo a que seja dado como estado repetido, se uma das duas formas já tiver sido gerada. O exemplo do conjunto de inteiros, a normalização pode ser a ordenação do vetor, constituindo assim um estado único entre todas as formas que o conjunto pode ser representado em vetor. Problemas de tabuleiro, há simetrias que podem gerar várias versões da mesma posição.

Note: Se a verificação de estados repetidos for baseada em hashtables, a superclasse chama este método dentro de Sucessores().; Para otimizar o consumo de memória, são utilizadas hashtables com perdas. Se necessário pode alterar o tamanho da hashtable editando a macro TAMANHO_HASHTABLE; a variável tamanhoCodificado tem de ter o número de variáveis de 64 bits utilizadas, garantindo que o vetor estado[] não é acedido na posição tamanhoCodificado ou superior.

See also: Inicializar()

void CSubProblema::Codifica(uint64_t estado[OBJETO_HASHTABLE])
{
    Vector<int> vetor; // assumindo neste exemplo que o estado é um vetor de inteiros pequenos
    Normalizar(vetor); // o vetor tem várias formas, e agora é normalizado por uma função de CSubProblema
    TProcuraConstrutiva::Codifica(estado); // chamar a superclasse após normalizar o estado
    // codificar números de 4 bits, assumindo que os inteiros pequenos cabem em 4 bits
    for (int i = 0, index = 0; i < vetor.Count(); i++, index += 4)
        estado[index >> 6] |= (uint64_t)vetor[i] << (index & 63);
}

Reimplemented from TProcuraConstrutiva.

Definition at line 131 of file Particao.cpp.

Here is the call graph for this function:

◆ Copiar() [1/2]

void CParticao::Copiar ( TPonto objecto )

inlinevirtual

Fica com uma cópia do objecto.

Note: Obrigatória a redefinição.

Este método tem de ser criado na subclasse, de modo a um estado poder ficar igual a outro. As variáveis de estado, devem ser todas copiadas.

Deve garantir que as variáveis copiadas sejam suficientes para reconstruir o estado corretamente. No entanto, uma instância pode ter dados que não mudam em cada estado. Essas variáveis não precisam de estar no estado, e podem ser alocadas de forma estática na subclasse, não sendo necessário copiar nesta função.

A não ser que exista uma estrutura de dados completa, o modelo de código em baixo pode ser facilmente reproduzido para qualquer subclasse.

Note: Não é preciso copiar as variáveis da classe TProcuraConstrutiva, pai, custo, heuristica.

See also: Sucessores() e Heuristica()

void CSubClasse::Copiar(TPonto objecto) {
        CSubProblema& obj = *((CSubProblema*)objecto);
        // copiar todas as variáveis do estado
        variavel = obj.variavel;
}

Reimplemented from TProcuraMelhorativa.

Definition at line 38 of file Particao.h.

Here is the call graph for this function:

◆ Copiar() [2/2]

void CParticao::Copiar ( TProcuraConstrutiva * objecto )

inline

Definition at line 24 of file Particao.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Cruzamento()

void CParticao::Cruzamento	(	TPonto	a,
		TPonto	b
	)

virtual

Reimplemented from TProcuraMelhorativa.

Definition at line 149 of file Particao.cpp.

Here is the call graph for this function:

◆ Debug() [1/2]

void CParticao::Debug ( void )

virtual

Mostra o estado no ecr�, para debug.

Note: Redefini��o opcional. Necess�rio para visualizar a procura, e explorar o espa�o manualmente.

Esta fun��o dever� mostrar claramente o estado atual, em texto mas da forma mais confort�vel poss�vel. O formato texto destina-se principalmente a quem implementa o problema, e n�o utilizadores finais. � importante poder explorar o espa�o de estados, para verificar a correta implementa��o dos sucessores, como tamb�m possa ver a �rvore de procura dos algoritmos, para �rvores pequenas, e assim detectar bugs.

Note: Antes de cada linha, chame a fun��o NovaLinha(). Dependendo do contexto, NovaLinha() pode imprimir caracteres que representam os ramos da �rvore de procura, criando uma visualiza��o textual que simula a estrutura da procura.; A exibi��o do estado pode variar conforme o n�vel de debug definido em parametro[nivelDebug].valor. Um n�vel menor pode mostrar informa��es mais sucintas, enquanto um n�vel maior pode detalhar todas as vari�veis do estado.

See also: NovaLinha()

void CSubProblema::Debug(void)
{
       NovaLinha();
    // neste exemplo o estado � apenas um n�mero
    if(parametro[nivelDebug].valor <= atividade)
           printf("--<([%d])>--", variavel); // vers�o compacta do estado
    else {
        // vers�o mais elaborada do estado
    }
}

Reimplemented from TProcura.

Definition at line 86 of file Particao.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Debug() [2/2]

void CParticao::Debug ( void )

virtual

Mostra o estado no ecr�, para debug.

Note: Redefini��o opcional. Necess�rio para visualizar a procura, e explorar o espa�o manualmente.

Esta fun��o dever� mostrar claramente o estado atual, em texto mas da forma mais confort�vel poss�vel. O formato texto destina-se principalmente a quem implementa o problema, e n�o utilizadores finais. � importante poder explorar o espa�o de estados, para verificar a correta implementa��o dos sucessores, como tamb�m possa ver a �rvore de procura dos algoritmos, para �rvores pequenas, e assim detectar bugs.

Note: Antes de cada linha, chame a fun��o NovaLinha(). Dependendo do contexto, NovaLinha() pode imprimir caracteres que representam os ramos da �rvore de procura, criando uma visualiza��o textual que simula a estrutura da procura.; A exibi��o do estado pode variar conforme o n�vel de debug definido em parametro[nivelDebug].valor. Um n�vel menor pode mostrar informa��es mais sucintas, enquanto um n�vel maior pode detalhar todas as vari�veis do estado.

See also: NovaLinha()

void CSubProblema::Debug(void)
{
       NovaLinha();
    // neste exemplo o estado � apenas um n�mero
    if(parametro[nivelDebug].valor <= atividade)
           printf("--<([%d])>--", variavel); // vers�o compacta do estado
    else {
        // vers�o mais elaborada do estado
    }
}

Reimplemented from TProcura.

◆ Distancia()

int CParticao::Distancia ( TPonto a )

virtual

Reimplemented from TProcuraMelhorativa.

Definition at line 159 of file Particao.cpp.

Here is the call graph for this function:

◆ Duplicar() [1/2]

TProcuraConstrutiva * CParticao::Duplicar ( void )

virtual

Cria um objecto que é uma cópia deste.

Note: Obrigatória a redefinição.

Este método tem de ser criado na subclasse, de modo a criar uma cópia do mesmo tipo. O código da subclasse geralmente segue um padrão e pode utilizar o modelo abaixo, aproveitando o método Copiar(). É especialmente útil na função de Sucessores(), na geração de um novo estado.

Returns: Retorna o novo estado, acabado de gerar.

Note: Caso exista falha de memória, colocar a variável memoriaEsgotada a true, para tentativa de terminar a execução de forma graciosa.

TNo CSubClasse::Duplicar(void)
{
    CSubClasse* clone = new CSubClasse;
       if(clone!=NULL)
           clone->Copiar(this);
       else
            memoriaEsgotada = true;
       return clone;
}

Implements TProcuraConstrutiva.

Definition at line 13 of file Particao.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Duplicar() [2/2]

TPonto CParticao::Duplicar ( void )

inlinevirtual

Cria um objecto que é uma cópia deste.

Note: Obrigatória a redefinição.

Este método tem de ser criado na subclasse, de modo a criar uma cópia do mesmo tipo. O código da subclasse geralmente segue um padrão e pode utilizar o modelo abaixo, aproveitando o método Copiar(). É especialmente útil na função de Sucessores(), na geração de um novo estado.

Returns: Retorna o novo estado, acabado de gerar.

Note: Caso exista falha de memória, colocar a variável memoriaEsgotada a true, para tentativa de terminar a execução de forma graciosa.

TNo CSubClasse::Duplicar(void)
{
    CSubClasse* clone = new CSubClasse;
       if(clone!=NULL)
           clone->Copiar(this);
       else
            memoriaEsgotada = true;
       return clone;
}

Implements TProcuraConstrutiva.

Definition at line 29 of file Particao.h.

Here is the call graph for this function:

◆ Inicializar() [1/2]

void CParticao::Inicializar ( void )

virtual

Coloca o objecto no estado inicial da procura.

Note: Obrigat�ria a redefini��o.

Este m�todo inicializa as vari�veis de estado no estado inicial vazio. Representa o estado inicial antes de qualquer a��o ser realizada na procura. Caso existam dados de inst�ncia, deve neste m�todo carregar a inst�ncia. A primeira instru��o dever� chamar o m�todo da superclasse, conforme modelo em baixo.

Note: A vari�vel instancia.valor, tem o ID da inst�ncia que deve ser carregada.

void CSubProblema::Inicializar(void)
{
    TProcura::Inicializar();
       // acertar as vari�veis est�ticas, com a inst�ncia (ID: instancia.valor)
       CarregaInstancia(); // exemplo de m�todo em CSubProblema para carregar uma inst�ncia
    // pode/deve utilizar vari�vel "ficheiroInstancia" concatenado com instancia.valor, com o ID da inst�ncia
    // inicializar todas as vari�veis de estado
       variavel = 0;
    // Determinar o tamanho m�ximo do estado codificado, se aplic�vel
       tamanhoCodificado = 1;
}

Reimplemented from TProcura.

Definition at line 23 of file Particao.cpp.

Here is the call graph for this function:

◆ Inicializar() [2/2]

void CParticao::Inicializar ( void )

virtual

Coloca o objecto no estado inicial da procura.

Note: Obrigat�ria a redefini��o.

Este m�todo inicializa as vari�veis de estado no estado inicial vazio. Representa o estado inicial antes de qualquer a��o ser realizada na procura. Caso existam dados de inst�ncia, deve neste m�todo carregar a inst�ncia. A primeira instru��o dever� chamar o m�todo da superclasse, conforme modelo em baixo.

Note: A vari�vel instancia.valor, tem o ID da inst�ncia que deve ser carregada.

void CSubProblema::Inicializar(void)
{
    TProcura::Inicializar();
       // acertar as vari�veis est�ticas, com a inst�ncia (ID: instancia.valor)
       CarregaInstancia(); // exemplo de m�todo em CSubProblema para carregar uma inst�ncia
    // pode/deve utilizar vari�vel "ficheiroInstancia" concatenado com instancia.valor, com o ID da inst�ncia
    // inicializar todas as vari�veis de estado
       variavel = 0;
    // Determinar o tamanho m�ximo do estado codificado, se aplic�vel
       tamanhoCodificado = 1;
}

Reimplemented from TProcura.

◆ MostrarSolucao() [1/2]

void CParticao::MostrarSolucao ( void )

inlinevirtual

definir para visualizar a solu��o

Reimplemented from TProcura.

Definition at line 38 of file Particao.h.

Here is the call graph for this function:

◆ MostrarSolucao() [2/2]

void CParticao::MostrarSolucao ( void )

inlinevirtual

definir para visualizar a solu��o

Reimplemented from TProcura.

Definition at line 49 of file Particao.h.

Here is the call graph for this function:

◆ Mutar()

void CParticao::Mutar ( void )

virtual

Reimplemented from TProcuraMelhorativa.

Definition at line 142 of file Particao.cpp.

Here is the call graph for this function:

◆ NovaSolucao()

void CParticao::NovaSolucao ( void )

virtual

Reimplemented from TProcuraMelhorativa.

Definition at line 114 of file Particao.cpp.

Here is the call graph for this function:

◆ ResetParametros()

void CParticao::ResetParametros ( )

virtual

Inicializa os parametros, indicadores e inst�ncias.

Note: Redefini��o necess�ria, para pelo menos indicar as inst�ncias existentes

Nesta fun��o, a primeira instru��o dever� ser a chamada da fun��o da superclasse, para que sejam criados os parametros da superclasse antes de qualquer outra instru��o.

Cada problema pode ter um algoritmo e configura��es padr�o que funcionam bem na maioria dos casos. Nesta fun��o, podem ser definidos estes valores de omiss�o.

Novos par�metros podem ser adicionados conforme necess�rio para atender �s particularidades do problema. Estes parametros podem depois ser selecionados ou inclu�dos num teste emp�rico, de modo a averiguar em fase de testes, qual a melhor configura��o, evitando escolhas arbitr�rias ou n�o fundamentadas.

Nesta fun��o deve ser redefinida a vari�vel com informa��o dos IDs das inst�ncias dispon�veis. Essa vari�vel � do tipo TParametro, mas n�o est� na lista de parametros, devendo ser inicializada aqui.

Existindo novos indicadores, devem ser adicionados aqui, e redefinida a fun��o Indicador() para calcular o valor.

Note: Na cria��o de um novo parametro, dar uma estrutura TParametro.; Ao adicionar novos par�metros, � recomend�vel manter a enumera��o sincronizada com a da superclasse. O primeiro elemento deve ser parametrosConstrutivos, garantindo que novas adi��es na superclasse sejam automaticamente refletidas aqui.; A inst�ncia selecionada ir� ser carregada em Inicializar(), utilizando o valor atual.

See also: TParametro

Exemplo com a altera��o do valor de omiss�o de um parametro, e adi��o de dois novos parametros.

// continua��o da enumera��o EParametrosProcujra
enum ESubProblema { opcaoHeur = parametrosProcura, opcaoSuc };
void CSubProblema::ResetParametros(void)
{
    static const char* nomesSuc[] = { "todas", "contributo" }; // nomes para os valores de opcaoSuc
    // chamar primeiro o m�todo na superclasse
    TProcura::ResetParametros();
    // neste exemplo considerou-se que se pretende ver algum debug, de omiss�o
    parametro[nivelDebug].valor = 1;
 
    // novo parametro para utilizar na fun��o Heuristica()
    parametro.Add({ "Op��o Heur�stica", 0,0,10,
        "explica��o do que acontece na heuristica, com este parametro entre 0 e 10",NULL });
    // novo parametro para utilizar na fun��o Sucessores()
    parametro.Add({ "Op��o Sucessores", 0,0,1,
        "0 gera todas as a��es; 1 gera apenas a��es que tenham um contributo para a solu��o.",nomesSuc });
 
    // novo indicador
    indicador.Add({ "Ordenado","verifica se um vetor est� ordenado", indOrdenar });
    indAtivo.Add(indOrdenar); // adicionar aos indicadores ativos de omiss�o
 
    // indicar que h� 10 inst�ncias, sendo a inst�ncia inicial a 1
       instancia = { "Problema", 1,1,10, "Caracter�sticas dos problemas", NULL };
}

Reimplemented from TProcura.

Definition at line 151 of file Particao.cpp.

Here is the call graph for this function:

◆ SolucaoCompleta()

bool CParticao::SolucaoCompleta ( void )

inlinevirtual

Verifica se o estado actual é objectivo (é uma solução completa)

Note: Obrigatória a redefinição.

Returns: Retorna verdadeiro se é um estado objetivo, ou falso caso contrário.

Este método verifica se o estado atual é objetivo, e portanto temos uma solução completa. A complexidade da verificação depende do problema, podendo ser um teste simples ou envolver múltiplas condições.

Note: Este método será chamado pelos algoritmos de procura no momento adequado, não necessariamente na geração de sucessores. Por isso, deve ser implementado separadamente de Sucessores(), garantindo que a avaliação do objetivo seja feita apenas quando necessário.

bool CSubProblema::SolucaoCompleta(void) {
    // pode ser um simples teste, ou algo mais complexo, dependente do problema
    // verificar se as condições pretendidas estão satisfeitas
    return variavel > 1000;
}

Reimplemented from TProcuraConstrutiva.

Definition at line 34 of file Particao.h.

Here is the call graph for this function:

◆ Sucessores()

void CParticao::Sucessores ( TVector< TNo > & sucessores )

virtual

Coloca em sucessores a lista de estados sucessores.

Note: Obrigatória a redefinição.

Parameters

sucessores - variável com a lista de estados sucessores a retornar.

Este é o método principal, que define a árvore de procura. Para o estado atual, duplicar o estado por cada ação / estado que seja sucessor. Alterar as variáveis de estado para corresponderem à ação efetuada no estado sucessor. Caso o custo não seja unitário, definir o custo da ação. Chamar o método da superclasse no final, já que irá atualizar estatísticas, bem como eliminar estados que sejam repetidos, dependendo da parametrização.

Note: O custo da ação deve ser definido aqui, mas ao chamar Sucessores() da superclasse, ele será acumulado para representar o custo total desde o estado inicial.; O método Duplicar() já coloca as variáveis de estado iguais ao estado atual. Apenas modifique as variáveis de estado que precisam refletir a ação i.; Caso seja feita uma verificação e a ação afinal não é válida, apagar o estado.; Não é preciso considerar estados repetidos, a verificação será feita na superclasse.

void CSubProblema::Sucessores(TVector<TNo>&sucessores)
{
    CSubProblema* novo;
    for(int i = 0; i < numeroAcoes; i++) {
        sucessores.Add(novo = (CSubProblema*)Duplicar());
        // aplicar a ação i nas variáveis de estado
        novo->variavel = i;
           // se o custo não for unitário, indicar o custo da ação
        novo->custo = 1 + i / 10;
        // Caso o estado gerado não seja válido, remova-o da lista e liberte a memória:
        if (!novo->EstadoValido()) // exemplo de método em CSubProblema para verificar a validade
            delete sucessores.Pop();
       }
    TProcuraConstrutiva::Sucessores(sucessores);
}

Reimplemented from TProcuraConstrutiva.

Definition at line 51 of file Particao.cpp.

Here is the call graph for this function:

◆ TesteManual()

void CParticao::TesteManual ( const char * nome )

virtual

Inicializa a intera��o com o utilizador.

Note: Redefini��o opcional

Esta fun��o arranca com o teste manual, orientada para o programador. A interface permite:

visualizar e trocar de inst�ncia
explorar o espa�o de estados nessa instancia, executando a��es
ver um caminho que esteja gravado (por explora��o manual ou por execu��o de um algoritmo)
ver e editar qualquer parametro de execu��o
o algoritmo � tamb�m um parametro, podendo naturalmente ser alterado
h� parametros sobre limites de execu��o, informa��o de debug, op��es de implementa��o e op��es de algoritmos
executar o algoritmo com a configura��o atual
adicionar a configura��o atual a um conjunto de configura��es de teste
executar um teste emp�rico, executando todas as configura��es de teste, no conjunto de inst�ncias selecionadas

Note: Esta fun��o deve ser o ponto de entrada, a executar no main, caso n�o se utilize a fun��o TProcura::main().

See also: TParametro, main

void CSubProblema::TesteManual(const char* nome)
{
     // a��es extra antes do teste manual, ou redefini��o completa;
       TProcura::TesteManual(nome); // chamada do m�todo da superclasse, caso n�o redefina por completo
}
 
// exemplo do main, sem processar argumentos (ver TProcura::main)
int main()
{
    CSubProblema problema;
    problema.TesteManual("CSubProblema");
}

Reimplemented from TProcura.

Definition at line 107 of file Particao.cpp.

Here is the call graph for this function:

◆ Vizinhanca()

void CParticao::Vizinhanca ( TVector< TPonto > & vizinhos )

virtual

Reimplemented from TProcuraMelhorativa.

Definition at line 132 of file Particao.cpp.

Here is the call graph for this function:

Member Data Documentation

◆ direita

TVector< int > CParticao::direita

Definition at line 19 of file Particao.h.

◆ esquerda

TVector< int > CParticao::esquerda

Definition at line 19 of file Particao.h.

◆ numeros

TVector< int > CParticao::numeros

Definition at line 19 of file Particao.h.

◆ solCompleta

TVector<bool> CParticao::solCompleta

Definition at line 25 of file Particao.h.

◆ totalDireita

int CParticao::totalDireita

Definition at line 20 of file Particao.h.

◆ totalEsquerda

int CParticao::totalEsquerda

Definition at line 20 of file Particao.h.

The documentation for this class was generated from the following files:

Construtiva/Teste/Particao.h
Melhorativa/Teste/Particao.h
Construtiva/Teste/Particao.cpp
Melhorativa/Teste/Particao.cpp

Public Member Functions

Public Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ CParticao() [1/2]

◆ ~CParticao() [1/2]

◆ CParticao() [2/2]

◆ ~CParticao() [2/2]

Member Function Documentation

◆ Acao()

◆ Avaliar()

◆ Codifica()

◆ Copiar() [1/2]

◆ Copiar() [2/2]

◆ Cruzamento()

◆ Debug() [1/2]

◆ Debug() [2/2]

◆ Distancia()

◆ Duplicar() [1/2]

◆ Duplicar() [2/2]

◆ Inicializar() [1/2]

◆ Inicializar() [2/2]

◆ MostrarSolucao() [1/2]

◆ MostrarSolucao() [2/2]

◆ Mutar()

◆ NovaSolucao()

◆ ResetParametros()

◆ SolucaoCompleta()

◆ Sucessores()

◆ TesteManual()

◆ Vizinhanca()

Member Data Documentation

◆ direita

◆ esquerda

◆ numeros

◆ solCompleta

◆ totalDireita

◆ totalEsquerda