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

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

virtual void	SolucaoVazia (void)
	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)

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

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

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
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 TParametro	instancia = { NULL,1,1,1, NULL, NULL }
	ID da instância atual, a ser utilizado em SolucaoVazia().

static TVector< TParametro >	parametro
	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< TNo >	caminho
	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

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	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
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 int	NovoValor (const char *prompt)

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

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 call graph for this function:

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

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`
	)

virtual

Executa testes empíricos, em todas as configurações guardadas, nas instâncias selecionadas.

Note: Redefinição não é necessária

Parameters

inicio	- ID da primeira instância no teste (ou -1 para a primeira)
fim	- ID da última instância no teste (ou -1 para a última)
mostrarSolucoes	- se true, mostra a solução após cada execução, c.c. indica apenas a instância em processamento.

Esta função é chamada de TesteManual() para executar testes empíricos. A função apresenta-se como método virtual, atendendo a que será redefinida nas procuras adversas. É genérica e não se prevê outras situações que seja necessário redefini-la.

Note: Pode ser chamada diretamente do código, e nesse caso é necessário que a variável estática 'configuracoes' tenha as configurações em teste. Se configuracoes estiver vazia, o teste empírico será executado apenas com a configuração atual, avaliando seu desempenho isoladamente, sem comparação com outras configurações.

See also: TesteManual()

Reimplemented from TProcuraConstrutiva.

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:

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