Representa um estado no problema do Aspirador. More...

#include <Aspirador.h>

Inheritance diagram for CAspirador:

Collaboration diagram for CAspirador:

Public Member Functions
	CAspirador (void)

	~CAspirador (void)

TProcuraConstrutiva *	Duplicar (void)
	Cria um objecto que é uma cópia deste.

void	Copiar (TProcuraConstrutiva *objecto)

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

void	ResetParametros ()
	Inicializa os parâmetros, indicadores e instâncias.

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 (bool completo=true) override
	Mostra o estado no ecrã, para debug.

TString	Acao (TProcuraConstrutiva *sucessor)

bool	Distinto (TNo estado)
	Verifica se o estado actual distinto do fornecido.

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

int	Heuristica (void)
	Função para calcular quanto falta para o final, o valor da heurística.

Public Member Functions inherited from TProcuraConstrutiva
	TProcuraConstrutiva (void)

virtual	~TProcuraConstrutiva (void)

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 bool	Validar (TVector< TString > solucao)
	Verifica a validade de uma solução para a instância atual.

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 bool	Acao (TString acao)
	Executa a ação (movimento, passo, jogada, lance, etc.) no estado atual.

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 bool	Parar (void)
	Verifica se a procura deve ser interrompida.

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

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

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

virtual void	TesteEmpirico (TVector< int > instancias, TString ficheiro="")
	Executa testes empíricos, em todas as configurações guardadas, nas instâncias selecionadas.

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

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

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
TVector< char >	salas

int	aspirador

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.

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

virtual void	SubstituirHT (int indice)

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

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

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

static int	custoHT [TAMANHO_HASHTABLE]

static TBits	estadoCodHT

static int	colocadosHT = 0

Detailed Description

Representa um estado no problema do Aspirador.

Este problema consiste ter salas vizinhas, que podem estar sujas ou limpas. Pretende-se ter todas as salas limpas, sendo as ações de mover para a sala do lado, ou aspirar.

Definition at line 11 of file Aspirador.h.

Constructor & Destructor Documentation

◆ CAspirador()

CAspirador::CAspirador ( void )

Definition at line 6 of file Aspirador.cpp.

Here is the caller graph for this function:

◆ ~CAspirador()

CAspirador::~CAspirador ( void )

Definition at line 9 of file Aspirador.cpp.

Member Function Documentation

◆ Acao()

TString CAspirador::Acao ( TProcuraConstrutiva * sucessor )

Definition at line 56 of file Aspirador.cpp.

◆ Codifica()

void CAspirador::Codifica ( TBits & estado )

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: Inicializar()

void CSubProblema::Codifica(TBits estado)
{
    Vector<int> vetor; // assumindo neste exemplo que o estado é um vetor de inteiros pequenos
    Normalizar(vetor); // o vetor tem várias formas, e agora é normalizado por uma função de CSubProblema
    TProcuraConstrutiva::Codifica(estado); // chamar a superclasse após normalizar o estado
    // codificar números de 4 bits, assumindo que os inteiros pequenos cabem em 4 bits
    for (int i = 0, index = 0; i < vetor.Count(); i++, index += 4)
        estado[index >> 6] |= (uint64_t)vetor[i] << (index & 63);
}

Reimplemented from TProcuraConstrutiva.

Definition at line 119 of file Aspirador.cpp.

Here is the call graph for this function:

◆ Copiar()

void CAspirador::Copiar ( TProcuraConstrutiva * objecto )

inline

Definition at line 24 of file Aspirador.h.

Here is the caller graph for this function:

◆ Debug()

void CAspirador::Debug ( bool completo = true )

overridevirtual

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(NIVEL_DEBUG). 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(bool completo)   // refazer comentários....
{
       NovaLinha();
    // neste exemplo o estado é apenas um número
    if(Parametro(NIVEL_DEBUG) <= ATIVIDADE)
           printf("--<([%d])>--", variavel); // versão compacta do estado
    else {
        // versão mais elaborada do estado
    }
}

Reimplemented from TProcura.

Definition at line 67 of file Aspirador.cpp.

Here is the call graph for this function:

◆ Distinto()

bool CAspirador::Distinto ( TNo estado )

virtual

Verifica se o estado actual distinto do fornecido.

Note: Redefinição opcional. Necessário para identificação de estados repetidos por teste de ascendentes.

Returns: Retorna verdadeiro se o estado é distinto, e falso se é igual

Compara as variáveis de estado para determinar se dois estados são iguais ou diferentes.

Note: Se a verificação de estados repetidos for baseada na análise de ascendentes, a superclasse chama este método dentro de Sucessores().

bool CSubProblema::Distinto(TNo estado) {
    CSubProblema& outro = *((CSubProblema*)estado);
    // verificar todas as variáveis de estado
    return variavel != outro.variavel;
}

Reimplemented from TProcuraConstrutiva.

Definition at line 88 of file Aspirador.cpp.

