8#define BUFFER_SIZE 1024
44 "Profundidade Primeiro",
58 parametro.Add({
"Ver",4,1,100,
"Mostra estado a cada K ações. Se 1 mostra sempre estados e nunca ações.",
NULL });
61 "Valor dependente do algoritmo. \n\
62Largura: 0 sem limite, >0 número máximo de estados gerados não expandidos. \n\
63Profundidade: >0 limite de profundidade, =0 iterativo, <0 sem limite.",
NULL });
65 parametro.Add({
"Repetidos", 1,1,3,
"Forma de lidar com os estados repetidos (ignorá-los, ascendentes, gerados).",
69 "Peso aplicado à heuristica, na soma com o custo para calculo do lower bound. No A*, se peso 0, fica custo uniforme, h(n) não conta, se peso 100 fica A* normal, se superior a 100 aproxima-se do melhor primeiro.",
NULL });
72 "RuÃdo a adicionar à heurÃstica, para testes de robustez. Se K positivo, adicionar entre 0 e K-1, se negativo, o valor a adicionar pode ser positivo ou negativo.",
NULL });
75 "Baralhar os sucessores ao expandir.",
NULL });
81 indicador.Add({
"Lower Bound",
"valor mÃnimo para a melhor solução, se igual ao custo da solução obtida, então esta é ótima",
174 if (
lista.Last()->SolucaoCompleta()) {
256 lista.Estado()->DebugPasso();
257 if (
lista.Estado()->SolucaoCompleta())
296 if ((nivel > 1 || nivel < 0) && !
Parar()) {
377 for (
int i = 0;
i <
id.Count();
i++) {
423 for (
int i = 0;
i <
id.Count();
i++) {
459 for (
int i = 0;
i <
id.Count();
i++) {
500 lista.Estado()->DebugPasso();
501 if (
lista.Estado()->SolucaoCompleta())
592 printf(
" Solução encontrada!");
768 printf(
"\nSem sucessores.");
788 case -1:
printf(
"ImpossÃvel\n");
break;
789 case -2:
printf(
"Não resolvido\n");
break;
832 }
while (
opcao != 0);
844 for (
int i = 0;
i < 8 && valor;
i++) {
845 unsigned char octeto = valor & 255;
870 printf(
"\nHT: utilização %d%%, reuso: %.2f vezes",
@ limite
Valor dependente do algoritmo. Exemplo: Profundidade limitada.
@ ruidoHeur
RuÃdo a adicionar à heurÃstica para testes de robustez.
@ estadosRepetidos
Forma de lidar com estados repetidos (ignorá-los, ascendentes, gerados).
@ verAcoes
Mostra estado a cada K ações. Se 1, mostra sempre estados e nunca ações.
@ baralharSuc
Baralhar os sucessores ao expandir.
@ indExpansoes
número de expansões efetuadas durante a procura
@ indCusto
o resultado é o custo da solução atual, sendo um upper bound
@ indGeracoes
número de estados gerados durante a procura
@ indLowerBound
valor mÃnimo para a melhor solução, se igual ao custo da solução obtida, então esta é ótima
@ ascendentes
estados são comparados com ascendentes, e se forem repetidos são removidos
@ gerados
estados são comparados com todos os gerados, e se forem repetidos são removidos
#define TAMANHO_HASHTABLE
@ detalhe
Debug detalhada sobre estados e decisões.
@ atividade
Apenas eventos principais.
@ completo
Mostra toda a execução detalhadamente.
@ passos
Exibe passos intermediários.
@ nada
Sem informações de debug.
@ nivelDebug
Nível de debug, de reduzido a completo.
@ algoritmo
Algoritmo base a executar.
Lista ordenada de nós para algoritmos de procura informada.
Representa um estado no espaço de estados.
void DebugCorte(int sucessores=-1, bool duplo=false)
void DebugSucessores(TVector< TNo > &sucessores)
TProcuraConstrutiva(void)
void DebugRamo(char ramo, char folha)
int SolucaoEncontrada(bool continuar=false)
void DebugEstado(int id=-1, int pai=-1)
void DebugSolucao(bool continuar=false)
void ExecucaoTerminada(clock_t inicio) override
Chamar após a execução do algoritmo. Grava o tempo consumido.
static uint64_t elementosHT[TAMANHO_HASHTABLE][OBJETO_HASHTABLE]
void CalcularHeuristicas(TVector< TNo > &sucessores, TVector< int > *id=NULL, bool sortLB=false)
int SolucaoParcial(int i, TVector< TNo > &sucessores)
void NovaLinha(bool tudo=true)
int ObjetivoAlcancado(int item, TVector< TNo > &lista)
static void LibertarVector(TVector< TNo > &vector, int excepto=-1, int maiorQue=-1)
virtual void SubstituirHT(int indice)
void Explorar()
definir para explorar manualmente os dados (não definido em TProcura, apenas em TProcuraConstrutiva)
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...
void CalculaCaminho(bool completa=true)
void DebugExpansao(int sucessor, int sucessores, bool duplo=false)
void DebugIteracao(int iteracao)
void VerificaLimites(int limite, int porProcessar, TVector< TNo > &sucessores)
static int custoHT[TAMANHO_HASHTABLE]
static uint64_t estadoCodHT[OBJETO_HASHTABLE]
static bool memoriaEsgotada
Flag indicando problemas de memória esgotada.
static int Dominio(int &variavel, int min=INT_MIN, int max=INT_MAX)
Limita o domínio de um parâmetro inteiro.
static int resultado
Resultado retornado pelo algoritmo na última execução.
virtual int Indicador(int id)
Retorna um indicador, após a execução do algoritmo.
static int iteracoes
Número total de iterações realizadas na última execução.
virtual void ResetParametros()
Inicializa os parametros, indicadores e instâncias.
virtual bool Parar(void)
Verifica se a procura deve ser interrompida.
virtual void ExecucaoTerminada(clock_t inicio)
Chamar após a execução do algoritmo. Grava o tempo consumido.
virtual void Debug(void)
Mostra o estado no ecrã, para debug.
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 ...
static TVector< int > indAtivo
virtual void LimparEstatisticas(clock_t &inicio)
Chapar antes da execução do algoritmo. Limpa valores estatísticos, e fixa o instante limite de tempo para...
static TVector< TParametro > parametro
Parâmetros a serem utilizados na configuração atual.
TVector< Item > & Add(Item a)
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 LarguraPrimeiro(int limite=0)
Executa a procura em largura primeiro, algoritmo cego.
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 void Copiar(TNo objecto)
Fica com uma cópia do objecto.
virtual TNo Duplicar(void)=0
Cria um objecto que é uma cópia deste.
int Indicador(int id) override
Redefinição. Ver TProcura::Indicador().
int ExecutaAlgoritmo()
Executa o algoritmo com os parametros atuais.
virtual int Heuristica(void)
Função para calcular quanto falta para o final, o valor da heurÃstica.
virtual void Codifica(uint64_t estado[OBJETO_HASHTABLE])
Codifica o estado para um vetor de inteiros de 64 bits.
virtual const char * Acao(TNo sucessor)
Retorna a ação (movimento, passo, jogada, lance, etc.) que gerou o sucessor.
int heuristica
Estimativa para o custo até um estado objetivo, se disponÃvel.
int custo
Custo total acumulado desde o estado inicial.
TNo pai
Ponteiro para o estado pai, na árvore de procura.
static int expansoes
Número de expansões efetuadas.
static int lowerBound
Valor mÃnimo que a solução pode apresentar, obtido pela procura.
static int tamanhoCodificado
Número de inteiros de 64 bits utilizados para codificar um objeto (≤ OBJETO_HASHTABLE).
static int geracoes
Número de estados gerados.
static TVector< TNo > caminho
Solução retornada pela procura (os estados devem ser libertados).
static TVector< unsigned char > ramo
static TNo solucao
Estado objetivo encontrado, retornado pela procura (deve ser libertado).
unsigned int rand(int seq)
Retorna o próximo valor pseudo-aleatório.