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