Métodos para redefinir, sugeridos

Functions
virtual TString	TProcuraConstrutiva::Acao (TNo sucessor)
	Retorna a ação (movimento, passo, jogada, lance, etc.) que gerou o sucessor.
virtual void	TProcuraConstrutiva::Codifica (TBits &estado)
	Codifica o estado para um vetor de inteiros de 64 bits.
virtual int	TProcuraConstrutiva::Heuristica (void)
	Função para calcular quanto falta para o final, o valor da heurística.

Detailed Description

Métodos de redefinição aconselhados a uma boa implementação

Function Documentation

Acao()

virtual TString TProcuraConstrutiva::Acao ( TNo  sucessor )

inlinevirtual

Retorna a ação (movimento, passo, jogada, lance, etc.) que gerou o sucessor.

Note

Redefinição opcional.

Parameters

sucessor

- estado filho deste, cuja ação deve ser identificada

Returns

texto identificando a ação, pode ser uma constante

Este método não é crítico, mas é importante para se poder visualizar ações. Se este método não for redefinido, a interface mostrará apenas os estados completos, sem detalhar as ações que os geraram.

Durante a exploração manual do espaço de estados, permitir que ações sejam fornecidas diretamente, ao invés de depender do ID do sucessor, facilita testes e integração com outros sistemas. Esta situação é vantajosa, para permitir introduzir uma sequência de ações, que eventualmente venha de outro programa, permitindo assim a validação da solução.

const char* CSubProblema::Acao(TNo sucessor) {
    CSubProblema& filho = *((CSubProblema*)sucessor);
    // determinar pela diferença das variáveis de estado, a ação
    // exemplo de ações hipotéticas de manter, incrementar ou decrementar o valor da variável
    if(variavel == filho.variavel)
        return "manter";
    if(variavel == filho.variavel + 1)
        return "inc";
    if(variavel == filho.variavel - 1)
        return "dec";
    return "Inválida";
}

Reimplemented in CJogoEmLinha.

Definition at line 352 of file TProcuraConstrutiva.h.

Here is the caller graph for this function:

Codifica()

void TProcuraConstrutiva::Codifica ( TBits &  estado )

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(TBits estado)
{
    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 in CJogoDoGalo, CJogoEmLinha, CAspirador, COitoDamas, CParticao, and CPuzzle8.

Definition at line 1024 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Heuristica()

int TProcuraConstrutiva::Heuristica ( void  )

virtual

Função para calcular quanto falta para o final, o valor da heurística.

Note

Redefinição opcional. Necessário para utilizar os algoritmos informados.

Returns

Retorna a melhor estimativa, sem ultrapassar a real, do custo do estado atual até ao objetivo.

A função heurística é crítica para utilizar os algoritmos informados. Deve devolver uma estimativa sem ultrapassar o custo real, do custo que falta para atingir o estado objetivo mais próximo do estado atual. Se a estimativa não ultrapassar o custo real, a heurística será admissível. No entanto, em alguns casos, heurísticas não admissíveis podem ser utilizadas, podendo acelerar a procura, mesmo que ocasionalmente levem a resultados subótimos.

No final, chame a função heurística da superclasse para atualizar as estatísticas e o número de avaliações. Se estiver configurado, esse processo também pode introduzir ruído na heurística, o que pode impactar certos algoritmos de procura.

Esta função pretende-se rápida, e o mais próxima possível do valor real, sem ultrapassar.

Note

Num problema, existindo alternativas, umas mais rápidas menos precisas, outras mais lentas mais precisas, é aconselhada a criação de um ou mais parâmetros para que a heurística possa ser calculada de acordo com o parâmetro definido. Em fase de testes logo se averigua qual a versão que adiciona mais vantagem à procura.

Uma heurística pode resultar de um relaxamento do problema. Verifique se o problema sem uma das restrições (fazendo batota), se consegue resolver mais facilmente. Utilize como heurística o custo de resolver o problema sem essa restrição.

void CSubProblema::Heuristica(void)
{
    heuristica = 0; // ponto de partida, há 0 de custo
    // utilizar neste exemplo a distância até 1000, local onde estará o objetivo
    heuristica = abs(variavel - 1000);
    // chamar a função heurística da superclass
    return TProcuraConstrutiva::Heuristica();
}

Reimplemented in CJogoDoGalo, CJogoEmLinha, TProcuraAdversa, CAspirador, and CPuzzle8.

Definition at line 622 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function: