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)

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

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 (TVector< int > instancias, TString ficheiro="") override
	Executa testes empíricos, em todas as configurações guardadas, nas instâncias selecionadas.

void	TesteEmpiricoGestor (TVector< int > instancias, TString ficheiro="") override
	Teste empírico com modo mestre-escravo (este é o mestre)

void	TesteEmpiricoTrabalhador (TVector< int > instancias, TString ficheiro="") override
	Teste empírico com modo mestre-escravo (este é o escravo)

void	TesteValidacao (TVector< int > instancias, TVector< int > impossiveis, TVector< int > referencias, TString fichSolucoes, TString fichResultados="") override
	Executa testes de validação, executando cada solução na instância respetiva, e verificando a sua validade bem como características.

bool	Validar (TVector< TString > solucao) override
	Verifica a validade de uma solução para a instância atual.

TString	Jogar (TString jogo, int configID)

void	PontuacaoJogos (TVector< TString > &jogos)

bool	CoerenciaJogo (TVector< TString > &jogos, TVector< TString > &anterior)

void	JogoTerminado (TString &jogo)

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)

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

int	MaiorAmeaca (TVector< int > &qMin, TVector< int > &qMax, int maxAmeaca) const
	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.

void	ResetParametros () override
	Redefinição. Ver TProcura::ResetParametros().

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

virtual void	Codifica (TBits &estado)
	Codifica o estado para um vetor de inteiros de 64 bits.

virtual bool	Acao (TString 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.

TVector< TString >	Solucao ()
	retorna uma solução no formato do TResultado, para ser gravada em ficheiro de soluções, ou visualizada (pode ser utilizada para mostrar a solução, ou para gravar a solução num formato mais legível)

int	ExecutaAlgoritmo ()
	Executa o algoritmo com os parâmetros atuais.

int64_t	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 () override
	Chamar antes da execução do algoritmo. Limpa valores estatísticos, e fixa o instante limite de tempo para a execução.

void	ExecucaoTerminada () 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	Gravar (void)

virtual void	Debug (bool completo=true)
	Mostra o estado no ecrã, para debug.

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

virtual void	TesteManual (TString nome)
	Inicializa a interação com o utilizador.

virtual void	RelatorioValidacao (TVector< TResultado > resultados, TVector< int > referencias)

virtual void	main (int argc, char *argv[], TString nome)
	Inicializa a interação com o utilizador.

virtual TVector< int64_t >	CodificarSolucao ()
	retorna um vetor de inteiros com a codificação da solução (esta codificação será adicionada aos indicadores, no ficheiro CSV de resultados)

bool	TempoExcedido ()

bool	IteracoesExcedido ()

int	Parametro (int id) const

int &	Parametro (int id)

bool	ParametroAtivo (int id, TVector< int > *valores=NULL) const

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 = NULL
	Ponteiro para o estado pai, na árvore de procura.

int	custo = 1
	Custo total acumulado desde o estado inicial.

int	heuristica = 0
	Estimativa para o custo até um estado objetivo, se disponível.

int	debugID = 0
	ID do estado, para efeitos de debug.

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 int	resultadoCompleto = 0
	resultado após SolucaoCompleta() retornar true (-1 vitória minimizar, 0 empate, 1 vitória maximizar)

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	expansoes = 0
	Número de expansões efetuadas.

static int	geracoes = 0
	Número de estados gerados.

static int	custoAcao = 0
	custo da última ação realizada (Acao(TString))

static TVector< const char * >	ramo

static constexpr const char *	RAMO_ESTADO = " ├■"

static constexpr const char *	RAMO_ESTADO2 = " ├□"

static constexpr const char *	RAMO_ESTADO_FIM = " └■"

static constexpr const char *	RAMO_ESTADO2_FIM = " └□"

static constexpr const char *	RAMO_NOVO = " ├─"

static constexpr const char *	RAMO_FIM = " └─"

static constexpr const char *	RAMO_CONTINUA = " │ "

static constexpr const char *	RAMO_VAZIO = " "

Static Public Attributes inherited from TProcura
static TParametro	instancia = { "",1,1,1 }
	ID da instância atual, a ser utilizado em SolucaoVazia().

static TString	ficheiroInstancia = ""
	prefixo do nome ficheiro de uma instância - editado pelo utilizador Caso não seja nulo, utilizar como prefixo, concatenando com ID da instância, para obter o ficheiro 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

static TString	ficheiroGravar = ""
	prefixo do nome do ficheiro para gravar a instância para ficheiro (terá sido gerada)

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

static int	mpiID = 0
	MPI - rank do processo.

static int	mpiCount = 1
	MPI - número de processos.

static int	modoMPI = 0
	Modo MPI.

static int	gravarSolucao = 0
	Gravar solução CSV (todas as ações)

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

int	Pontos (int resultado)
	converte -infinito, 0, +infinito em -1 (vitória preta), 1 (vitória branca), 0 empate

void	ExecutaTarefa (TVector< TResultadoJogo > &resultados, int inst, int brancas, int pretas, TVector< TVector< int > > *torneio=NULL)
	Executa uma tarefa num teste empírico.

bool	RelatorioCSV (TVector< TResultadoJogo > &resultados, TString ficheiro)
	Gera um relatório CSV com os resultados.

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

void	DebugChamada (bool noFolha, int alfa=0, int beta=0)

Protected Member Functions inherited from TProcuraConstrutiva
void	DebugExpansao (int sucessor, int sucessores, bool minimizar=true)

void	DebugCorte (int sucessores=-1, bool duplo=false)

void	DebugSolucao (bool continuar=false)

void	DebugChamada (bool noFolha)

void	DebugPasso (CListaNo *lista=NULL)

void	DebugSucessores (TVector< TNo > &sucessores)

void	DebugIteracao (int iteracao, const char *simbolo)

void	DebugEstado (bool novaLinha=true) const

void	DebugRamo (const char ramo, const char folha)

void	DebugFolha (bool fimLinha, const char *fmt,...)

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, int iAux=-1, TVector< int > *id=NULL)

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	ExecutaTarefa (TVector< TResultado > &resultados, int inst, int conf)
	Executa uma tarefa num teste empírico.

