Métodos para redefinir, sugeridos

Functions
virtual const char *	TProcuraConstrutiva::Acao (TNo sucessor)
	Retorna a ação (movimento, passo, jogada, lance, etc.) que gerou o sucessor.
virtual void	TProcuraConstrutiva::Codifica (uint64_t estado[OBJETO_HASHTABLE])
	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.
virtual void	TProcuraConstrutiva::Debug (void)
	Mostra o estado no ecrã, para debug.
virtual void	TProcuraConstrutiva::ResetParametros ()
	Inicializa os parametros.

Detailed Description

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

Function Documentation

Acao()

virtual const char * 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 452 of file TProcuraConstrutiva.h.

Here is the caller graph for this function:

Codifica()

void TProcuraConstrutiva::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

SolucaoVazia()

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 in CJogoDoGalo, and CJogoEmLinha.

Definition at line 1371 of file TProcuraConstrutiva.cpp.

Here is the caller graph for this function:

Debug()

void TProcuraConstrutiva::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 in CJogoDoGalo, and CJogoEmLinha.

Definition at line 558 of file TProcuraConstrutiva.cpp.

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 parametros para que a heurística possa ser calculada de acordo com o parametro 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, and TProcuraAdversa.

Definition at line 546 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

ResetParametros()

void TProcuraConstrutiva::ResetParametros ( )

virtual

Inicializa os parametros.

Note

Redefinição necessária se forem adicionados novos parametros, ou for alterado o valor de omissão de parametros 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, que se não forem alterados, irá executar a configuração mais genérica.

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.

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.

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 EParametrosConstrutiva
enum ESubProblema { opcaoHeur = parametrosConstrutivas, opcaoSuc };
void CSubProblema::ResetParametros(void)
{
    static const char* nomesSuc[] = { "todas", "contributo" }; // nomes para os valores de opcaoSuc
    // chamar primeiro o método na superclasse
    TProcuraConstrutiva::ResetParametros();
    // neste exemplo considerou-se que se pretende ver apenas estados completos, ignorando ações
    parametro[verAcoes].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 });
}

Reimplemented in CJogoEmLinha, and TProcuraAdversa.

Definition at line 50 of file TProcuraConstrutiva.cpp.

Here is the call graph for this function:

Here is the caller graph for this function: