Representa um estado no espaço de estados. More...

#include <TProcuraAdversa.h>

Inheritance diagram for TProcuraAdversa:

Collaboration diagram for TProcuraAdversa:

Public Member Functions
	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)

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 TNo	Duplicar (void)=0
	Cria um objecto que é uma cópia deste.

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

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

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

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

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 void	Codifica (uint64_t estado[OBJETO_HASHTABLE])
	Codifica o estado para um vetor de inteiros de 64 bits.

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 void	Debug (void)
	Mostra o estado no ecr�, para debug.

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

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

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

void	MostrarCaminho ()

unsigned int	Hash ()

void	LimparHT ()

bool	ExisteHT ()

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 Attributes
int	indiceHT

Static Protected Attributes
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

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 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.

Detailed Description

Representa um estado no espaço de estados.

Esta classe base deve ser redefinida com um problema concreto, permitindo a execução de procuras adversas.

Definition at line 45 of file TProcuraAdversa.h.

Constructor & Destructor Documentation

◆ TProcuraAdversa()

TProcuraAdversa::TProcuraAdversa ( void )

Definition at line 17 of file TProcuraAdversa.cpp.

◆ ~TProcuraAdversa()

TProcuraAdversa::~TProcuraAdversa ( void )

Definition at line 22 of file TProcuraAdversa.cpp.

Member Function Documentation

◆ CorteAlfaBeta()

bool TProcuraAdversa::CorteAlfaBeta	(	int	valor,
		int &	alfa,
		int &	beta
	)

protected

verifica se há um corte alfa/beta, atualizando alfa e beta

Definition at line 348 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ExecutaAlgoritmo()

int TProcuraAdversa::ExecutaAlgoritmo ( )

virtual

Executa o algoritmo com os parametros atuais.

Reimplemented from TProcura.

Definition at line 491 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ExisteHeuritica()

bool TProcuraAdversa::ExisteHeuritica ( void )

Definition at line 124 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ExisteHT()

bool TProcuraAdversa::ExisteHT ( )

protected

Definition at line 517 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Heuristica()

int TProcuraAdversa::Heuristica ( void )

virtual

chamar após calcular a heurística (grava o valor, dependendo da parametrização)

Reimplemented from TProcuraConstrutiva.

Definition at line 114 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ MaiorAmeaca()

int TProcuraAdversa::MaiorAmeaca	(	TVector< int > &	qMin,
		TVector< int > &	qMax,
		int	maxAmeaca
	)

Utilitário para calculo de uma heurística standard em jogos simples.

calcular o número de ameaças de vitória, para cada lado, de menor comprimento:

qMin - vetor com número de ameaças (1 ou mais) a 1 jogada (na primeira posição), a 2 (na segunda posição), e assim sucessivamente;
qMax - vetor com número de ameaças (1 ou mais) a 1 jogada (na primeira posição), a 2 (na segunda posição), e assim sucessivamente;

Definition at line 209 of file TProcuraAdversa.cpp.

Here is the caller graph for this function:

◆ MetodoIterativo()

int TProcuraAdversa::MetodoIterativo ( int alfaBeta )

protected

iteração, aumentando o nível progressivamente

Definition at line 176 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ MiniMax()

int TProcuraAdversa::MiniMax ( int nivel = 4 )

retorna o valor do estado actual, apos procura de profundidade nivel

Definition at line 50 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ MiniMaxAlfaBeta()

int TProcuraAdversa::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

Definition at line 272 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ NoFolha()

int TProcuraAdversa::NoFolha ( bool nivel )

protected

fim da procura, por corte de nível (ou não haver sucessores), retornar heurística

Definition at line 240 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ OrdenarSucessores()

void TProcuraAdversa::OrdenarSucessores	(	TVector< TNo > &	sucessores,
		TVector< int > &	id,
		int	nivel
	)

protected

Definition at line 133 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ResetParametros()

void TProcuraAdversa::ResetParametros ( )

virtual

Método para inicializar os parâmetros (redefinir se forem adicionados parâmetros específicos)

Reimplemented from TProcura.

Definition at line 26 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ SubstituirHT()

void TProcuraAdversa::SubstituirHT ( int indice )

protectedvirtual

Reimplemented from TProcuraConstrutiva.

Definition at line 512 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ TesteEmpirico()

void TProcuraAdversa::TesteEmpirico	(	int	inicio = `-1`,
		int	fim = `-1`,
		bool	mostrarSolucoes = `true`
	)

Definition at line 391 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

◆ Utilizavel()

bool TProcuraAdversa::Utilizavel	(	TValorEstado &	valor,
		int	nivel,
		int	alfa,
		int	beta
	)

protected

ver se o valor obtido é utilizável no contexto atual

Definition at line 339 of file TProcuraAdversa.cpp.

Here is the caller graph for this function:

◆ ValorEstado()

bool TProcuraAdversa::ValorEstado	(	TValorEstado &	valor,
		int	operacao
	)

protected

ler ou gravar o melhor valor conhecido

Definition at line 535 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

◆ completo

bool TProcuraAdversa::completo

static

controlo para indicar se a procura foi realizada de forma completa (c.c. foi cortada)

Definition at line 57 of file TProcuraAdversa.h.

◆ indiceHT

int TProcuraAdversa::indiceHT

protected

Definition at line 113 of file TProcuraAdversa.h.

◆ infinito

int TProcuraAdversa::infinito = 1000

static

valor de infinito (vitoria/derrota), omissao 1000

Definition at line 55 of file TProcuraAdversa.h.

◆ minimizar

bool TProcuraAdversa::minimizar

o jogador actual deve minimizar o custo (ou maximizar caso tenha o valor falso)

Definition at line 53 of file TProcuraAdversa.h.

◆ nivelOK

int TProcuraAdversa::nivelOK = 0

static

profundidade máxima no método iterativo

Definition at line 59 of file TProcuraAdversa.h.

◆ reutilizadoAvaliacao

int TProcuraAdversa::reutilizadoAvaliacao

staticprotected

Definition at line 119 of file TProcuraAdversa.h.

◆ valorHT

TValorEstado TProcuraAdversa::valorHT

staticprotected

Definition at line 111 of file TProcuraAdversa.h.

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

Adversa/TProcuraAdversa.h
Adversa/TProcuraAdversa.cpp

Public Member Functions

Public Attributes

Static Public Attributes

Protected Member Functions

Protected Attributes

Static Protected Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ TProcuraAdversa()

◆ ~TProcuraAdversa()

Member Function Documentation

◆ CorteAlfaBeta()

◆ ExecutaAlgoritmo()

◆ ExisteHeuritica()

◆ ExisteHT()

◆ Heuristica()

◆ MaiorAmeaca()

◆ MetodoIterativo()

◆ MiniMax()

◆ MiniMaxAlfaBeta()

◆ NoFolha()

◆ OrdenarSucessores()

◆ ResetParametros()

◆ SubstituirHT()

◆ TesteEmpirico()

◆ Utilizavel()

◆ ValorEstado()

Member Data Documentation

◆ completo

◆ indiceHT

◆ infinito

◆ minimizar

◆ nivelOK

◆ reutilizadoAvaliacao

◆ valorHT