void	InserirRegisto (TVector< TResultado > &resultados, int inst, int conf)
	Insere um novo registo de resultados.

int64_t	Registo (TResultado &resultado, int id)
	Procura um registo com determinado id.

void	Registo (TResultado &resultado, int id, int64_t valor)
	Atualiza o valor de um registo.

void	MostraParametros (int detalhe=1, TVector< int > *idParametros=NULL, TString titulo="")
	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.

bool	RelatorioCSV (TVector< TResultado > &resultados, TString ficheiro, bool parametros=true)
	Gera um relatório CSV com os resultados.

void	InserirConfiguracoes (TString 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 (TString programa)
	Mostra ajuda de utilização do programa.

void	DebugTabela (ENivelDebug nivel, TVector< int >tabela, TString tipo="", TString prefixo="", int modoCor=0, bool duplaColuna=false)
	Mostra uma tabela de inteiros, 10 elementos por linha, apenas se o nível de debug for igual ou superior.

bool	JuntarCSV (TString ficheiro)
	Juntar ficheiros CSV gerados por diferentes processos MPI em um único ficheiro.

void	TesteInicio (TVector< int > &instancias, TVector< int > &configAtual)
	arranque de teste, auxiliar aos Testes Empíricos

void	TesteFim ()

Protected Attributes
int	indiceHT

Static Protected Attributes
static TValorEstado	valorHT [TAMANHO_HASHTABLE]

static int	reutilizadoAvaliacao

Static Protected Attributes inherited from TProcuraConstrutiva
static TBits	elementosHT [TAMANHO_HASHTABLE]

static int	custoHT [TAMANHO_HASHTABLE]

static TBits	estadoCodHT

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 (TString prompt)

static TString	NovoTexto (TString prompt)

static bool	Debug (ENivelDebug tipo, bool exato, const char *fmt,...)
	Mostra uma informação de debug, se o nível de debug for suficiente.

static TString	MostraTempo (double segundos)
	Mostra tempo num formato humano.

static void	MostraCaixa (TVector< TString > titulo, ECaixaParte parte, TVector< int > largura, bool aberta=true, int identacao=0)

static void	MostraCaixa (TString titulo, ECaixaParte parte, int largura=70, bool aberta=true, int identacao=0, const char *icon="")

static void	MostraCaixa (TVector< TString > textos, int largura=70, bool aberta=true, int identacao=0)

static void	Mensagem (TString titulo, const char *fmt,...)

static void	MostraConjunto (TVector< int > valores, const char *etiqueta)

static void	DebugHSL (float h=-1, float s=1.0, float l=0.2, bool fundo=true)
	Muda a cor (fundo/letra) com HSL.

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.

static void	InicializaMPI (int argc, char *argv[])
	Inicializa o ambiente MPI, se aplicável.

static void	FinalizaMPI ()
	Finaliza o ambiente MPI, se aplicável.

static double	Cronometro (enum ECronometro id=CONT_ALGORITMO, bool inicializar=false)
	retorna o tempo em segundos desde que o cronómetro foi inicializado

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 61 of file TProcuraAdversa.h.

Constructor & Destructor Documentation

◆ TProcuraAdversa()

TProcuraAdversa::TProcuraAdversa ( void )

Definition at line 23 of file TProcuraAdversa.cpp.

◆ ~TProcuraAdversa()

TProcuraAdversa::~TProcuraAdversa ( void )

Definition at line 28 of file TProcuraAdversa.cpp.

Member Function Documentation

◆ CoerenciaJogo()

bool TProcuraAdversa::CoerenciaJogo	(	TVector< TString > &	jogos,
		TVector< TString > &	anterior
	)

Definition at line 1004 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ 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 420 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ DebugChamada()

void TProcuraAdversa::DebugChamada	(	bool	noFolha,
		int	alfa = `0`,
		int	beta = `0`
	)

protected

Definition at line 65 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 1113 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ExecutaTarefa()

void TProcuraAdversa::ExecutaTarefa	(	TVector< TResultadoJogo > &	resultados,
		int	inst,
		int	brancas,
		int	pretas,
		TVector< TVector< int > > *	torneio = `NULL`
	)

protected

Executa uma tarefa num teste empírico.

Parameters

resultados	Vetor onde inserir o resultado.
inst	ID da instância.
conf	ID da brancas
conf	ID da pretas

Definition at line 542 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 183 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 1142 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 173 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Jogar()

TString TProcuraAdversa::Jogar	(	TString	jogo,
		int	configID
	)

Definition at line 872 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ JogoTerminado()

void TProcuraAdversa::JogoTerminado ( TString & jogo )

Definition at line 907 of file TProcuraAdversa.cpp.

Here is the caller graph for this function:

◆ MaiorAmeaca()

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

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 270 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 235 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 92 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 330 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 302 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 192 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Pontos()

int TProcuraAdversa::Pontos ( int resultado )

inlineprotected

converte -infinito, 0, +infinito em -1 (vitória preta), 1 (vitória branca), 0 empate

Definition at line 140 of file TProcuraAdversa.h.

Here is the caller graph for this function:

◆ PontuacaoJogos()

void TProcuraAdversa::PontuacaoJogos ( TVector< TString > & jogos )

Definition at line 931 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ RelatorioCSV()

bool TProcuraAdversa::RelatorioCSV	(	TVector< TResultadoJogo > &	resultados,
		TString	ficheiro
	)

protected

Gera um relatório CSV com os resultados.

Parameters

resultados	Vetor de resultados.
ficheiro	com o nome do ficheiro onde gravar.

Definition at line 1071 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 32 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ SolucaoCompleta()

bool TProcuraAdversa::SolucaoCompleta ( void )

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

Implemented in CJogoDoGalo, and CJogoEmLinha.

Here is the caller graph for this function:

◆ SubstituirHT()

void TProcuraAdversa::SubstituirHT ( int indice )

protectedvirtual

Reimplemented from TProcuraConstrutiva.

Definition at line 1137 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Sucessores()

void TProcuraAdversa::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 += (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::Sucessores(sucessores);
}

Reimplemented from TProcuraConstrutiva.

Definition at line 59 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ TesteEmpirico()

void TProcuraAdversa::TesteEmpirico	(	TVector< int >	instancias,
		TString	ficheiro = `""`
	)

overridevirtual

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

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

Parameters

instancias	- IDs das instâncias a serem utilizadas
ficheiro	- nome do ficheiro com os resultados, caso exista

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

Note: o parâmetro NIVEL_DEBUG controla a quantidade de informação que é mostrada relativamente às tarefas, sendo colocado com o valor NADA para a execução do algoritmo; 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 TProcura.

Definition at line 462 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

◆ TesteEmpiricoGestor()

void TProcuraAdversa::TesteEmpiricoGestor	(	TVector< int >	instancias,
		TString	ficheiro = `""`
	)

overridevirtual

Teste empírico com modo mestre-escravo (este é o mestre)

Reimplemented from TProcura.

Definition at line 608 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

◆ TesteEmpiricoTrabalhador()

void TProcuraAdversa::TesteEmpiricoTrabalhador	(	TVector< int >	instancias,
		TString	ficheiro = `""`
	)

overridevirtual

Teste empírico com modo mestre-escravo (este é o escravo)

Reimplemented from TProcura.

Definition at line 758 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

◆ TesteValidacao()

void TProcuraAdversa::TesteValidacao	(	TVector< int >	instancias,
		TVector< int >	impossiveis,
		TVector< int >	referencias,
		TString	fichSolucoes,
		TString	fichResultados = `""`
	)

overridevirtual

Executa testes de validação, executando cada solução na instância respetiva, e verificando a sua validade bem como características.

Note: Redefinição opcional, caso seja necessário um processo de validação específico.

Esta função carrega a instância e solução (conjunto de ações), as quais são executadas passo a passo, verificando a validade de cada ação sendo calculados indicadores do resultado final.

Caso existam ações inválidas, ou a solução não seja completa, o resultado é considerado inválido, sendo retornado o número de ações corretamente executadas. (isto faz sentido apenas em TProcurasConstrutivas.... nesta classe pode ser algo genérico, sendo redefinida em TProcurasConstrutivas...) (fazer uma função validação geral, a redefinir em TProcurasConstrutivas?) (deixar o formato da solução em aberto, o ficheiro recebe ID da instância, seguido da solução.

Parameters

instancias	- IDs das instâncias a serem validadas.
impossiveis	- IDs das instâncias impossíveis, de entre as instâncias dadas.
referencias	- custo mínimo, custo máximo, tempo mínimo, tempo máximo.
fichSolucoes	- nome do arquivo contendo as soluções a validar para as instâncias.
fichResultados	- nome do arquivo onde os resultados da validação serão gravados (opcional).

Reimplemented from TProcura.

Definition at line 803 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 411 of file TProcuraAdversa.cpp.

Here is the caller graph for this function:

◆ Validar()

bool TProcuraAdversa::Validar ( TVector< TString > solucao )

overridevirtual

Verifica a validade de uma solução para a instância atual.

Note: Redefinição necessária, caso seja necessário um processo de validação específico.

Esta função é chamada para verificar a validade de cada ação durante a execução da solução, bem como para calcular indicadores do resultado final. O formato da solução é genérico, podendo ser adaptado conforme as necessidades específicas do problema.

Parameters

solucao - representação da solução a ser validada (formato específico a ser definido na subclasse).

Returns: Retorna verdadeiro se a solução for válida, ou falso caso contrário.

Reimplemented from TProcuraConstrutiva.

Definition at line 850 of file TProcuraAdversa.cpp.

Here is the call graph for this function:

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 1158 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 73 of file TProcuraAdversa.h.

◆ indiceHT

int TProcuraAdversa::indiceHT

protected

Definition at line 166 of file TProcuraAdversa.h.

◆ infinito

int TProcuraAdversa::infinito = 1000

static

valor de infinito (vitoria/derrota), omissao 1000

Definition at line 71 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 69 of file TProcuraAdversa.h.

◆ nivelOK

int TProcuraAdversa::nivelOK = 0

static

profundidade máxima no método iterativo

Definition at line 75 of file TProcuraAdversa.h.

◆ resultadoCompleto

int TProcuraAdversa::resultadoCompleto = 0

static

resultado após SolucaoCompleta() retornar true (-1 vitória minimizar, 0 empate, 1 vitória maximizar)

Definition at line 77 of file TProcuraAdversa.h.

◆ reutilizadoAvaliacao

int TProcuraAdversa::reutilizadoAvaliacao

staticprotected

Definition at line 172 of file TProcuraAdversa.h.

◆ valorHT

TValorEstado TProcuraAdversa::valorHT

staticprotected

Definition at line 164 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

◆ CoerenciaJogo()

◆ CorteAlfaBeta()

◆ DebugChamada()

◆ ExecutaAlgoritmo()

◆ ExecutaTarefa()

◆ ExisteHeuritica()

◆ ExisteHT()

◆ Heuristica()

◆ Jogar()

◆ JogoTerminado()

◆ MaiorAmeaca()

◆ MetodoIterativo()

◆ MiniMax()

◆ MiniMaxAlfaBeta()

◆ NoFolha()

◆ OrdenarSucessores()

◆ Pontos()

◆ PontuacaoJogos()

◆ RelatorioCSV()

◆ ResetParametros()

◆ SolucaoCompleta()

◆ SubstituirHT()

◆ Sucessores()

◆ TesteEmpirico()

◆ TesteEmpiricoGestor()

◆ TesteEmpiricoTrabalhador()

◆ TesteValidacao()

◆ Utilizavel()

◆ Validar()

◆ ValorEstado()

Member Data Documentation

◆ completo

◆ indiceHT

◆ infinito

◆ minimizar

◆ nivelOK

◆ resultadoCompleto

◆ reutilizadoAvaliacao

◆ valorHT