Ya hemos hablado de la búsqueda de coste uniforme BCU, de la búsqueda en amplitud BFS y la búsqueda en profundidad DFS. De esta última, podríamos aplicarle ciertas modificaciones, para que sea iterativa y por otro lado añadirle una limitación de profundidad.
Porque limitamos la profundidad de la búsqueda ?. Uno de los posibles problemas que nos podríamos encontrar en las búsqueda en profundidad es un espacio de estados infinito y realmente no creo que queramos entrar en una búsqueda infinita.
Por eso aveces nos vemos con la necesidad, de limitar nuestras búsquedas hasta recorrer cierto nivel de estados
ESCENARIO
En este caso, vamos a partir del código que se publicó en el post de búsqueda en profundidad DFS, lo modificaremos para que sea iterativo y luego le pondremos un límite de profundidad.
De esta manera, tendremos lo que esperamos. Aquí debajo, tenéis el punto de partida, por si no queréis entrar en el otro post, aunque lo aconsejo «fuertemente«
private final Stack<NodeDFS> nodeDFS = new Stack<>();
private final List<NodeDFS> visited = new LinkedList<>();
Optional<NodeDFS> search(final int[] initialState, final int[] finalState) {
if(isNull(initialState)) {
throw new NullPointerException("initialState shouldn't be null");
}
if(isNull(finalState)) {
throw new NullPointerException("finalState shouldn't be null");
}
boolean foundFinalState = false;
Optional<NodeDFS> foundNode = Optional.empty();
final NodeDFS root = NodeDFS.of(initialState);
nodeDFS.add(root);
while(!foundFinalState && nodeDFS.size() != 0) {
final NodeDFS nodeDFS = this.nodeDFS.pop();
visited.add(nodeDFS);
if(Arrays.equals(nodeDFS.getState(), finalState)) {
foundFinalState = true;
foundNode = Optional.of(nodeDFS);
} else {
int[] nodeState = nodeDFS.getState();
this.processChild(new int[]{nodeState[1],nodeState[0],nodeState[2],nodeState[3]}, nodeDFS);
this.processChild(new int[]{nodeState[0],nodeState[2],nodeState[1],nodeState[3]}, nodeDFS);
this.processChild(new int[]{nodeState[0],nodeState[1],nodeState[3],nodeState[2]}, nodeDFS);
}
}
return foundNode;
}
private void processChild(final int[] state, final NodeDFS nodeDFS) {
final NodeDFS nodeDFSChild = NodeDFS.of(state);
nodeDFSChild.setParent(nodeDFS);
if(!this.nodeDFS.contains(nodeDFSChild) && !visited.contains(nodeDFSChild)) {
this.nodeDFS.add(nodeDFSChild);
}
}
Ese sería nuestro código para la búsqueda en profundidad, lo tenéis versionado en: github. Realmente, no necesitamos un gran «nivel» programación para, pasar este algoritmo a iterativo, pero siempre resulta interesante, ver cómo evoluciona un algoritmo.
LA VERSIÓN ITERATIVA
Paras hacer transformar el while en una búsqueda iterativa, tan sólo tenemos que extraer esta parte en un método a parte
private Optional<NodeDFS> iterativeSearch() {
while(!foundFinalState && nodeBFS.size() != 0) {
final NodeBFS nodeDFS = this.nodeBFS.poll();
visited.add(nodeDFS);
if(Arrays.equals(nodeDFS.getState(), finalState)) {
foundFinalState = true;
foundNode = Optional.of(nodeDFS);
} else {
int[] nodeState = nodeDFS.getState();
this.processChild(new int[]{nodeState[1],nodeState[0],nodeState[2],nodeState[3]}, nodeDFS);
this.processChild(new int[]{nodeState[0],nodeState[2],nodeState[1],nodeState[3]}, nodeDFS);
this.processChild(new int[]{nodeState[0],nodeState[1],nodeState[3],nodeState[2]}, nodeDFS);
}
}
}esta parte nos daría varios errores. Lo que necesitemos, lo pasamos por parámetro y el resultado, si lo encontramos, es devolverlo con un return dentro del «if» y sino lo encontramos llamamos al mismo método.
El resultado de este proceso sería:
Optional<NodeDFS> search(final int[] initialState, final int[] finalState) {
if(isNull(initialState)) {
throw new NullPointerException("initialState shouldn't be null");
}
if(isNull(finalState)) {
throw new NullPointerException("finalState shouldn't be null");
}
nodeDFS.add(NodeDFS.of(initialState));
return iterativeSearch(finalState);
}
private Optional<NodeDFS> iterativeSearch(final int[] finalState) {
final NodeDFS nodeDFS = this.nodeDFS.pop();
visited.add(nodeDFS);
if(Arrays.equals(nodeDFS.getState(), finalState)) {
return Optional.of(nodeDFS);
} else {
int[] nodeState = nodeDFS.getState();
this.processChild(new int[]{nodeState[1],nodeState[0],nodeState[2],nodeState[3]}, nodeDFS);
this.processChild(new int[]{nodeState[0],nodeState[2],nodeState[1],nodeState[3]}, nodeDFS);
this.processChild(new int[]{nodeState[0],nodeState[1],nodeState[3],nodeState[2]}, nodeDFS);
}
return iterativeSearch(finalState);
}Si queréis el código completo, seguir este enlace github
LIMITANDO LA PROFUNDIDAD
Qué problema tendríamos aquí ?. Que las búsquedas con tendencia al infinito, serían un problema a tener en cuenta, ya que esta búsqueda nunca terminaría. Por este motivo, limitaremos la profundidad de nuestra búsqueda.
Para limitar, este tipo de búsqueda, añadiremos una variable extra, para controlar en el nivel que estamos.
Si queremos evitar tener dos variables: nivel en el que estamos y limite, usaremos una sola, donde iremos restando uno a medida que vamos profundizando y devolveremos que no hemos encontrado nada, si llegamos a cero
private Optional<NodeDFS> iterativeSearch(final int[] finalState, int depthBoundary) {
if(depthBoundary > 0){
final NodeDFS nodeDFS = this.nodeDFS.pop();
visited.add(nodeDFS);
if (Arrays.equals(nodeDFS.getState(), finalState)) {
return Optional.of(nodeDFS);
} else {
int[] nodeState = nodeDFS.getState();
this.processChild(new int[]{nodeState[1], nodeState[0], nodeState[2], nodeState[3]}, nodeDFS);
this.processChild(new int[]{nodeState[0], nodeState[2], nodeState[1], nodeState[3]}, nodeDFS);
this.processChild(new int[]{nodeState[0], nodeState[1], nodeState[3], nodeState[2]}, nodeDFS);
}
return iterativeSearch(finalState, --depthBoundary);
}
return Optional.empty();
}Bastante sencillo no ?. Es muy muy interesante, que miréis primero el algoritmo, base y veáis la evolución desde la DFS, sin ningún tipo de limite de computación y este resultado.
Obviamente, pueden haber alternativas, pero si tenéis controlada, la base siempre podéis aplicar pequeños cambios para adaptarlo a vuestras necesidades
IMPLEMENTACIÓN
