TProcuraAdversa
Algoritmos de procura adversa
Loading...
Searching...
No Matches
CJogoEmLinha Class Reference

#include <JogoEmLinha.h>

Inheritance diagram for CJogoEmLinha:
Collaboration diagram for CJogoEmLinha:

Public Member Functions

 CJogoEmLinha (void)
 
 ~CJogoEmLinha (void)
 
TProcuraConstrutivaDuplicar (void)
 Cria um objecto que é uma cópia deste.
 
void Copiar (TProcuraConstrutiva *objecto)
 
void SolucaoVazia (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 ResetParametros ()
 Inicializa os parametros.
 
int Heuristica (void)
 Função para calcular quanto falta para o final, o valor da heurística.
 
const char * Acao (TNo sucessor)
 Retorna a ação (movimento, passo, jogada, lance, etc.) que gerou o sucessor.
 
void TesteManual (const char *nome)
 Inicializa a interação com o utilizador.
 
void Codifica (uint64_t estado[OBJETO_HASHTABLE])
 Codifica o estado para um vetor de inteiros de 64 bits.
 
int Codigo (char peca)
 
int Indice (int i, int j)
 
char Casa (int i, int j)
 
void Casa (int i, int j, char valor)
 
bool VerLinha (int i, int j, int di, int dj)
 
- Public Member Functions inherited from TProcuraAdversa
 TProcuraAdversa (void)
 
 ~TProcuraAdversa (void)
 
void ResetParametros ()
 Método para inicializar os parâmetros (redefinir se forem adicionados parâmetros específicos)
 
int MiniMax (int nivel=4)
 retorna o valor do estado actual, apos procura de profundidade nivel
 
int MiniMaxAlfaBeta (int nivel=4, int alfa=-infinito, int beta=+infinito)
 retorna o valor do estado actual, apos procura de profundidade nivel. Idêntico a MiniMax
 
void TesteEmpirico (int inicio=-1, int fim=-1, bool mostrarSolucoes=true)
 Executa testes empíricos, em todas as configurações guardadas, nas instâncias selecionadas.
 
int ExecutaAlgoritmo ()
 Executa o algoritmo com os parametros atuais.
 
int Heuristica (void)
 chamar após calcular a heurística (grava o valor, dependendo da parametrização)
 
bool ExisteHeuritica (void)
 
int MaiorAmeaca (TVector< int > &qMin, TVector< int > &qMax, int maxAmeaca)
 Utilitário para calculo de uma heurística standard em jogos simples.
 
- Public Member Functions inherited from TProcuraConstrutiva
 TProcuraConstrutiva (void)
 
virtual ~TProcuraConstrutiva (void)
 
virtual void Copiar (TNo objecto)
 Fica com uma cópia do objecto.
 
virtual bool Acao (const char *acao)
 Executa a ação (movimento, passo, jogada, lance, etc.) no estado atual.
 
virtual bool Parar (void)
 Verifica se a procura deve ser interrompida.
 
virtual bool Distinto (TNo estado)
 Verifica se o estado actual distinto do fornecido.
 
virtual void MostrarSolucao (void)
 Mostrar solução, seja um caminho ou o próprio estado.
 
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)
 
void FinalizarCorrida (clock_t inicio)
 
int LowerBound ()
 
void NovaLinha (bool tudo=true)
 

Public Attributes

TVector< char > tabuleiro
 
- Public Attributes inherited from TProcuraAdversa
bool minimizar
 o jogador actual deve minimizar o custo (ou maximizar caso tenha o valor falso)
 
- 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.
 

Static Public Attributes

static TJogoEmLinha inst = { 3,3,3,regular }
 
- Static Public Attributes inherited from TProcuraAdversa
static int infinito = 1000
 valor de infinito (vitoria/derrota), omissao 1000
 
static bool completo
 controlo para indicar se a procura foi realizada de forma completa (c.c. foi cortada)
 
static int nivelOK = 0
 profundidade máxima no método iterativo
 
- Static Public Attributes inherited from TProcuraConstrutiva
static TParametro instancia = { NULL,1,1,1, NULL, NULL }
 ID da instância atual, a ser utilizado em SolucaoVazia().
 
static TVector< TParametroparametro
 Parâmetros a serem utilizados na configuração atual.
 
static TVector< TVector< int > > configuracoes
 Conjuntos de configurações para teste empírico.
 
static int geracoes = 0
 Número total de gerações realizadas na procura.
 
static int expansoes =0
 Número total de expansões realizadas na procura.
 
static int avaliacoes =0
 Número total de avaliações realizadas na procura.
 
static TVector< TNocaminho
 Solução retornada pela procura (os estados devem ser libertados).
 
