follow braegel at http://twitter.com
www.flickr.com
Fotos von Bernd Brägelmann Mehr Fotos von Bernd Brägelmann

  • Blogroll

  • Scripte

  • Mehr von mir

  • Extern

    • June 5, 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

    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;
    }

    }

    Topics: Allgemein |

    Comments