Strategien zur Suche
Der Zweck dieses Bespielcodes ist die Demonstration verschiedener Suchstrategien im Kontext von Problemlösungen. Speziell sind dies die folgenden:
- Breadth First
- Depth First
- Iterative Deepening
- Best First
Mein Beispielcode
Ich habe das Applet als Commandozeilenprogram umgeschrieben.
Erfahrungen mit Ruby
Generell ging die Konvertierung sehr schnell. Das Klassenmodell habe ich direkt übertragen können. An vielen Stellen ist der Ruby Code kompakter und eleganter. Vermisst habe ich eine Methode, um in ein Array an einer bestimmten Stelle ein Element einfügen zu können (Ab Ruby 1.8 funktioniert array.insert(pos, elems), aber meine Dokumentation bezog sich noch 1.6). Beim Versuch diese selbst zu schreiben fehlte mir eine das Analogon einer FOR Schleife mit negativer Schrittweise. (reverse_each). Ferner bin ich über die Übergabe per Referenz gestolpert. Die bedeutet, dass man zwar die übergebenen Objekte in einer Methode verändern kann. Wenn man allerdings dem Parameter einen neuen Wert zuweist, so bleibt in der aufrufenden Methode das Objekt unverändert.
Ruby inspirierte mich zu folgenden Erweiterungen:
- Ein uns Ausgabe des Graphen mit XML
- Iterator für die Suchstrategien: für jeden besuchten Knoten kann von aussen vorgegebenes Codestück aufgerufen werden.
Erfahrungen mit dem Beispiel
Das Beispielproblem greift in einigen Bereichen zu kurz. So ist die Benennung des Suchziels als "state" hier verwirrend, es ist auch nicht einsichtig wofür dieser gebraucht wird. Andererseits wurde man sich bei einer Routensuche natürlich wünschen, den Weg zu erfahren, und nicht nur das man das Ziel erreichen kann. Ein schöneres Beispielproblem findet sich in Ivan Bratko's Prolog Buch: Ein Turm von Bauklötzen soll umgeschichtet werden, wobei man jeweils nur einen auf einmal bewegen darf. Hier werden die jeweiligen Knoten erst zu Laufzeit generiert, und das State-Feld bekommt einen Sinn.
Die Demonstration des Best-First Algorithmus mittels festen Kosten ist unbefriedigend: Man ist auf einen Startknoten festgelegt.
Der Code erscheint an einige Stellen mit heisser Nadel gestrickt: So gibt es vier verschiedene Methoden "addLinks()",
ja nachdem ob man 1,2,3 oder vier Links zu einem Node hinzufügen will.
Für de Konstruktion des Beispielgraphen werden zwei und eine halbe kostbare
Buchseiten verbraucht.
Das Einlesen aus einer Datei hätte selbst in Java weniger Platz gekostet und wäre weniger langweilig gewesen.
Mitten in dem Suchalgorithmus finden sich Aufrufe der AWT-Library, um die Statusnachrichten senden zu können.
Das Beispielprogramm sollte aber gerade den Suchalgorithmus vorstellen. Artifakte der Benutzerschnittstelle
sollte man dabei vermeiden. In Ruby kann man dieses Problem mit Iteratoren geschickt umgehen.
Aber auch in Java wäre eine Trennung mittels Observer möglich gewesen.
Und zu guter Letzt verwendet auch dieses Buch in seinen Beispielcode keine Syntaxhervorhebung. Leider ist dies aber selbst bei Büchern aus dem Jahr 2003 immer noch nicht der Fall.
Die erste Version der Ruby Umsetzung finden sie hier:
Quelle: Joseph P. Bigus, Jennifer Bigus: "Constructing Intelligent Agents Using Java", 1998, Wiley Computer Publishing, Beschreibung bei Wiley
home - contact - dev-zone
Copyright © 2003,2004 by Karsten Meier. All Rights reserved.