static bool memoriaEsgotada = false
 Flag indicando problemas de memória esgotada.
 
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 TVector< unsigned char > ramo
 
static int espacosRamo =2
 
static clock_t instanteFinal = 0
 

Additional Inherited Members

- Static Public Member Functions inherited from TProcuraConstrutiva
static void LibertarVector (TVector< TNo > &vector, int excepto=-1, int maiorQue=-1)
 
static int NovoValor (const char *prompt)
 
- Protected Member Functions inherited from TProcuraAdversa
int NoFolha (bool nivel)
 fim da procura, por corte de nível (ou não haver sucessores), retornar heurística
 
bool CorteAlfaBeta (int valor, int &alfa, int &beta)
 verifica se há um corte alfa/beta, atualizando alfa e beta
 
int MetodoIterativo (int alfaBeta)
 iteração, aumentando o nível progressivamente
 
void OrdenarSucessores (TVector< TNo > &sucessores, TVector< int > &id, int nivel)
 
void SubstituirHT (int indice)
 
bool ExisteHT ()
 
bool ValorEstado (TValorEstado &valor, int operacao)
 ler ou gravar o melhor valor conhecido
 
bool Utilizavel (TValorEstado &valor, int nivel, int alfa, int beta)
 ver se o valor obtido é utilizável no contexto atual
 
- 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 ExplorarSucessores (bool jogo=false)
 
void EditarParametros ()
 
void EditarConfiguracoes ()
 
void MostrarConfiguracoes (int detalhe, int atual=-1)
 
void SolicitaInstancia ()
 
bool TempoExcedido ()
 
bool GeracoesExcedido ()
 
bool ExpansoesExcedido ()
 
bool AvaliacoesExcedido ()
 
void MostrarCaminho ()
 
void MostraParametros (int detalhe=1, TVector< int > *idParametros=NULL)
 
void MostraRelatorio (TVector< TResultado > &resultados)
 
int Dominio (int &variavel, int min=INT_MIN, int max=INT_MAX)
 
void ConfiguracaoAtual (TVector< int > &parametros, int operacao)
 
int MelhorResultado (TResultado base, TResultado alternativa)
 
void CalculaTorneio (TVector< TResultado > &resultados)
 
void MostrarTorneio (TVector< TVector< int > > &torneio, bool jogo=false)
 
void BarraTorneio (bool nomes)
 
void ExtrairConfiguracao (TVector< TResultado > &resultados, TVector< TResultado > &extracao, int configuracao)
 
unsigned int Hash ()
 
void LimparHT ()
 
bool ExisteHT ()
 
- Protected Attributes inherited from TProcuraAdversa
int indiceHT
 
- Static Protected Attributes inherited from TProcuraAdversa
static TValorEstado valorHT [TAMANHO_HASHTABLE]
 
static int reutilizadoAvaliacao
 
- 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

Definition at line 27 of file JogoEmLinha.h.

Constructor & Destructor Documentation

◆ CJogoEmLinha()

CJogoEmLinha::CJogoEmLinha ( void  )

Definition at line 7 of file JogoEmLinha.cpp.

Here is the caller graph for this function:

◆ ~CJogoEmLinha()

CJogoEmLinha::~CJogoEmLinha ( void  )

Definition at line 11 of file JogoEmLinha.cpp.

Member Function Documentation

◆ Acao()

const char * CJogoEmLinha::Acao ( TNo  sucessor)
virtual

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";
}
Representa um estado no espaço de estados.

Reimplemented from TProcuraConstrutiva.

Definition at line 159 of file JogoEmLinha.cpp.

◆ Casa() [1/2]

char CJogoEmLinha::Casa ( int  i,
int  j 
)
inline

Definition at line 69 of file JogoEmLinha.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ Casa() [2/2]

void CJogoEmLinha::Casa ( int  i,
int  j,
char  valor 
)
inline

Definition at line 70 of file JogoEmLinha.h.

Here is the call graph for this function:

◆ Codifica()

void CJogoEmLinha::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);
}
#define OBJETO_HASHTABLE
virtual void Codifica(uint64_t estado[OBJETO_HASHTABLE])
Codifica o estado para um vetor de inteiros de 64 bits.

Reimplemented from TProcuraConstrutiva.

Definition at line 182 of file JogoEmLinha.cpp.

Here is the call graph for this function:

◆ Codigo()

int CJogoEmLinha::Codigo ( char  peca)
inline

Definition at line 67 of file JogoEmLinha.h.

Here is the caller graph for this function:

◆ Copiar()

void CJogoEmLinha::Copiar ( TProcuraConstrutiva objecto)

Definition at line 27 of file JogoEmLinha.cpp.

Here is the caller graph for this function:

◆ Debug()

