Flickr

www.flickr.com

Samstag, 5. Juni 2010

Weinkrügeproblem

Hier meine Java Lösung für das Weinkrügeproblem aus dem Buch Wissensverarbeitung - Eine Einführung in die Künstliche Intelligenz für Informatiker und Ingenieure - I. Boersch, J. Heinsohn, R. Socher - 2. Auflage.

Die Frage ist, wie man den Wein aus 3 Weinkrügen

  • 9 Liter (voll)

  • 7 Liter (leer)

  • 4 Liter (leer)



so verteilt, dass sich im 9 Liter Krug 6 Liter und im 4 Liter Krug 3 Liter Wein befinden?

Ist mein erster Java Versuch und ich bin möchtig stolz darauf. Bin für konstruktive Kritik offen!


WeinkruegeproblemV2.java:


import java.util.*;

public class WeinkruegeproblemV2 {

public static int [] init(){
int [] startstatus = {9,0,0,};
// int [] startstatus = {6,0,3,};

return startstatus;
}

public static boolean zielerreicht(Knoten k){
int [] zielstatus = {6,0,3,};
return Arrays.equals(k.getStatus(), zielstatus);
}

public static int [] umschuetten (int i, int j, Knoten k){
int umfuellmenge = 0;
int [] status = k.getStatus().clone();
int [] maxinhalt = {9,7,4,};
umfuellmenge = Math.min(k.getStatus()[i],maxinhalt[j]-k.getStatus()[j]);
status[i]=k.getStatus()[i] - umfuellmenge;
status[j]=k.getStatus()[j] + umfuellmenge;
return status;
}

public static boolean doublette(Knoten k){
int i;
// System.out.println("Checke Pfad mit "+k.getPfad().size()+ " Knoten auf Doublette.");
for (i=0;i if (Arrays.equals(k.getStatus(),k.getPfad().get(i).getStatus())){
// System.out.println("Doublette: "+i+Arrays.toString(k.getStatus())+" "+Arrays.toString(k.getPfad().get(i).getStatus()));
return true;
}
// System.out.println("Keine Doublette: "+i+Arrays.toString(k.getStatus())+" "+Arrays.toString(k.getPfad().get(i).getStatus()));
}
return false;
}

public static ArrayList expand(Knoten k){
ArrayList kinder = new ArrayList();
int i,j;
Knoten kind = new Knoten();


for (i=0;i<=2;i++){
for (j=0;j<=2;j++){
if (j!=i){
kind.setStatus(umschuetten(i,j,k));
kind.setPfad((ArrayList)k.getPfad());
// zeigeKnotenliste(k.getPfad());
// System.out.println(Arrays.toString(kind.getStatus()));

if (!Arrays.equals(kind.getStatus(),k.getStatus())){

if (!doublette(kind)){
// System.out.println("Neues Kind: "+Arrays.toString(kind.getStatus()));
// kind.addPfad(kind);
kinder.add(new Knoten( kind.getStatus(), kind.getPfad() ));
}
}
}
}

}

System.out.println("Kinder:");
zeigeKnotenliste(kinder);
return kinder;
}

public static void zeigeKnotenliste(ArrayList liste){
int i;

for (i=0;i System.out.println(i+" "+Arrays.toString(liste.get(i).getStatus()));
// System.out.println("Path:");
// zeigeKnotenliste(liste.get(i).getPfad());
// System.out.println();
}
System.out.println("==> "+ liste.size() + " Elemente");

}

public static void main(String[] args){
int dummy;
ArrayList agenda = new ArrayList();

Knoten z = new Knoten();
// zeigeKnotenliste(z.getPfad());
z.setStatus(init());
// zeigeKnotenliste(z.getPfad());

agenda.add(z);

while(!zielerreicht(z)){
// for (dummy=0;dummy<2;dummy++){
z.addPfad(z);
System.out.println("\nExpandiere "+Arrays.toString(z.getStatus()));
// System.out.println("Pfad :");
// zeigeKnotenliste(z.getPfad());
agenda.addAll(expand(z)); // Breitensuche
// System.out.println("Agenda nach Zufügung der Kinder:");
// zeigeKnotenliste(agenda);
agenda.remove(0);
System.out.println("Agenda:");
zeigeKnotenliste(agenda);
z = agenda.get(0);
}

// DEBUGGING
// System.out.println(Arrays.toString( z.getStatus() ));
// z.setStatus(init());
// System.out.println(Arrays.toString( z.getStatus() ));
// Knoten z1 = new Knoten();
// z1.setStatus(umschuetten(0,1,z));
// z1.addPfad(z);
// System.out.println(Arrays.toString( z.getStatus() ));
// System.out.println(Arrays.toString( z1.getStatus() ));
// System.out.println(zielerreicht(z));

System.out.println("\nLösung gefunden");
zeigeKnotenliste(z.getPfad());
}
}






Knoten.java:


import java.util.*;

public class Knoten {
private int[] status = {-1,-1,-1, };
private ArrayList pfad = new ArrayList();

Knoten(){ // Ueberladen
}

Knoten(int [] ueb_status){ // Ueberladen
status = ueb_status.clone();
}


Knoten(int [] ueb_status, ArrayList ueb_pfad){ // Ueberladen
status = ueb_status.clone();
pfad = (ArrayList)ueb_pfad.clone();
}

public void setStatus(int[] status){
this.status = status.clone();
}

public void setPfad(ArrayList ueb_pfad){
pfad=(ArrayList)ueb_pfad.clone();
}

public void addPfad(Knoten ueb_pfad){
pfad.add(ueb_pfad);
}

public int[] getStatus(){
return this.status;
}

public ArrayList getPfad(){
return this.pfad;
}


}


Keine Kommentare:

Kommentar veröffentlichen