Auschnitt aus dem Sourcecode des Java-Applets



/*
 * Title: "Suche" - Applet zum Experimentieren mit gängigen Suchalgorithmen (Ausschnitte)
 * Date: Mai 2001
 * Author: Martin Gutschke
 * Copyright (c): Martin Gutschke
 *      Info: http://www.4est.de
 * Weitere Informationen finden sich auf http://www.gutschke.de
 */

 public void expand(Knoten k,Queue o,Queue c)
 {
  if((checkbox1.getState()==false)||((k.tiefe+1)<=limit))
  {
   for(int r=0;r<k.size;r++)
   {
    if(k.kanten[r]!=null)
    {
     if((k.kanten[r].start.name!=k.comming)&&(k.kanten[r].ziel.name!=k.comming))
     {
      if((k.kanten[r].start.name)!=k.name)
      {
       Knoten k2=new Knoten();
       copyKnoten(k2,k.kanten[r].start);
       k2.tiefe=k.tiefe+1;                                           //neuer Knoten ist eine Suchbaumebene tiefer
       k2.comming=k.name;                                       //Name des Elternknotens merken
       k2.kosten=k.kosten+k.kanten[r].len;                //Kosten mitrechnen/erhöhen
       k2.way=k.way;
       if(k.way.equals("")==false)
       {
        k2.way=k2.way+" ";
       }
       k2.way=k2.way+k.name;
       if(choice1.getSelectedItem().equals("Breitensuche"))              //Optimierung für die Breiten- und Tiefensuche
       {
        o.hintenDran(k2);
       }
       else
       {
        o.vorneDran(k2);
       }
       graph.edgecolor(k.name,k2.name);                                           //Einfärbung des Graphen
      }
      if((k.kanten[r].ziel.name)!=k.name)
      {
       Knoten k2=new Knoten();
       copyKnoten(k2,k.kanten[r].ziel);
       k2.tiefe=k.tiefe+1;
       k2.comming=k.name;
       k2.kosten=k.kosten+k.kanten[r].len;
       k2.way=k.way;
       if(k.way.equals("")==false)
       {
        k2.way=k2.way+" ";
       }
       k2.way=k2.way+k.name;
       if(choice1.getSelectedItem().equals("Breitensuche"))
       {
        o.hintenDran(k2);
       }
       else
       {
        o.vorneDran(k2);
       }
       graph.edgecolor(k.name,k2.name);
      }
     }
    }
   }
  }
  c.hintenDran(k);
 }

 double hfunction(Object o1,Object o2)
 {
  Knoten k;
  Knoten z;
  int m;

  k=(Knoten)(o1);
  z=(Knoten)(o2);
  m=choice2.getSelectedIndex();

//Waagerechte Distanz

  if(m==0)
  {
   return(Math.abs(k.x-z.x));
  }

//Senkrechte Distanz

  if(m==1)
  {
   return(Math.abs(k.y-z.y));
  }

//Summe

  if(m==2)
  {
   return(Math.abs(k.x-z.x)+Math.abs(k.y-z.y));
  }

//Produkt

  if(m==3)
  {
   return(Math.abs(k.x-z.x)*Math.abs(k.y-z.y));
  }

//Kürzeste Entfernung

  if(m==4)
  {
   return(Math.sqrt((k.x-z.x)*(k.x-z.x)+(k.y-z.y)*(k.y-z.y)));                           //Rückgabe der voreingestellten Heuristik
  }

//Beste Richtung

  if(m==5)
  {
   Knoten l=(Knoten)(graph.getKnoten(k.comming));
   int w,n;
   double alfa;
   double beta;

   w=z.y-k.y;
   n=z.x-k.x;
   if(n!=0){
    alfa=Math.atan(w/n);
   }
   else
   {
    alfa=Math.PI/2*signum(w);
   }
   w=z.y-l.y;
   n=z.x-l.x;
   if(n!=0){
    beta=Math.atan(w/n);
   }
   else
   {
    beta=Math.PI/2*signum(w);
   }
   return(Math.abs(alfa-beta));
  }
  return 0;
 }

 double function(Object o)
 {
  Knoten k;
  double f;

  k=(Knoten)(o);
  f=Integer.parseInt(t0.getText())*k.tiefe
   +Integer.parseInt(t1.getText())*k.kosten
   +Integer.parseInt(t2.getText())*hfunction(k,zielknoten);
  return f;
 }

 public void sortlist(Queue o)
 {
  boolean tauschflag;
  Object temp1;
  Object temp2;

  if(choice1.getSelectedItem().equals("Tiefensuche"))
   return;
  if(choice1.getSelectedItem().equals("Begrenzte Tiefensuche"))
   return;
  if(choice1.getSelectedItem().equals("Iterative Tiefensuche"))
   return;
  if(choice1.getSelectedItem().equals("Breitensuche"))
   return;
  tauschflag=true;
  while(tauschflag==true)
  {
   tauschflag=false;
   for(int r=0;r<o.anz-1;r++)
   {
    if(function(o.liesMal(r))>function(o.liesMal(r+1)))                     //Vergleich für das Sortieren der Liste
    {
     temp1=o.liesMal(r);
     temp2=o.liesMal(r+1);
     o.schreibMal(r,temp2);
     o.schreibMal(r+1,temp1);
     tauschflag=true;
    }
   }
  }
 }

 public void search(String start,String ziel)
 {
  if(searchinitedflag==false){
   if(checkbox2.getState()==false)
   {
    laufzeit=0;
   }
   if(limittakenflag==false)
   {
    laufzeit=0;
    limit=Integer.parseInt(t3.getText());
    limittakenflag=true;
   }
   openlist.clear();
   initGraph();
   baum.clear();
   baumknotennr=0;
   baumfenster.paint(bf);
   kk=(Knoten)(graph.getKnoten(start));
   zielknoten=(Knoten)(graph.getKnoten(ziel));
   kk.tiefe=0;
   kk.kosten=0;
   if((checkbox1.getState()==false)||(Integer.parseInt(t3.getText())>0))
   {
    openlist.vorneDran(kk);
   }
   found=false;
   searchinitedflag=true;
  }
  if((openlist.anz>0)&&(found==false))
  {
   laufzeit++;                                                              //Mitzählen der besuchten Knoten (Laufzeitäquivalent)
   kk=(Knoten)(openlist.vorneWeg());                       //einen Knoten von der Queue holen...
   repaint();
   kk.color=new Color(255,0,0);
   kk.newcoloredflag=true;
   graph.nodecolor(kk.name,new Color(255,0,0));     //...und einfärben
   if(kk.name.equals(ziel))                                          //Zieltestfunktion
   {
    found=true;
    limittakenflag=false;
    openlist.clear();
   }
   expand(kk,openlist,closelist);                                  //Aufruf der Methode zum expandieren eines Knotens
   addBaum(kk);                                                           //Knoten dem Suchbaum hinzufügen
   bf.setColor(Color.white);
   bf.fillRect(0,0,1024,1024);
   baum.paint(bf);
   baumfenster.repaint();
   sortlist(openlist);                                                      //algorithmusabhängiges sortieren der Queue
   openlistfenster.repaint();
   graphenfenster.repaint();
  }
  else
  {
   searchinitedflag=false;
   if((checkbox1.getState()==true)&&(checkbox2.getState()==true)&&(found==false))
   {
    limit++;
   }
   else
   {
    traceflag=false;
    runflag=false;
    if(found==false)
    {
     ergebnisfenster.setVisible(true);
     ergebnisfenster.z1="Die Route von "+start+" nach "+ziel+" wurde nicht gefunden.";
     ergebnisfenster.z2="";
     ergebnisfenster.z3="Laufzeit: "+z.valueOf(laufzeit);
     ergebnisfenster.repaint();
    }
    if(found==true)
    {
     graphenfenster.repaint();
     ergebnisfenster.setVisible(true);
     ergebnisfenster.z1="Die gefundene Route von "+start+" nach "+ziel+" lautet:";
     ergebnisfenster.z2=kk.way+" "+ziel+".";
     ergebnisfenster.z3="Laufzeit: "+z.valueOf(laufzeit);
     ergebnisfenster.repaint();
    }
   }
  }
 }

Download (komplett)

Download (packages)

Start