TProcura
Biblioteca em C++ para testes paramétricos de algoritmos, e coleção de algoritmos de procura e otimização
Loading...
Searching...
No Matches
OitoDamas.h
Go to the documentation of this file.
1#pragma once
2#include "../TProcuraMelhorativa.h"
3#include "../TCodificacaoInteira.h"
4#include "../TCodificacaoPermutacao.h"
5
7// COitoDamas class
9// Author: José Coelho
10// Last revision: 2025-01-30
11// Description:
12// Implementa o problema das oito damas. Este problema consiste em colocar
13// oito damas de xadrez (movem-se na horizontal, vertical e diagonal), num
14// tabuleiro de xadrez, sem que estas se ataquem umas as outras.
15// Generalizado para N damas, o ID da instância é o número de damas
17
18constexpr int MAX_DAMAS = 40;
19
20class COitoDamas :
22{
23public:
26
27 // estrutura de dados: posicao de cada dama
29 static int nDamas; // número de damas desta instância
30
31 // Metodos virtuais redefinidos
34 if (clone != NULL)
35 clone->Copiar(this);
36 else
37 memoriaEsgotada = true;
38 return clone;
39 }
40
46
47 void Inicializar(void);
48 bool SolucaoCompleta(void) const { return damas.Count() == nDamas; }
49 void Debug(bool completo = true) override;
50 void MostrarSolucao(void) { Debug(); }
55
56 // metodos virtuais redefinidos de TProcuraMelhorativa
57
58 void NovaSolucao(void);
59 int Avaliar(void);
61 void Mutar(void);
62 void Cruzamento(TPonto a, TPonto b);
63 int Distancia(TPonto a);
64
65private:
66 // métodos de normalização de um estado
67 void Normalizar(TVector<int>& damas); // coloca em damas o estado normalizado
68 int PesoVersao(int tab[MAX_DAMAS][MAX_DAMAS]); // peso da versão do estado
69 void Simetria(int tab[MAX_DAMAS][MAX_DAMAS], int eixo); // aplica uma simetria
70 void Troca(int& a, int& b); // troca dois valores
71};
72
73// versão com codificação inteira
76{
77public:
80
81 int Avaliar(void) {
82 custo = 0;
84 // calcular o numero de pares de damas atacadas
85 for (int i = 0; i < nElementos - 1; i++)
86 for (int j = i + 1; j < nElementos; j++)
87 if (estado[i] == estado[j] || estado[i] - estado[j] == i - j || estado[i] - estado[j] == j - i)
88 custo++;
89 return custo;
90 }
91
96
99 if (clone != NULL)
100 clone->Copiar(this);
101 else
102 memoriaEsgotada = true;
103 return clone;
104 }
105
106 // deve carregar a instância, para variáveis estáticas, da subclasse
107 // definir valores globais: nElementos
115
116 void Debug(bool completo) {
117 if (!completo) {
119 return;
120 }
121 for (int i = 0; i < nElementos; i++) {
122 printf("\n");
123 for (int j = 0; j < nElementos; j++) {
124 int cor = ((i + j) % 2 ? ' ' : ':');
125 if (estado.Count() > i && estado[i] == j)
126 printf("%c%c", '#', '#');
127 else
128 printf("%c%c", cor, cor);
129 }
130 }
131 printf("\n");
132 }
133
134};
135
136// versão com codificação por permutação
139{
140public:
143
144 int Avaliar(void) {
145 custo = 0;
147 // calcular o numero de pares de damas atacadas
148 for (int i = 0; i < nElementos - 1; i++)
149 for (int j = i + 1; j < nElementos; j++)
150 if (estado[i] - estado[j] == i - j || estado[i] - estado[j] == j - i)
151 custo++;
152 return custo;
153 }
154
157 if (clone != NULL)
158 clone->Copiar(this);
159 else
160 memoriaEsgotada = true;
161 return clone;
162 }
163
164 // deve carregar a instância, para variáveis estáticas, da subclasse
165 // definir valores globais: nElementos
171
176
177 void Debug(bool completo) {
178 if (!completo) {
180 return;
181 }
182 for (int i = 0; i < nElementos; i++) {
183 printf("\n");
184 for (int j = 0; j < nElementos; j++) {
185 int cor = ((i + j) % 2 ? ' ' : ':');
186 if (estado.Count() > i && estado[i] == j)
187 printf("%c%c", '#', '#');
188 else
189 printf("%c%c", cor, cor);
190 }
191 }
192 printf("\n");
193 }
194
195};
196
constexpr int MAX_DAMAS
Definition OitoDamas.h:4
constexpr int MAX_DAMAS
Definition OitoDamas.h:18
void Debug(bool completo)
Mostra o estado no ecrã, para debug.
Definition OitoDamas.h:116
TPonto Duplicar(void)
Cria um objecto que é uma cópia deste.
Definition OitoDamas.h:97
void Inicializar(void)
Coloca o objecto no estado inicial da procura.
Definition OitoDamas.h:108
int Avaliar(void)
Definition OitoDamas.h:81
void ResetParametros()
Inicializa os parametros, indicadores e instâncias.
Definition OitoDamas.h:92
int Avaliar(void)
Definition OitoDamas.h:144
void Inicializar(void)
Coloca o objecto no estado inicial da procura.
Definition OitoDamas.h:166
TPonto Duplicar(void)
Cria um objecto que é uma cópia deste.
Definition OitoDamas.h:155
void Debug(bool completo)
Mostra o estado no ecrã, para debug.
Definition OitoDamas.h:177
void ResetParametros()
Inicializa os parametros, indicadores e instâncias.
Definition OitoDamas.h:172
Representa um estado do problema das 8 damas.
Definition OitoDamas.h:15
void Cruzamento(TPonto a, TPonto b)
Definition OitoDamas.cpp:78
bool SolucaoCompleta(void) const
Definition OitoDamas.h:48
void Copiar(TPonto objecto)
Fica com uma cópia do objecto.
Definition OitoDamas.h:41
void Debug(bool completo=true) override
Mostra o estado no ecrã, para debug.
TPonto Duplicar(void)
Cria um objecto que é uma cópia deste.
Definition OitoDamas.h:32
static int nDamas
Definition OitoDamas.h:22
void Inicializar(void)
Coloca o objecto no estado inicial da procura.
void Vizinhanca(TVector< TPonto > &vizinhos)
Definition OitoDamas.cpp:59
void Mutar(void)
Definition OitoDamas.cpp:72
void NovaSolucao(void)
Definition OitoDamas.cpp:39
int Distancia(TPonto a)
Definition OitoDamas.cpp:89
~COitoDamas(void)
TVector< int > damas
Definition OitoDamas.h:21
void MostrarSolucao(void)
definir para visualizar a solução
Definition OitoDamas.h:50
int Avaliar(void)
Definition OitoDamas.cpp:47
void ResetParametros()
Inicializa os parametros, indicadores e instâncias.
Definition OitoDamas.h:51
void Copiar(TProcuraConstrutiva *objecto)
Definition OitoDamas.h:27
COitoDamas(void)
void Debug(bool completo=true) override
Mostra o estado no ecrã, para debug.
static TVector< int > maxValor
void ResetParametros()
Inicializa os parametros, indicadores e instâncias.
void Copiar(TPonto objecto)
Fica com uma cópia do objecto.
void Debug(bool completo=true) override
Mostra o estado no ecrã, para debug.
void ResetParametros()
Inicializa os parametros, indicadores e instâncias.
void Copiar(TPonto objecto)
Fica com uma cópia do objecto.
virtual void Copiar(TPonto objecto)
Fica com uma cópia do objecto.
void Inicializar(void)
Inicializar a instância. No final, chamar NovaSolucao() para inicializar o estado.
virtual int Avaliar(void)
int custo
Custo total, atualizada após Avaliar()
void ResetParametros() override
Inicializa os parametros, indicadores e instâncias.
static bool memoriaEsgotada
Flag indicando problemas de memória esgotada.
Definition TProcura.h:501
static int resultado
Resultado retornado pelo algoritmo na última execução.
Definition TProcura.h:493
static TParametro instancia
ID da instância atual, a ser utilizado em SolucaoVazia().
Definition TProcura.h:24
TVector< Item > & Reset(Item const &i)
Preenche todo o vetor com um mesmo valor.
Definition TVector.h:784
int Count() const
Definition TVector.h:227
int valor
valor do parametro
Definition TProcura.h:139