[java] Intelligenza artificiale e metodi Blind Search

[franksisca]

allora, ero senza fare neinte (magari) e mi sono messo ad implementare i metodi di ricerca denominati Blind Search, ovvero il Depth-first (http://en.wikipedia.org/wiki/Depth-first_search) e il Breadth-first (http://it.wikipedia.org/wiki/Breadth-first_search).

ecco le mie implementazioni (magari servono a qualcuno):


classe astratta che implementa ricorsivamente la ricerca "bruta"

package blindSearch;

import java.util.List;

public abstract class AlgoritmoBlind {

public Nodo blindSearch(List<Nodo> listaNodi) {
Nodo attuale;
if (listaNodi.isEmpty())
return null;
else {
attuale = scegli(listaNodi);
if (isGoal(attuale))
return attuale;
aggiungi(listaNodi, attuale);
listaNodi.remove(attuale);
return blindSearch(listaNodi);
}
}


protected abstract void aggiungi(List<Nodo> listaNodi, Nodo attuale);

protected abstract Nodo scegli(List<Nodo> listaNodi);

protected abstract boolean isGoal(Nodo attuale);

}






classe che implementa i metodi per la ricerca "depth"
package blindSearch;

import java.util.List;

public class DepthFirst extends AlgoritmoBlind {

@Override
protected boolean isGoal(Nodo attuale) {
return attuale.isGoal();
}

@Override
protected Nodo scegli(List<Nodo> listaNodi) {
return listaNodi.get(0);
}

@Override
protected void aggiungi(List<Nodo> listaNodi, Nodo attuale) {
if(attuale.isLeaf())return;
List <Nodo> listaFigli= attuale.getSons();
listaNodi.addAll(0,listaFigli);

}

}





classe per la ricerca breadth
package blindSearch;

import java.util.List;

public class BreadthFirst extends AlgoritmoBlind {

@Override
protected boolean isGoal(Nodo attuale) {
return attuale.isGoal();
}

@Override
protected Nodo scegli(List<Nodo> listaNodi) {
return listaNodi.get(0);
}

@Override
protected void aggiungi(List<Nodo> listaNodi, Nodo attuale) {
if(attuale.isLeaf())return;
List <Nodo> listaFigli= attuale.getSons();
listaNodi.addAll(listaFigli);


}

}






per testarli ho usato questa classe:
package blindSearch;
/**
* 0
* / \
* / \
* 1 2
* / \ / \
* 3 4 5 6
* /\ /\ /\ /\
* 7 8 9 10 11 12 13 14
*
* UNICO GOAL 14
*/
import java.util.LinkedList;
import java.util.List;

public class TestAlgoritmiDepthFirst {

public static void main (String arg[]){
List <Nodo> nodi=new LinkedList<Nodo>();
List <Nodo> figli_1=new LinkedList<Nodo>();
List <Nodo> figli_2=new LinkedList<Nodo>();
List <Nodo> figli_3=new LinkedList<Nodo>();
List <Nodo> figli_4=new LinkedList<Nodo>();
List <Nodo> figli_5=new LinkedList<Nodo>();
List <Nodo> figli_6=new LinkedList<Nodo>();
List <Nodo> figli_7=new LinkedList<Nodo>();

nodi.add(0, new Nodo(figli_1, null));
nodi.add(1, new Nodo(figli_2, nodi.get(0)));
nodi.add(2, new Nodo(figli_3, nodi.get(0)));
nodi.add(3, new Nodo(figli_4, nodi.get(1)));
nodi.add(4, new Nodo(figli_5, nodi.get(1)));
nodi.add(5, new Nodo(figli_6, nodi.get(2)));
nodi.add(6, new Nodo(figli_7, nodi.get(2)));
nodi.add(7, new Nodo(null, nodi.get(3)));
nodi.add(8, new Nodo(null, nodi.get(3)));
nodi.add(9, new Nodo(null, nodi.get(4)));
nodi.add(10, new Nodo(null, nodi.get(4)));
nodi.add(11, new Nodo(null, nodi.get(5)));
nodi.add(12, new Nodo(null, nodi.get(5)));
nodi.add(13, new Nodo(null, nodi.get(6)));
nodi.add(14, new Nodo(null, nodi.get(6)));

int cnt=0;
for(Nodo n:nodi){
n.setValue(""+cnt);
cnt++;
}

nodi.get(14).setGoal(true);

nodi.get(7).setLeaf(true);
nodi.get(8).setLeaf(true);
nodi.get(9).setLeaf(true);
nodi.get(10).setLeaf(true);
nodi.get(11).setLeaf(true);
nodi.get(12).setLeaf(true);
nodi.get(13).setLeaf(true);
nodi.get(14).setLeaf(true);

figli_1.add(nodi.get(1));
figli_1.add(nodi.get(2));
figli_2.add(nodi.get(3));
figli_2.add(nodi.get(4));
figli_3.add(nodi.get(5));
figli_3.add(nodi.get(6));
figli_4.add(nodi.get(7));
figli_4.add(nodi.get(8));
figli_5.add(nodi.get(9));
figli_5.add(nodi.get(10));
figli_6.add(nodi.get(11));
figli_6.add(nodi.get(12));
figli_7.add(nodi.get(13));
figli_7.add(nodi.get(14));

List <Nodo>iniziale=new LinkedList<Nodo>();
iniziale.add(nodi.get(0));
AlgoritmoBlind alg=new DepthFirst();
double startTime=System.currentTimeMillis();
Nodo goal=alg.blindSearch(iniziale);
double finishTime=System.currentTimeMillis();
System.out.print("Tempo di calcolo del Depth First=: " );
System.out.println(finishTime-startTime + " millisecondi");
System.out.println("Il goal è:"+goal.getValue());
System.out.println("il path del GOAL è:");
String path=goal.getValue();
Nodo parent=goal.getParentNode();
while(parent!=null){
path+="<---"+parent.getValue();
parent=parent.getParentNode();
}
System.out.println(path);


}
}





come potete vedere ho costruito l'albero manualmente, e data la dimensione molto piccola, i risultati "auspicabili" non sono analizzabili.

volevo sapere se avevate qualche classe che scrivesse un albero intero e simmetrico, dando possibilità di definire in automatico foglie e goal.

la mia attuale classse nodo è questa:

package blindSearch;

import java.util.List;

public class Nodo {

private final List <Nodo> sonsNode;
private String value;
private boolean isGoal=false;
private Nodo parentNode;
private boolean isLeaf=false;

public Nodo (List <Nodo> sons, Nodo parent){
this.sonsNode=sons;
this.parentNode=parent;
}

public List<Nodo> getSons() {
return this.sonsNode;
}

public boolean isGoal() {
return isGoal;
}

public void setGoal(boolean isGoal) {
this.isGoal = isGoal;
}

public String getValue() {
return value;
}

public void setValue(String value) {
this.value = value;
}

public Nodo getParentNode() {
return parentNode;
}

public void setParentNode(Nodo parentNode) {
this.parentNode = parentNode;
}

public boolean isLeaf() {
return isLeaf;
}

public void setLeaf(boolean isLeaf) {
this.isLeaf = isLeaf;
}


}

[franksisca]

ovviamente lo potrei fare in auitomatico, ma al momento non ci sono con la testa, sto implementando l'Iterative Deepening, e ci sto ragionando (non è difficile, ma comunque sto cercando di "aggiustarlo")

se mi aiutate (nella costruzione dell'albero di ricerca) ve ne sarei grato ;)