[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 e il Breadth-first.

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