-
Notifications
You must be signed in to change notification settings - Fork 8
/
Canibais.R
96 lines (70 loc) · 2.59 KB
/
Canibais.R
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
source("Estado.R")
## Classe e métodos para o problema dos 3 Missionários e 3 Canibais
Canibais <- function(desc = NULL, pai = NULL){
e <- environment()
assign("desc", desc, envir = e)
assign("pai", pai, envir = e)
assign("g", 0, envir = e)
assign("h", Inf, envir = e)
assign("f", Inf, envir = e)
class(e) <- c("Canibais", "Estado")
return(e)
}
## Sobrecarregando o operador "==" para comparação entre estados
Ops.Canibais = function(obj1,obj2){
if(.Generic == "=="){
return(all(obj1$desc == obj2$desc))
}
}
## Sobrecarga da função genérica "print" do R
print.Canibais <- function(obj) {
cat("(M C B): (", obj$desc, ")\n")
cat("G(n): ", obj$g, "\n")
cat("H(n): ", obj$h, "\n")
cat("F(n): ", obj$f, "\n")
}
## Sobrecarga da função genérica "heuristica", definida por Estado.R
heuristica.Canibais <- function(atual){
if(is.null(atual$desc))
return(Inf)
## h(obj) = M + C + B
return(sum(atual$desc))
}
geraFilhos.Canibais <- function(obj) {
filhos <- list()
filhosDesc <- list()
desc <- obj$desc
bAtual <- as.numeric(desc[3])
bNovo <- as.numeric(bAtual != 1)
## gera filhos usando todos os operadores
if(bAtual == 1){
operadores <- list(c(2,0,bAtual), c(0,2,bAtual), c(1,1,bAtual), c(1,0,bAtual), c(0,1,bAtual))
filhosDesc <- lapply(operadores, function(op) desc-op)
} else {
operadores <- list(c(2,0,bNovo), c(0,2,bNovo), c(1,1,bNovo), c(1,0,bNovo), c(0,1,bNovo))
filhosDesc <- lapply(operadores, function(op) desc+op)
}
## verifica estados filhos incompatíveis com o problema
incompativeis <- sapply(1:length(filhosDesc),
function(i) {
fDesc <- filhosDesc[[i]]
if((fDesc['C'] > fDesc['M']) || ## Se #Canibais > #Missionários OU
(any(fDesc[1:2] > 3)) || ## #Canibais ou #Missionários > 3 OU
(any(fDesc[1:2] < 0))) ## #Canibais ou #Missionarios < 0 então
i ## é incompatível: retorna índice
else
0 ## senão é compatível
})
## mantém no vetor apenas os que são incompatíveis
incompativeis <- incompativeis[incompativeis != 0]
## remove estados filhos incompatíveis
filhosDesc <- filhosDesc[-incompativeis]
## gera os objetos Canibais para os filhos
for(filhoDesc in filhosDesc){
filho <- Canibais(desc = filhoDesc, pai = obj)
filho$h <- heuristica(filho)
filho$g <- obj$g + 1
filhos <- c(filhos, list(filho))
}
return(filhos)
}