Here is the call graph for this function:

◆ Duplicar()

TProcuraConstrutiva * CAspirador::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
            memoriaEsgotada = true;
       return clone;
}

Implements TProcuraConstrutiva.

Definition at line 12 of file Aspirador.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Heuristica()

int CAspirador::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 parâmetros para que a heurística possa ser calculada de acordo com o parâmetro definido. Em fase de testes logo se averigua qual a versão que adiciona mais vantagem à procura.; Uma heurística pode resultar de um relaxamento do problema. Verifique se o problema sem uma das restrições (fazendo batota), se consegue resolver mais facilmente. Utilize como heurística o custo de resolver o problema sem essa restrição.

void CSubProblema::Heuristica(void)
{
    heuristica = 0; // ponto de partida, há 0 de custo
    // utilizar neste exemplo a distância até 1000, local onde estará o objetivo
    heuristica = abs(variavel - 1000);
    // chamar a função heurística da superclass
    return TProcuraConstrutiva::Heuristica();
}

Reimplemented from TProcuraConstrutiva.

Definition at line 95 of file Aspirador.cpp.

Here is the call graph for this function:

◆ Inicializar()

void CAspirador::Inicializar ( 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.

void CSubProblema::Inicializar(void)
{
    TProcura::Inicializar();
       // 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
    // pode/deve utilizar variável "ficheiroInstancia" concatenado com instancia.valor, com o ID da instância
    // inicializar todas as variáveis de estado
       variavel = 0;
    // Determinar o tamanho máximo do estado codificado, se aplicável
       tamanhoCodificado = 1;
}

Reimplemented from TProcura.

Definition at line 22 of file Aspirador.cpp.

Here is the call graph for this function:

◆ ResetParametros()

void CAspirador::ResetParametros ( )

virtual

Inicializa os parâmetros, indicadores e instâncias.

Note: Redefinição necessária, para pelo menos indicar as instâncias existentes

Nesta função, a primeira instrução deverá ser a chamada da função da superclasse, para que sejam criados os parÂmetros 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 por omissão.

Novos parâmetros podem ser adicionados conforme necessário para atender às particularidades do problema. Estes parâmetros 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.

Nesta função deve ser redefinida 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 parÂmetros, devendo ser inicializada aqui.

Existindo novos indicadores, devem ser adicionados aqui, e redefinida a função Indicador() para calcular o valor.

Note: Na criação de um novo parâmetro, 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.; A instância selecionada irá ser carregada em Inicializar(), utilizando o valor atual.

See also: TParametro

Exemplo com a alteração do valor por omissão de um parâmetro, e adição de dois novos parametros.

// continuação da enumeração EParametrosProcura
enum ESubProblema { opcaoHeur = parametrosProcura, opcaoSuc };
void CSubProblema::ResetParametros(void)
{
    static const char* nomesSuc[] = { "todas", "contributo" }; // nomes para os valores de opcaoSuc
    // chamar primeiro o método na superclasse
    TProcura::ResetParametros();
    // neste exemplo considerou-se que se pretende ver algum debug, por omissão
    Parametro(NIVEL_DEBUG) = ATIVIDADE;
 
    // novo parâmetro para utilizar na função Heuristica()
    parametro += { "Opção Heurística", 0,0,10,
        "explicação do que acontece na heuristica, com este parametro entre 0 e 10",NULL };
    // novo parâmetro para utilizar na função Sucessores()
    parametro += { "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 };
 
    // novo indicador
    indicador += { "Ordenado","verifica se um vetor está ordenado", indOrdenar };
    indAtivo += indOrdenar; // adicionar aos indicadores ativos por omissão
 
    // indicar que há 10 instâncias, sendo a instância inicial a 1
       instancia = { "Problema", 1,1,10, "Características dos problemas", NULL };
}

Reimplemented from TProcura.

Definition at line 31 of file Aspirador.cpp.

Here is the call graph for this function:

◆ SolucaoCompleta()

bool CAspirador::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 80 of file Aspirador.cpp.

Here is the call graph for this function:

◆ Sucessores()

void CAspirador::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 37 of file Aspirador.cpp.

Here is the call graph for this function:

Member Data Documentation

◆ aspirador

int CAspirador::aspirador

Definition at line 20 of file Aspirador.h.

◆ salas

TVector<char> CAspirador::salas

Definition at line 19 of file Aspirador.h.

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

Construtiva/Teste/Aspirador.h
Construtiva/Teste/Aspirador.cpp

Public Member Functions

Public Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ CAspirador()

◆ ~CAspirador()

Member Function Documentation

◆ Acao()

◆ Codifica()

◆ Copiar()

◆ Debug()

◆ Distinto()

◆ Duplicar()

◆ Heuristica()

◆ Inicializar()

◆ ResetParametros()

◆ SolucaoCompleta()

◆ Sucessores()

Member Data Documentation

◆ aspirador

◆ salas