void CJogoEmLinha::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)
{
// neste exemplo o estado é apenas um número
printf("--<([%d])>--", variavel); // versão compacta do estado
else {
// versão mais elaborada do estado
}
}
@ nivelDebug
Nível de debug, de reduzido a completo.
@ atividade
Apenas eventos principais.
void NovaLinha(bool tudo=true)
static TVector< TParametro > parametro
Parâmetros a serem utilizados na configuração atual.

Reimplemented from TProcuraConstrutiva.

Definition at line 130 of file JogoEmLinha.cpp.

Here is the call graph for this function:

◆ Duplicar()

TProcuraConstrutiva * CJogoEmLinha::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
return clone;
}
virtual void Copiar(TNo objecto)
Fica com uma cópia do objecto.
static bool memoriaEsgotada
Flag indicando problemas de memória esgotada.

Implements TProcuraConstrutiva.

Definition at line 16 of file JogoEmLinha.cpp.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ Heuristica()

int CJogoEmLinha::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
}
virtual int Heuristica(void)
Função para calcular quanto falta para o final, o valor da heurística.
int heuristica
Estimativa para o custo até um estado objetivo, se disponível.

Reimplemented from TProcuraConstrutiva.

Definition at line 190 of file JogoEmLinha.cpp.

Here is the call graph for this function:

◆ Indice()

int CJogoEmLinha::Indice ( int  i,
int  j 
)
inline

Definition at line 68 of file JogoEmLinha.h.

Here is the caller graph for this function:

◆ ResetParametros()

void CJogoEmLinha::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
// 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 });
}
@ verAcoes
Mostra estado a cada K ações. Se 1, mostra sempre estados e nunca ações.
@ parametrosConstrutivas
Marcador para permitir a extensão do enum em subclasses.
virtual void ResetParametros()
Inicializa os parametros.

Reimplemented from TProcuraConstrutiva.

Definition at line 154 of file JogoEmLinha.cpp.

Here is the call graph for this function:

◆ SolucaoCompleta()

bool CJogoEmLinha::SolucaoCompleta ( void  )
virtual

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 105 of file JogoEmLinha.cpp.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ SolucaoVazia()

void CJogoEmLinha::SolucaoVazia ( 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.
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::SolucaoVazia(void)
{
// 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
}
virtual void SolucaoVazia(void)
Coloca o objecto no estado inicial da procura.
static int tamanhoCodificado
Número de inteiros de 64 bits utilizados para codificar um objeto (≤ OBJETO_HASHTABLE).

Reimplemented from TProcuraConstrutiva.

Definition at line 34 of file JogoEmLinha.cpp.

Here is the call graph for this function:

◆ Sucessores()

void CJogoEmLinha::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 * Duplicar(void)
Cria um objecto que é uma cópia deste.
void Add(Item a)
Definition TVector.h:54
Item & Pop()
Definition TVector.h:61
virtual void Sucessores(TVector< TNo > &sucessores)
Coloca em sucessores a lista de estados sucessores.

Reimplemented from TProcuraConstrutiva.

Definition at line 61 of file JogoEmLinha.cpp.

Here is the call graph for this function:

◆ TesteManual()

void CJogoEmLinha::TesteManual ( const char *  nome)
virtual

Inicializa a interação com o utilizador.

Note
Redefinição necessária para definir as instancias existentes.

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

Esta função deve ser redefinida para inicializar 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.

Note
A instância selecionada irá ser carregada em SolucaoVazia(), utilizando o valor atual.
Esta função deve ser o ponto de entrada, a executar no main.
See also
TParametro
void CSubProblema::TesteManual(const char* nome)
{
// indicar que há 10 instâncias, sendo a instância inicial a 1
instancia = { "Problema", 1,1,10, "Características dos problemas", NULL };
}
// exemplo do main
int main()
{
CSubProblema problema;
problema.TesteManual("CSubProblema");
}
virtual void TesteManual(const char *nome)
Inicializa a interação com o utilizador.
static TParametro instancia
ID da instância atual, a ser utilizado em SolucaoVazia().
int main(int argc, char *argv[])
Definition teste.cpp:11

Reimplemented from TProcuraConstrutiva.

Definition at line 176 of file JogoEmLinha.cpp.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ VerLinha()

bool CJogoEmLinha::VerLinha ( int  i,
int  j,
int  di,
int  dj 
)

Definition at line 79 of file JogoEmLinha.cpp.

Here is the call graph for this function:
Here is the caller graph for this function:

Member Data Documentation

◆ inst

TJogoEmLinha CJogoEmLinha::inst = { 3,3,3,regular }
static

Definition at line 5 of file JogoEmLinha.h.

◆ tabuleiro

TVector<char> CJogoEmLinha::tabuleiro

Definition at line 31 of file JogoEmLinha.h.


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