Zelle: Grenzen im Zustandsraum, Nachbarschaftsbeziehungen, Jwc
Liste: Schablonen-Klasse für Listen beliebigen Typs
Greedy: Schnittstelle zur Hardware (SimRobot), Greedy-Controller
SimRobot: Ansteuerung von SimRobot (Hardware)
Folie: Implementierung
Zustandsraum als Binärbaum
schnelles Finden von Zellen
Zellteilung ohne großen Aufwand
"Vergessen" möglich
Algorithmus unabhängig von der Dimensionstiefe des Zustandsraumes
Berechnung der Jwc's mittels dynamischer Programmierung
Aufwand quadratisch in der Zellenzahl
Zur Zeit omnidirektionale Tonne
Wissensbasis global gespeichert
Folie: Lesbarer Code:
for(;;) { REPEAT FOREVER
berechneAlleJwc(*this,part); Compute Jwc() for
each cell
Zelle& i=lieferZelleAusZustand(*this,s); Let i:= the cell
containing the
current state s.
if(zielErreicht(i)) return true; If i=GOAL then exit
(success)
if(i.entfernung==UNENDLICH) return false; If Jwc()=infty then
exit (failure)
...
for(ListenElement<Zelle*>* z=qq.gibKopf(); Construct a new set
z;z=z->gibNaechstesElement()) of cells from Q"
if(!zielErreicht(*(z->eintrag))) { produced by splitting
z->eintrag->teileZelle(); each cell.
r.fuegeEin(ZelleZgr(z->eintrag->links)); Call this new set R.
r.fuegeEin(ZelleZgr(z->eintrag->rechts));
part=part+r-qq; P:=P+R-Q"
wissensbasis.loesche(inqq,&qq); delete those members
of database D that
contain a member of Q"