Ayuda grafo virtual
Publicado por daniel (3 intervenciones) el 05/01/2016 12:13:12
Buenas. Estoy realizando un trabajo de universidad, donde el problema es:
Disponemos de un tablero lineal con N casillas. También dispondremos de N-l fichas
numeradas de 1 a N-1. Inicialmente las fichas están colocadas de forma aleatoria en
cualquier posición del tablero dejando siempre una casilla como hueco. El objetivo del
juego será mover o hacer saltar las fichas, utilizando el menor número posible de
movimientos, de forma que se llegue a un tablero objetivo. Las fichas solo podrán hacer
los siguientes movimientos:
1) Desplazarse a una casilla vacía contigua.
2) Saltar por encima de otra ficha y posicionarse en la casilla vacía
Ejemplo:
Tablero inicial: -1,1,2,3,4,5,6
Tablero objetivo: -1,6,5,4,3,2,1
Secuenciada de desplazamientos y saltos (el valor -1 representa la casilla vacía):
-1,1,2,3,4,5,6
1,-1,2,3,4,5,6
1,3,2,-1,4,5,6
1,3,2,5,4,-1,6
1,3,2,5,4,6,-1
1,3,2,5,-1,6,4
1,3,-1,5,2,6,4
-1,3,1,5,2,6,4
3,-1,1,5,2,6,4
3,5,1,-1,2,6,4
3,5,1,6,2,-1,4
3,5,1,6,2,4,-1
3,5,1,6,-1,4,2
3,5,-1,6,1,4,2
-1,5,3,6,1,4,2
5,-1,3,6,1,4,2
5,6,3,-1,1,4,2
5,6,3,4,1,-1,2
5,6,3,4,1,2,-1
5,6,3,4,-1,2,1
5,6,-1,4,3,2,1
-1,6,5,4,3,2,1
Me dan un codigo, donde solo tengo que rellenar getNeighborListOf y isNeighbor.La duda es que debo añadir
en getNeighborListOf para que no solo muestre los movimientos vecinos, sino tambien los movimientos con
saltos.
Disponemos de un tablero lineal con N casillas. También dispondremos de N-l fichas
numeradas de 1 a N-1. Inicialmente las fichas están colocadas de forma aleatoria en
cualquier posición del tablero dejando siempre una casilla como hueco. El objetivo del
juego será mover o hacer saltar las fichas, utilizando el menor número posible de
movimientos, de forma que se llegue a un tablero objetivo. Las fichas solo podrán hacer
los siguientes movimientos:
1) Desplazarse a una casilla vacía contigua.
2) Saltar por encima de otra ficha y posicionarse en la casilla vacía
Ejemplo:
Tablero inicial: -1,1,2,3,4,5,6
Tablero objetivo: -1,6,5,4,3,2,1
Secuenciada de desplazamientos y saltos (el valor -1 representa la casilla vacía):
-1,1,2,3,4,5,6
1,-1,2,3,4,5,6
1,3,2,-1,4,5,6
1,3,2,5,4,-1,6
1,3,2,5,4,6,-1
1,3,2,5,-1,6,4
1,3,-1,5,2,6,4
-1,3,1,5,2,6,4
3,-1,1,5,2,6,4
3,5,1,-1,2,6,4
3,5,1,6,2,-1,4
3,5,1,6,2,4,-1
3,5,1,6,-1,4,2
3,5,-1,6,1,4,2
-1,5,3,6,1,4,2
5,-1,3,6,1,4,2
5,6,3,-1,1,4,2
5,6,3,4,1,-1,2
5,6,3,4,1,2,-1
5,6,3,4,-1,2,1
5,6,-1,4,3,2,1
-1,6,5,4,3,2,1
Me dan un codigo, donde solo tengo que rellenar getNeighborListOf y isNeighbor.La duda es que debo añadir
en getNeighborListOf para que no solo muestre los movimientos vecinos, sino tambien los movimientos con
saltos.
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
package us.lsi.astar.fpermutas;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.Stream;
import us.lsi.graphs.SimpleEdge;
import us.lsi.graphs.VirtualVertex;
import com.google.common.collect.Lists;
public class EstadoPermutaFichas implements
VirtualVertex<EstadoPermutaFichas, SimpleEdge<EstadoPermutaFichas>> {
public static EstadoPermutaFichas create(Integer... d) {
return new EstadoPermutaFichas(d);
}private Integer[] datos;
private int phueco;
public static int numFichas = 6;private EstadoPermutaFichas(Integer... d) {
super();
this.datos = new Integer[EstadoPermutaFichas.numFichas+1];
if (Stream.of(d).distinct().count() != (EstadoPermutaFichas.numFichas )+1)
throw new IllegalArgumentException("Existen piezas repetidas");
int i = 0;for (int e : d) {
if (e < -1
|| e > (EstadoPermutaFichas.numFichas)) {
throw new IllegalArgumentException("Pieza fuera de rango");
}if (e == -1) {
this.phueco = i;
}this.datos[i]=e;
i++;
} }public EstadoPermutaFichas(Integer[] datos, int phueco) {
super();
this.datos = datos;
this.phueco = phueco;
}public Integer getFicha(int i) {
if (i < 0 || i >= EstadoPermutaFichas.numFichas+1)
throw new IllegalArgumentException();
return datos[i];
}public EstadoPermutaFichas getVecino(int f) {
if (f < 0 || f >= EstadoPermutaFichas.numFichas+1 || datos[f]==-1)
throw new IllegalArgumentException();
Integer[] dd = new Integer[EstadoPermutaFichas.numFichas+1];
for (int i = 0; i < EstadoPermutaFichas.numFichas+1; i++) {
dd[i] = datos[i];
}dd[phueco] = datos[f];
dd[f] = datos[phueco];
return new EstadoPermutaFichas(dd, f);
}@Override
public Set<EstadoPermutaFichas> getNeighborListOf() {
List<Integer> ls = Lists.newArrayList(-2, -1, 1, 2);
return
ls
.stream().
map( x ->x+ this.phueco)
.filter( x -> x == -1 && x>=1
&& x <= EstadoPermutaFichas.numFichas+1 )
.<EstadoPermutaFichas> map(
x -> this.getVecino(x)) //DUDA
.collect(Collectors.<EstadoPermutaFichas> toSet());
}public Set<SimpleEdge<EstadoPermutaFichas>> edgesOf() {
return this
.getNeighborListOf()
.stream()
.<SimpleEdge<EstadoPermutaFichas>> map(
x -> SimpleEdge.<EstadoPermutaFichas> create().createEdge(
this, x))
.collect(Collectors.<SimpleEdge<EstadoPermutaFichas>> toSet());
}@Override
public boolean isNeighbor(EstadoPermutaFichas e) {
return this.getNumCasillasDiferentes(e) == 2
&& (Math.abs(this.phueco - e.phueco) == 1 || Math.abs(this.phueco - e.phueco) == 2);
}public boolean isValid() {
return true;
}public Integer getNumCasillasDiferentes(EstadoPermutaFichas e) {
Integer s = 0;for (int i = 0; i < EstadoPermutaFichas.numFichas+1; i++) {
if (!this.datos[i].equals(e.datos[i])) {
s++;
} }return s;
}public int getHuecoPos() {
return phueco;
}@Override
public int hashCode() {
final int prime = 31; int result = 1;result = prime * result + Arrays.deepHashCode(datos);
return result;
}@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (!(obj instanceof EstadoPermutaFichas))
return false;
EstadoPermutaFichas other = (EstadoPermutaFichas) obj;
if (!Arrays.deepEquals(datos, other.datos))
return false;
return true;
}@Override
public String toString() {
String s = "";
for (int i = 0; i < datos.length; i++) {
if (i < datos.length - 1) {
s = s + datos[i] + ",";
} else {
s = s + datos[i] + "\n";
} }return s;
}}Valora esta pregunta
0