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.cpp
Go to the documentation of this file.
1#include "OitoDamas.h"
2#include <stdio.h>
3#include <string.h>
4
5int COitoDamas::nDamas = 8; // número de damas desta instância
6
8{
9}
10
12{
13}
14
16{
18 damas = {};
21}
22
23
24void COitoDamas::Debug(bool completo)
25{
26 for (int i = 0; i < nDamas; i++) {
27 printf("\n");
28 for (int j = 0; j < nDamas; j++) {
29 int cor = ((i + j) % 2 ? ' ' : ':');
30 if (damas.Count() > i && damas[i] == j)
31 printf("%c%c", '#', '#');
32 else
33 printf("%c%c", cor, cor);
34 }
35 }
36}
37
38// e gerada uma nova solucao aleatoriamente.
40{
42 for (int i = 0; i < nDamas; i++)
44}
45
46// Retorna o valor da solucao completa actual.
48{
49 custo = 0;
51 // calcular o numero de pares de damas atacadas
52 for (int i = 0; i < nDamas - 1; i++)
53 for (int j = i + 1; j < nDamas; j++)
54 if (damas[i] == damas[j] || damas[i] - damas[j] == i - j || damas[i] - damas[j] == j - i)
55 custo++;
56 return custo;
57}
58
60{
61 // trocar a posicao de cada dama
62 for (int i = 0; i < nDamas; i++)
63 for (int j = 0; j < nDamas; j++)
64 if (j != damas[i]) {
66 vizinho->damas[i] = j;
68 }
70}
71
73{
74 // trocar a posicao de uma das damas (50%)
76}
77
79{
80 int divisao = 1 + TRand::rand() % (nDamas - 2); // divisao tem de ter elementos de um e de outro
81 damas.Count(8);
82 for (int i = 0; i < divisao; i++)
83 damas[i] = ((COitoDamas*)a)->damas[i];
84 for (int i = divisao; i < 8; i++)
85 damas[i] = ((COitoDamas*)b)->damas[i];
87}
88
90{
91 int distancia = 0;
92 for (int i = 0; i < nDamas; i++)
93 if (damas[i] != ((COitoDamas*)a)->damas[i])
94 distancia++;
95 return distancia;
96}
97
98
Representa um estado do problema das 8 damas.
Definition OitoDamas.h:15
void Cruzamento(TPonto a, TPonto b)
Definition OitoDamas.cpp:78
void Debug(bool completo=true) override
Mostra o estado no ecrã, para debug.
Definition OitoDamas.cpp:70
static int nDamas
Definition OitoDamas.h:22
void Inicializar(void)
Coloca o objecto no estado inicial da procura.
Definition OitoDamas.cpp:24
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)
Definition OitoDamas.cpp:10
TVector< int > damas
Definition OitoDamas.h:21
TProcuraConstrutiva * Duplicar(void)
Cria um objecto que é uma cópia deste.
Definition OitoDamas.cpp:14
int Avaliar(void)
Definition OitoDamas.cpp:47
COitoDamas(void)
Definition OitoDamas.cpp:6
virtual void Cruzamento(TPonto a, TPonto b)
void Inicializar(void)
Inicializar a instância. No final, chamar NovaSolucao() para inicializar o estado.
virtual int Avaliar(void)
virtual void Vizinhanca(TVector< TPonto > &vizinhos)
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
int Count() const
Definition TVector.h:227
int custo
Custo total acumulado desde o estado inicial.
unsigned int rand(int seq)
Retorna o próximo valor pseudo-aleatório.
Definition TRand.cpp:46
int valor
valor do parametro
Definition TProcura.h:139