TProcura
Biblioteca em C++ para testes paramétricos de algoritmos, e coleção de algoritmos de procura e otimização
Loading...
Searching...
No Matches
TProcuraConstrutiva.cpp
Go to the documentation of this file.
2#include "CListaNo.h"
3#include <stdio.h>
4#include <time.h>
5#include <string.h>
6#include <ctype.h>
7
8#define BUFFER_SIZE 1024
9
10
11// auxiliar para construcao da arvore de procura
13// espacamento entre ramos da arvore de debug
15// valor retornado pela procura (tem de ser libertado)
17// valor retornado pela procura (tem de ser libertado)
19// lowerBound: valor mínimo que a solução pode obter
25
26
27// tamanho em inteiros de 64 bits de um objeto (inferior ou igual a OBJETO_HASHTABLE)
29
31int TProcuraConstrutiva::custoHT[TAMANHO_HASHTABLE]; // hashtable / custo do estado que foi gerado
32uint64_t TProcuraConstrutiva::estadoCodHT[OBJETO_HASHTABLE]; // elemento codificado
33int TProcuraConstrutiva::colocadosHT = 0; // número de elementos colocados na HT
34
35TProcuraConstrutiva::TProcuraConstrutiva(void) : pai(NULL), custo(1), heuristica(0) {
36}
37
38
40{
41 static const char* nomesAlgoritmos[] = {
42 "Largura Primeiro",
43 "Custo Uniforme",
44 "Profundidade Primeiro",
45 "Melhor Primeiro",
46 "A*",
47 "IDA*",
48 "Branch and Bound" };
49 static const char* nomesRepetidos[] = {
50 "ignorar",
51 "ascendentes",
52 "gerados" };
54 // definir parametros base
55 // algoritmos, alterar
56 parametro[algoritmo] = { "Algoritmo",1,1,7,"Algoritmo base a executar.", nomesAlgoritmos };
57 // ver Acoes (ou apenas estados completos)
58 parametro.Add({ "Ver",4,1,100,"Mostra estado a cada K ações. Se 1 mostra sempre estados e nunca ações.",NULL });
59 // limite (algoritmo)
60 parametro.Add({ "Limite",0,-1,1000000,
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 });
64 // estados repetidos
65 parametro.Add({ "Repetidos", 1,1,3, "Forma de lidar com os estados repetidos (ignorá-los, ascendentes, gerados).",
67 // pesoAStar
68 parametro.Add({ "pesoAStar",100,0,10000,
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 });
70 // ruido heuristica
71 parametro.Add({ "ruido",0,-100,100,
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 });
73 // baralhar sucessores
74 parametro.Add({ "baralhar",0,0,1,
75 "Baralhar os sucessores ao expandir.",NULL });
76
77 indicador[indCusto].nome = "Custo";
78 indicador[indCusto].descricao = "o resultado é o custo da solução atual";
79 indicador.Add({ "Expansões","número de expansões efetuadas", indExpansoes });
80 indicador.Add({ "Gerações","número de estados gerados", indGeracoes });
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",
84}
85
86// Executa uma ação (movimento, passo, jogada, lance, etc.) no estado atual. Caso não seja feito nada, retornar falso.
87bool TProcuraConstrutiva::Acao(const char* acao) {
90 for (int i = 0; i < sucessores.Count(); i++)
91 if (strcmp(acao, Acao(sucessores[i])) == 0) {
94 return true;
95 }
96 return false;
97}
98
99// Coloca em sucessores a lista de objectos sucessores (sao alocados neste metodo e tem de ser apagados)
100// O custo se não existir, deixar a 1 (valor de omissão)
101// chamar o metodo desta classe apos adicionar os sucessores para actualizar geracoes e expansoes,
102// bem como verificar a existência de estados repetidos
104 if (memoriaEsgotada)
105 return;
106 // colocar como pai o estado atual e atualizar custos
107 for (int i = 0; i < sucessores.Count(); i++) {
108 sucessores[i]->pai = this;
109 sucessores[i]->custo += custo;
110 // o custo total tem de estar atualizado antes de se utilizar nas hashtables
111 }
112 // verificação de estados repetidos
114 for (int i = 0; i < sucessores.Count(); i++)
115 if (sucessores[i]->ExisteHT()) {
116 // estado já gerado anteriormente, está na hashtable, pelo que não interessa
117 delete sucessores[i];
118 sucessores[i] = NULL;
119 }
120 }
122 // verificar se o estado já foi gerado na árvore de procura
123 // remover todos os estados que ja tenham sido expandidos neste ramo
124 for (int i = 0; i < sucessores.Count(); i++) {
125 TNo avo = this;
126 while (avo != NULL && avo->Distinto(sucessores[i]))
127 avo = avo->pai;
128 // estado é igual a um avô, não interessa
129 if (avo != NULL) {
130 delete sucessores[i];
131 sucessores[i] = NULL;
132 }
133 }
134 }
135 sucessores.Remove(NULL);
136 if (Parametro(baralharSuc) == 1)
137 sucessores.RandomOrder();
138 expansoes++;
139 geracoes += sucessores.Count();
140}
141
142
143// metodo interno para libertar objectos nao necessarios
144void TProcuraConstrutiva::LibertarVector(TVector<TNo>& vector, int excepto, int maiorQue)
145{
146 for (int i = 0; i < vector.Count(); i++)
147 if (i != excepto && i > maiorQue && vector[i] != NULL)
148 delete vector[i];
149 vector.Count(0);
150}
151
153// Procura em Largura Primeiro: expande primeiro o estado gerado não expandido mais antigo
154// retorna o valor da solução e coloca o caminho no vector (se calcularCaminho=true), ou -1 caso não encontre solucao
155// limite é o número de estados gerados não expandidos, que não pode ultrapassar esse limite
156// os que ultrapassarem são deitados fora (se 0 este limite não importa, podendo haver problemas de memória)
158{
159 TVector<TNo> lista; // lista de nós gerados na árvore de procura (expandidos ou não)
160 lista.Add(this); // nó inical: estado, custo
161 for (int i = 0; i < lista.Count() && !Parar(); i++) {
162 // processar o próximo estado não expandido (estão expandidos todos os anteriores a i)
163 lista[i]->DebugPasso();
164 // expansão deste estado
166 lista[i]->Sucessores(sucessores);
167 // garantir que os limites são respeitados, para evitar problemas de memória
169 // inserir tudo no final da lista
170 for (int j = 0; j < sucessores.Count(); j++) {
171 lista.Add(sucessores[j]);
172 // verificar se é um estado objetivo, a solução é completa nesse caso
173 // teste na geração e não na expansão
174 if (lista.Last()->SolucaoCompleta()) {
176 return ObjetivoAlcancado(lista.Count() - 1, lista); // Sucesso! Terminar a procura e retornar
177 }
178 }
179
181 lista[i]->DebugSucessores(sucessores);
182
183 // Nao se pode libertar estados ja expandidos porque nao se sabe se
184 // os pais sao necessarios ou nao.
185 // todos os estados antes de i, são os estados gerados e expandidos (fechados)
186 // todos os estados após i são estados gerados mas não expandidos (abertos)
187 }
188 // nada feito, libertar tudo excepto o estado inicial que é este objeto, e retornar
190 return -1; // falhou
191}
192
194{
195 estado->CalculaCaminho(completa); // extrair o caminho do estado objetivo até ao estado inicial
196 solucao = estado->Duplicar(); // registar este estado como a solução
197 solucao->custo = estado->custo;
199 return solucao->custo;
200}
201
208
210 TNo atual = this;
211 // limpar o caminho anterior (caso do BnB que obtém mais que uma solução)
212 while (caminho.Count() > 0)
213 delete caminho.Pop();
214 caminho.Add(atual->Duplicar());
215 caminho.Last()->custo = atual->custo;
216
217 // apenas se a lista estiver completa, há a garantia dos pais não terem sido apagados
218 if (completa) {
219 // obter caminho para a solucao
220 while (atual->pai != NULL) {
221 atual = atual->pai;
222 caminho.Add(atual->Duplicar());
223 caminho.Last()->custo = atual->custo;
224 }
225 }
226 caminho.Invert();
227}
228
230 int limite, int porProcessar, TVector<TNo>& sucessores)
231{
232 // caso o limite seja ultrapassado,
233 // remover elementos a mais da lista de sucessores
234 if (limite != 0 && limite < porProcessar + sucessores.Count()) {
235 int maximo = limite - porProcessar;
236 if (maximo >= 0 && maximo < sucessores.Count()) {
237 for (int i = maximo; i < sucessores.Count(); i++)
238 delete sucessores[i];
239 sucessores.Count(maximo);
240 }
241 else if (maximo < 0)
243 }
244}
245
246
248// Procura Custo Uniforme: expande primeiro o estado gerado não expandido de menor custo acumulado
250{
252
253 lista.Inserir(this); // começa apenas com o elemento atual
254
255 for (lista.atual = 0; !Parar() && lista.Estado() != NULL; lista.atual = lista.Proximo()) {
256 lista.Estado()->DebugPasso();
257 if (lista.Estado()->SolucaoCompleta())
258 return ObjetivoAlcancado(lista.Estado(), lista.Completa());
259
261 lista.Estado()->Sucessores(sucessores);
262 // insere por ordem de custo, e não apenas no final
263 lista.Inserir(sucessores);
265 lista.Estado()->DebugSucessores(sucessores);
266 }
267 return -1; // falhou
268}
269
271// Procura em Profundidade Primeiro: expande primeiro o estado gerado não expandido mais novo
272// caso o nivel=-1, e feita uma procura em profunidade normal
273// caso o nivel>0, e feita uma procura em profundidade limitada
274// caso o nivel=0, e feita uma procura em profundidade iterativa, sem limite
275// versão recursiva
277{
278 DebugChamada();
279 if (nivel == 0) { // metodo iterativo
280 int resultado = -1;
281 do {
282 // limpar hashtable: estados gerados no nível anterior não devem impedir nova geração
283 LimparHT();
284 DebugIteracao(nivel + 1);
285 // chamar a profundidade nível 1, e se não resolver, o nível 2, e assim sucessivamente
287 } while (resultado == -1 && !Parar());
288 return resultado;
289 }
290
291 // metodo normal
292 // verificar se o estado atual é objetivo, ou seja, a solução parcial é já completa
293 if (SolucaoCompleta())
294 return SolucaoEncontrada();
295
296 if ((nivel > 1 || nivel < 0) && !Parar()) {
297 // caso o nível seja superior a 1 ou sem limite, expandir o estado atual
300 // tentar todos os sucessores, um de cada vez
301 for (int i = 0; i < sucessores.Count(); i++) {
302 DebugExpansao(i, sucessores.Count());
303 // chamada recursiva, reduzindo o nível
304 if (sucessores[i]->ProfundidadePrimeiro(nivel - 1) >= 0)
305 // este sucessor resolveu o problema, retornar
306 return SolucaoParcial(i, sucessores);
307 }
308 // nenhum dos sucessores resolveu o problema
309 DebugCorte(sucessores.Count());
311 }
312 else
313 DebugCorte();
314
315 // falha na procura neste nó, ou não há estado objetivo a partir daqui
316 // ou atingiu-se o limite, pelo que temos de retornar -1
317 return -1;
318}
319
321 // sucesso!
323 if (solucao == NULL)
324 solucao = Duplicar();
325 else // caso existam várias soluções, substitui a anterior
326 solucao->Copiar(this);
328 return solucao->custo = custo;
329}
330
332{
333 // solução parcial já registada, adicionar este nó e retornar o custo até ao momento
335 return solucao->custo;
336}
337
339 for (int i = 0; i < caminho.Count(); i++) {
340 if (Parametro(verAcoes) > 1) {
341 // mostrar o estado a cada K ações, no início e no fim
342 if (i % Parametro(verAcoes) == 0 || i == caminho.Count() - 1) {
343 caminho[i]->Debug();
344 // mostrar custo
345 printf(" (g:%d) ", caminho[i]->custo);
346 }
347 // mostrar a ação
348 if (i < caminho.Count() - 1)
349 printf(" %s", caminho[i]->Acao(caminho[i + 1]));
350 }
351 else {
352 caminho[i]->Debug();
353 printf(" (g:%d) ", caminho[i]->custo);
354 }
355 }
356 if (caminho.Count() == 0)
357 printf("Caminho vazio.");
358}
359
360
362// Algoritmo Melhor Primeiro: expande primeiro o estado gerado não expandido com melhor heurística
363// versão recursiva, idêntico a ProcuraPrimeiro()
365{
366 DebugChamada();
367 if (SolucaoCompleta())
368 return SolucaoEncontrada();
369
370 if ((nivel <= 0 || nivel > 1) && !Parar()) {
372 TVector<int> id; // índice para ordenar os sucessores por heurística
374 CalcularHeuristicas(sucessores, &id); // id fica ordenado por heurística
375 // processar todos os sucessores da mesma forma que a procura em profundidade,
376 // mas utilizando a ordem id, por heurística
377 for (int i = 0; i < id.Count(); i++) {
378 DebugExpansao(i, id.Count());
379 if (sucessores[id[i]]->MelhorPrimeiro(nivel - 1) >= 0)
380 return SolucaoParcial(id[i], sucessores);
381 }
382 DebugCorte(sucessores.Count());
384 }
385 else
386 DebugCorte();
387 return -1;
388}
389
391// Algoritmo IDAStar: procura em profundidade limitada a um upperBound
392// idêntico a MelhorPrimeiro() mas cortando quando upperBound já não consegue ser obtido
394{
395 DebugChamada();
396 if (upperBound == 0) { // parte iterativa
397 int resultado = -1;
398 // primeiro valor para o lower bound, a heurística no nó raiz
399 lowerBound = Heuristica(); // o custo é zero atualmente
400 if (lowerBound == 0)
401 lowerBound++;
402 do {
403 // limpar hashtable: estados gerados no nível anterior não devem impedir nova geração
404 LimparHT();
406 // ver se há uma solução com este valor
408 // o valor de lowerBound é atualizado, para utilizar na próxima iteração se necessário
409 } while (resultado == -1 && !Parar());
410 return resultado;
411 }
412
413 if (SolucaoCompleta())
414 return SolucaoEncontrada();
415
416 if (!Parar()) {
418 TVector<int> id; // índice para ordenar os sucessores por heurística
420 CalcularHeuristicas(sucessores, &id, true); // id fica ordenado por LB
421 // processar todos os sucessores da mesma forma que a procura em profundidade,
422 // mas utilizando a ordem id, por heurística
423 for (int i = 0; i < id.Count(); i++) {
424 int atual = sucessores[id[i]]->LowerBound();
425 DebugExpansao(i, id.Count());
426 if (atual > upperBound) {
427 // acima do permitido nesta iteração
428 if (lowerBound == upperBound || lowerBound > atual)
429 lowerBound = atual;
430 DebugCorte(); // estado cortado, não expandido
431 }
432 else {
433 if (sucessores[id[i]]->IDAStar(upperBound) >= 0)
434 return SolucaoParcial(id[i], sucessores);
435 }
436 }
437 DebugCorte(sucessores.Count());
439 }
440 return -1;
441}
442
444// Algoritmo BranchAndBound:
445// idêntico a MelhorPrimeiro(), mas continua após a primeira solução
446// explora apenas os estados em que f(n) < atual solução (LB<UB)
448{
449 DebugChamada();
450 if (SolucaoCompleta())
451 return SolucaoEncontrada(true);
452
453 if (!Parar()) {
455 TVector<int> id; // índice para ordenar os sucessores por heurística
457 CalcularHeuristicas(sucessores, &id, true); // id fica ordenado por LB
458 // processar todos os sucessores, mas apenas se LB<UB
459 for (int i = 0; i < id.Count(); i++) {
460 DebugExpansao(i, id.Count());
461 if (upperBound && sucessores[id[i]]->LowerBound() >= upperBound) {
462 DebugCorte(); // estado cortado, e os seguintes não serão expandidos
463 break;
464 }
465 int resultado = sucessores[id[i]]->BranchAndBound(upperBound);
466 // mesmo que exista um resultado, continuar à procura de melhor
467 if (resultado > 0 && (!upperBound || resultado < upperBound))
469 }
470 DebugCorte(sucessores.Count());
472 }
473 return (solucao != NULL ? solucao->custo : -1);
474}
475
477 TVector<TNo>& sucessores, TVector<int>* id, bool sortLB)
478{
480 // obter os valores heurísticos, e ordentar o índice
481 for (int i = 0; i < sucessores.Count(); i++) {
482 sucessores[i]->heuristica = sucessores[i]->Heuristica();
483 if (id != NULL)
485 }
486 if (id != NULL)
487 heuristicas.Sort(id); // ordenar id
488}
489
490
492// Algoritmo AStar: expande primeiro o estado gerado não expandido com melhor custo+heurística
493// Idêntico a CustoUniforme()
495{
497 lista.Inserir(this); // estado único
498
499 for (lista.atual = 0; !Parar() && lista.Estado() != NULL; lista.atual = lista.Proximo()) {
500 lista.Estado()->DebugPasso();
501 if (lista.Estado()->SolucaoCompleta())
502 return ObjetivoAlcancado(lista.Estado(), lista.Completa());
503
505 lista.Estado()->Sucessores(sucessores);
506 // atualiza as heurísticas, sendo esta a única diferença para CustoUniforme
508 // insere por ordem de custo, e não apenas no final
509 lista.Inserir(sucessores);
511 lista.Estado()->DebugSucessores(sucessores);
512 }
513
514 return -1; // falhou
515}
516
517// Redefinir para poder utilizar os algoritmos informados
518// Esta função deve devolver o custo estimado por baixo,
519// desde este estado até ao estado final mais proximo (é um valor minimo),
520// colocando esse valor na variável heuristica
521// chamar este método para actualiacao de avaliacoes
530
531
532// Metodo para ser chamado antes de analisar cada sucessor
533void TProcuraConstrutiva::DebugExpansao(int sucessor, int sucessores, bool duplo)
534{
535 if (Parametro(nivelDebug) >= passos) {
536 if (sucessor > 0)
537 NovaLinha(false);
538
539 if (sucessor == 0 && sucessores == 1) { // só um ramo
540 DebugRamo(Parametro(nivelDebug) < completo ? '-' : ' ', duplo ? '#' : '+');
541 ramo.Add(' '); // a ser impresso nesta posição nas linhas seguintes
542 }
543 else if (sucessor == 0) { // início e continua
544 DebugRamo(Parametro(nivelDebug) < completo ? '-' : ' ', duplo ? '#' : '+');
545 ramo.Add(duplo ? '/' : '|'); // a ser impresso nesta posição nas linhas seguintes
546 }
547 else if (sucessor > 0 && sucessor < sucessores - 1) { // no meio e continua
548 DebugRamo(' ', duplo ? '#' : '+');
549 ramo.Last() = (duplo ? '/' : '|');
550 }
551 else {
552 DebugRamo(' ', duplo ? '#' : '+'); // no fim, vai acabar
553 ramo.Last() = ' '; // a ser impresso nesta posição nas linhas seguintes
554 }
555 }
556}
557
558void TProcuraConstrutiva::DebugRamo(char ramo, char folha) {
559 for (int i = 0; i < espacosRamo; i++)
560 printf("%c", ramo);
561 printf("%c", folha);
562}
563
564
565// Metodo para ser chamado quando nao ha sucessores ou ha um corte de profundidade
566void TProcuraConstrutiva::DebugCorte(int sucessores, bool duplo)
567{
568 if (Parametro(nivelDebug) >= passos) {
569 if (sucessores < 0) {
571 printf("%c ", '='); // corte de profundidade
572 DebugEstado();
574 Debug();
575 }
576 }
577 else if (sucessores > 0)
578 ramo.Pop();
579 else if (Parametro(nivelDebug) < completo) { // ramo em que nao e possivel continuar
580 printf("%c ", '&');
581 DebugEstado();
583 Debug();
584 }
585 }
586}
587
588// Encontrou uma solucao
590{
592 printf(" Solução encontrada!");
593 if (!continuar)
594 ramo.Count(0);
595 Debug();
596 printf("(g:%d)", custo);
597 }
598 else {
600 Debug();
602 ramo.Pop();
603 }
604}
605
606// Informacao de debug na chamada ao metodo recursivo
608{
609 if (Parametro(nivelDebug) == atividade && expansoes % 1000 == 0)
610 printf("#");
612 // neste nível, cada estado expandido é visualizado, não apenas os estados folha
613 DebugEstado();
614 if (pai != NULL)
615 printf(" %s", pai->Acao(this)); // mostra sempre a ação
616 if (Parametro(verAcoes) == 1 || pai == NULL)
617 Debug();
618 NovaLinha();
619 }
620}
621
622// Chamar sempre que se quer uma nova linha com a arvore em baixo
624{
625 printf("\n");
626 for (int i = 0; i < ramo.Count() - (tudo ? 0 : 1); i++)
627 printf("%*s%c", espacosRamo, " ", ramo[i]);
628}
629
630// Passo no algoritmo em largura
632{
633 if (Parametro(nivelDebug) == atividade && expansoes % 1000 == 0)
634 printf("#");
635 if (Parametro(nivelDebug) >= passos) {
636 printf("\n");
637 DebugEstado();
638 }
640 Debug();
641}
642// Mostrar sucessores
644 if (Parametro(verAcoes) > 2) {
645 // mostrar apenas ações
646 printf("\nAções: ");
647 for (int i = 0; i < sucessores.Count() && i < 30; i++) {
648 printf("%s ", Acao(sucessores[i]));
649 if (i % 10 == 9)
650 printf("\n ");
651 }
652 }
653 else {
654 ramo.Count(0);
655 ramo.Add(' ');
656 for (int i = 0; i < sucessores.Count() && i < 30; i++) {
657 ramo.First() = '+';
658 NovaLinha();
659 sucessores[i]->DebugEstado(i + 1);
660 if (i < sucessores.Count() - 1)
661 ramo.First() = '|';
662 else
663 ramo.First() = ' ';
664 printf(" %s", Acao(sucessores[i])); // mostra sempre a ação
665 if (Parametro(verAcoes) == 1)
666 sucessores[i]->Debug();
667 }
668 ramo.Count(0);
669
670 }
671}
672
673
674// uma nova iteração de um algoritmo iterativo
677 printf("\n");
679 printf("\nIteração %d:", iteracao);
681 printf(" (expansões %d, gerações %d, avaliações %d)\n", expansoes, geracoes, iteracoes);
682 else
683 printf("\n");
684 }
685}
686
687// informação geral sobre o estado
688void TProcuraConstrutiva::DebugEstado(int id, int pai) {
689 if (id >= 0) {
690 printf("#%d ", id);
691 if (pai >= 0)
692 printf("(#%d) ", pai);
693 }
694 printf("g:%d ", custo);
695 if (heuristica)
696 printf("h:%d ", heuristica);
697
698 if (expansoes)
699 printf("%d", expansoes);
700 if (geracoes)
701 printf("|%d", geracoes);
702 if (iteracoes)
703 printf("|%d", iteracoes);
704}
705
706
707// Chamar antes de iniciar uma procura
709{
711 geracoes = expansoes = 0;
712 ramo.Count(0);
713 while (caminho.Count() > 0)
714 delete caminho.Pop();
715 if (solucao != NULL)
716 delete solucao;
717 solucao = NULL;
718 LimparHT();
719}
720
721
723 int resultado = -1;
724 switch (Parametro(algoritmo)) {
725 case 1: resultado = LarguraPrimeiro(Dominio(parametro[limite].valor, 0)); break;
726 case 2: resultado = CustoUniforme(Dominio(parametro[limite].valor, 0)); break;
727 case 3: resultado = ProfundidadePrimeiro(parametro[limite].valor); break;
728 case 4: resultado = MelhorPrimeiro(parametro[limite].valor); break;
729 case 5: resultado = AStar(Dominio(parametro[limite].valor, 0)); break;
730 case 6: resultado = IDAStar(Dominio(parametro[limite].valor, 0)); break;
731 case 7: resultado = BranchAndBound(Dominio(parametro[limite].valor, 0)); break;
732 }
733 return custo = resultado;
734}
735
736
737
739{
741 if (solucao != NULL) {
743 delete solucao;
744 solucao = NULL;
745 }
746}
747
748
752 int opcao = 0;
754 do {
755 caminho.Add(Duplicar());
756 if (caminho.Count() > 1)
757 caminho.Last()->custo += caminho[caminho.Count() - 2]->custo;
758 else
759 caminho.Last()->custo = 0;
763 // linha com informação
764 DebugEstado();
765 Debug();
767 if (sucessores.Count() == 0) {
768 printf("\nSem sucessores.");
769 opcao = 0;
770 }
771 else {
772 char str[BUFFER_SIZE];
773 printf("\nSucessor [1-%d, ação(ões), exe]:", sucessores.Count());
775 opcao = atoi(str);
776 if (opcao == 0 && strlen(str) > 1) {
777 char* token;
778 opcao = sucessores.Count() + 1;
779 token = strtok(str, " \t\n\r");
780 // executar algoritmo
781 if (strcmp(token, "exe") == 0) {
783 backup = caminho;
784 caminho.Count(0);
786 int resultado;
787 switch (resultado = ExecutaAlgoritmo()) {
788 case -1: printf("Impossível\n"); break;
789 case -2: printf("Não resolvido\n"); break;
790 default: printf("Resolvido (%d)\n", resultado); break;
791 }
792 if (solucao != NULL) {
794 delete backup.Pop();
795 backup += caminho;
796 caminho = backup;
797 caminho.Pop(); // este último estado será adicionado
798 }
799 else
800 caminho = backup;
801 }
802 else {
803 int nAcoes = 0;
804 do {
805 // executar a ação
806 if (Acao(token))
807 nAcoes++;
808 else {
809 printf("Ação %s inválida.\n", token);
810 break;
811 }
812 token = strtok(NULL, " \t\n\r");
813
814 if (token != NULL) {
815 // há outra ação, é preciso atualizar o caminho
816 caminho.Add(Duplicar());
817 if (caminho.Count() > 1)
818 caminho.Last()->custo += caminho[caminho.Count() - 2]->custo;
819 else
820 caminho.Last()->custo = 0;
821 }
822
823 } while (token != NULL);
824 if (nAcoes > 0)
825 printf("Executadas %d ações com sucesso.\n", nAcoes);
826 }
827 }
828 }
829 if (opcao > 0 && opcao <= sucessores.Count())
830 Copiar(sucessores[opcao - 1]);
832 } while (opcao != 0);
833}
834
836 // utilizando FNV-1 hash (http://www.isthe.com/chongo/tech/comp/fnv/)
837 uint32_t h = 2166136261;
839 for (int i = 0; i < OBJETO_HASHTABLE && estadoCodHT[i]; i++) {
840 uint64_t valor = estadoCodHT[i];
841 // processar cada octeto
842 // quando o valor fica 0, já não interessa
843 // já que existindo dados, são distintos de 0
844 for (int i = 0; i < 8 && valor; i++) {
845 unsigned char octeto = valor & 255;
846 valor >>= 8;
847 h *= 16777619;
848 h ^= octeto;
849 }
850 }
851 return h % TAMANHO_HASHTABLE;
852}
853
856 if (Parametro(nivelDebug) >= 1) {
857 int usado = 0; // contar para calcular taxa de ocupação
858 for (int i = 0; i < TAMANHO_HASHTABLE; i++) {
859 bool limpo = true;
860 for (int j = 0; j < tamanhoCodificado; j++)
861 if (elementosHT[i][j] != 0) {
862 limpo = false;
863 elementosHT[i][j] = 0;
864 }
865 if (!limpo)
866 usado++;
867 }
868 // reportar estatísticas se existir muito reuso
869 if (usado > 0 && usado * 2 <= colocadosHT) {
870 printf("\nHT: utilização %d%%, reuso: %.2f vezes",
871 usado * 100 / TAMANHO_HASHTABLE,
872 1.0 * colocadosHT / usado);
873 }
874 }
875 else
876 for (int i = 0; i < TAMANHO_HASHTABLE; i++)
877 for (int j = 0; j < tamanhoCodificado; j++)
878 elementosHT[i][j] = 0;
879 colocadosHT = 0;
880 // coloca o estado atual na hasttable, para não ser gerado
881 ExisteHT();
882 }
883}
884
886 // caso não exista, retorna falso e insere
887 // se existe retorna verdade, e estiver lá outro elemento, substitui
888 unsigned int original = Hash();
889 unsigned int indice = original % TAMANHO_HASHTABLE;
890 for (int i = 0; i < tamanhoCodificado; i++)
891 if (elementosHT[indice][i] != estadoCodHT[i]) {
892 SubstituirHT(indice);
893 colocadosHT++;
894 return false; // não existia
895 }
896 // elemento é igual, mas se o custo for mais alto, não conta
897 // já que este elemento com custo mais baixo, pode conduzir à solução ou melhores soluções
898 // neste caso substitui e retorna que o estado não existe
899 if (custoHT[indice] > custo) {
900 SubstituirHT(indice);
901 return false; // existe mas com um custo mais alto
902 }
903 return true; // igual, estado já analisado
904}
905
907{
908 // substituir elemento
909 for (int i = 0; i < tamanhoCodificado; i++)
910 elementosHT[indice][i] = estadoCodHT[i];
911 custoHT[indice] = custo;
912}
913
914// estados repetidos: verificar todos os gerados
915// implementar para utilizar hashtables com perdas
916// converte o estado atual para a variável estado, utilizando o menor espaço possível
917// caso existam simetrias, normalizar o estado antes de codificar, para considerar exploradas todas as versões
919 for (int i = 0; i < tamanhoCodificado; i++)
920 estado[i] = 0;
921}
922
924{
925 if (id == indCusto)
926 return custo;
927 else if (id == indExpansoes)
928 return expansoes;
929 else if (id == indGeracoes)
930 return geracoes;
931 else if (id == indLowerBound)
932 return lowerBound;
933 return TProcura::Indicador(id);
934}
935
936
937
#define BUFFER_SIZE
@ 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
#define OBJETO_HASHTABLE
@ detalhe
Debug detalhada sobre estados e decisões.
Definition TProcura.h:66
@ atividade
Apenas eventos principais.
Definition TProcura.h:64
@ completo
Mostra toda a execução detalhadamente.
Definition TProcura.h:67
@ passos
Exibe passos intermediários.
Definition TProcura.h:65
@ nada
Sem informações de debug.
Definition TProcura.h:63
@ nivelDebug
Nível de debug, de reduzido a completo.
Definition TProcura.h:43
@ algoritmo
Algoritmo base a executar.
Definition TProcura.h:42
Lista ordenada de nós para algoritmos de procura informada.
Definition CListaNo.h:23
Representa um estado no espaço de estados.
void DebugCorte(int sucessores=-1, bool duplo=false)
void DebugSucessores(TVector< TNo > &sucessores)
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.
Definition TProcura.h:467
static int Dominio(int &variavel, int min=INT_MIN, int max=INT_MAX)
Limita o domínio de um parâmetro inteiro.
Definition TProcura.cpp:941
static int resultado
Resultado retornado pelo algoritmo na última execução.
Definition TProcura.h:459
virtual int Indicador(int id)
Retorna um indicador, após a execução do algoritmo.
Definition TProcura.cpp:74
static int iteracoes
Número total de iterações realizadas na última execução.
Definition TProcura.h:463
virtual void ResetParametros()
Inicializa os parametros, indicadores e instâncias.
Definition TProcura.cpp:37
virtual bool Parar(void)
Verifica se a procura deve ser interrompida.
Definition TProcura.h:336
virtual void ExecucaoTerminada(clock_t inicio)
Chamar após a execução do algoritmo. Grava o tempo consumido.
Definition TProcura.cpp:879
virtual void Debug(void)
Mostra o estado no ecrã, para debug.
Definition TProcura.cpp:87
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 ...
Definition TProcura.h:454
static TVector< int > indAtivo
Definition TProcura.h:455
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...
Definition TProcura.cpp:94
static TVector< TParametro > parametro
Parâmetros a serem utilizados na configuração atual.
Definition TProcura.h:451
int Parametro(int id)
Definition TProcura.h:479
Item & First()
Definition TVector.h:154
Item & Pop()
Definition TVector.h:127
TVector< Item > & Add(Item a)
Definition TVector.h:115
Item & Last()
Definition TVector.h:157
int Count() const
Definition TVector.h:160
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.
int AStar(int limite=0)
Executa a procura A*, algoritmo informado.
int IDAStar(int upperBound=0)
Executa a procura IDA*, algoritmo informado.
int MelhorPrimeiro(int nivel=0)
Executa a procura melhor primeiro, algoritmo informado.
int BranchAndBound(int upperBound=0)
Executa o algoritmo Branch-and-Bound, um algoritmo informado.
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.
Definition TRand.cpp:46