Métodos para redefinir mandatórios

Functions
virtual TNo	TProcuraConstrutiva::Duplicar (void)=0
	Cria um objecto que é uma cópia deste.
virtual void	TProcuraConstrutiva::Copiar (TNo objecto)
	Fica com uma cópia do objecto.
void	TProcuraConstrutiva::Inicializar (void) override
	Coloca o objecto no estado inicial da procura.
virtual void	TProcuraConstrutiva::Sucessores (TVector< TNo > &sucessores)
	Coloca em sucessores a lista de estados sucessores.
virtual bool	TProcuraConstrutiva::SolucaoCompleta (void)
	Verifica se o estado actual é objectivo (é uma solução completa)
void	TProcuraConstrutiva::ResetParametros () override
	Redefinição. Ver TProcura::ResetParametros().

Detailed Description

Métodos de redefinição obrigatória no problema

Function Documentation

Copiar()

virtual void TProcuraConstrutiva::Copiar ( TNo  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(TNo objecto) {
        CSubProblema& obj = *((CSubProblema*)objecto);
        // copiar todas as variáveis do estado
        variavel = obj.variavel;
}

Reimplemented in CProblemaArtificial.

Definition at line 197 of file TProcuraConstrutiva.h.

Here is the caller graph for this function:

Duplicar()

virtual TNo TProcuraConstrutiva::Duplicar ( void  )

pure 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;
}

Implemented in CJogoDoGalo, CJogoEmLinha, CAspirador, COitoDamas, CParticao, CProblemaArtificial, CPuzzle8, COitoDamas, CParticao, and CProblemaArtificial.

Here is the caller graph for this function:

Inicializar()

void TProcuraConstrutiva::Inicializar ( void  )

inlineoverridevirtual

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.

Se a função Codifica() estiver implementada, o tamanho do estado codificado deve ser determinado após o carregamento da instância, pois diferentes instâncias podem exigir tamanhos distintos.

See also

Codifica()

void CSubProblema::Inicializar(void)
{
    TProcuraConstrutiva::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
    // inicializar todas as variáveis de estado
       variavel = 0;
    // Determinar o tamanho máximo do estado codificado, se aplicável
       tamanhoCodificado = 1;
}

Redefinição. Ver TProcura::Inicializar().

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.

Note

Se a função Codifica() estiver implementada, o tamanho do estado codificado deve ser determinado após o carregamento da instância, pois diferentes instâncias podem exigir tamanhos distintos.

See also

Codifica()

Reimplemented from TProcura.

Definition at line 242 of file TProcuraConstrutiva.h.

Here is the call graph for this function:

Here is the caller graph for this function:

ResetParametros()

void TProcuraConstrutiva::ResetParametros ( )

overridevirtual

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

Reimplemented from TProcura.

Definition at line 39 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

SolucaoCompleta()

virtual bool TProcuraConstrutiva::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 in CJogoDoGalo, CJogoEmLinha, CAspirador, COitoDamas, CParticao, CProblemaArtificial, CPuzzle8, and COitoDamas.

Definition at line 305 of file TProcuraConstrutiva.h.

Here is the caller graph for this function:

Sucessores()

void TProcuraConstrutiva::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 in CJogoDoGalo, CJogoEmLinha, CAspirador, COitoDamas, CParticao, CProblemaArtificial, and CPuzzle8.

Definition at line 103 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function: