Best Practice Programmierstil Graphen-A*-Suche

[minzee]

Hi 🙂

Ich habe diesmal eine wirklich echt schwierige Frage. Es geht darum, in welchem Stil man am besten eine Graphen-A*-Suche programmiert.

Es geht hierum:

http://wwwiti.cs.uni-magdeburg.de/iti_db/algoj/code/algoj/kap16/Graph.java ... definiert eine Graph-Klasse mit einer Edge- und Node-Klasse
http://wwwiti.cs.uni-magdeburg.de/iti_db/algoj/code/algoj/kap16/AStarSearch.java ... definiert die Klasse für die A*-Suche

Irgendwie finde ich das gut, dass man der A*-Klasse einen kompletten Graphen übergibt. Damit kann man den Graphen für unterschiedlichste Zwecke verwenden.

Allerdings sind meiner Meinung nach damit folgende Unannehmlichkeiten verbunden:

- addNode muss ein node-Objekt zurückgeben
- die Node-Klasse benötigt eine Methode setCost zur Definition der h-Kosten
- die Graph-Klasse muss eine getNode-Methode zur Verfügung stellen

setCost benötigt man - soviel ich weiß - jedoch ausschließlich nur für A*-Suchen.

Eine andere Möglichkeit wäre, keine eigene AStarSearch-Klasse zu programmieren, sondern alles in der Graph-Klasse unterzubringen. Damit ergibt sich:

- addNode muss kein node-Objekt zurückgaben
- die Node-Klasse benötigt keine Methode setCost, die h-Kosten werden gleich bei addNode mit übergeben
- in der Graph-Klasse muss es keine getNode-Methode geben

Der Nachteil dieser Variante ist, dass man Graph-Instanzen nicht irgendwelchen Such-Klassen übergeben kann. Die Graph-Klasse bietet nur jene Möglichkeiten, die man in der Klasse programmiert hat.

In welchem Stil würdet ihr so etwas programmieren?

 

[arilou]

Ohne das jetzt im Detail geprüft zu haben, hört sich das nach einer klassischen Spezialisierungs-Situarion an.
D.h. du hast eine Klasse A, die "übliche Grundfunktionen" besitzt, und eine andere Klasse B, die zusätzlich weitere Methoden (oder mit zusätzlichen Parametern) besitzen soll, oder ein spezielles Verhalten zeigen soll.

Dann erbt Klasse B von Klasse A.
Die Grundfunktionen bleiben, les' mal nach, was "Polymorphie" bzgl. OOP bedeutet.

 

[DarXun]

Ohne das jetzt im Detail geprüft zu haben, hört sich das nach einer klassischen Spezialisierungs-Situarion an.
D.h. du hast eine Klasse A, die "übliche Grundfunktionen" besitzt, und eine andere Klasse B, die zusätzlich weitere Methoden (oder mit zusätzlichen Parametern) besitzen soll, oder ein spezielles Verhalten zeigen soll.

Dann erbt Klasse B von Klasse A.
Die Grundfunktionen bleiben, les' mal nach, was "Polymorphie" bzgl. OOP bedeutet.

Ich bin ja wirklich nur selten ein *****, aber - Bist du zufällig im falschen Thread gelandet?
Ich verstehe nicht, was das mit dem Thema vom TE zu tun hat??

Aber um auch was Konstruktives zu leisten:

addNode muss ein Node-Objekt zurückgeben
Inwiefern siehst du das als Unannehmlichkeit? Ich sehe da kein Problem, du musst das zurückgelieferte Objekt ja nicht unbedingt beachten, es behindert dich nicht.

die Node-Klasse benötigt eine Methode setCost zur Definition der h-Kosten
Alternativ könntest du die Kosten natürlich auch direkt in der addNode-Methode übergeben und im Graphen noch eine Node-zu-Kosten -Map aufbauen.
Dabei kann ich aber auch noch nicht ganz nachvollziehen was dich daran stört, dass die Kosten direkt in der Node mit abgespeichert werden... Du konzipierst doch in dem Moment eine A*-Suche, klar hat eine Node da auch Kosten.

Aber mal zum Vergleich zu deiner alternativen Vorgehensweise - Davon halte ich ehrlich gesagt wenig.
Es gibt in der Informatik den Begriff der Kohäsion. Ich zitier mal Wikipedia: "In einem System mit starker Kohäsion ist jede Programmeinheit (eine Methode, eine Klasse oder ein Modul) verantwortlich für genau eine wohldefinierte Aufgabe oder Einheit." (Koh)
Die Graph-Klasse ist mMn nicht für die Suche direkt verantwortlich. Deswegen würde ich die Suche definitiv auslagern. Die Graph-Klasse hat damit auch eine höhere Wiederverwendbarkeit.

LG

DarXun

 

[arilou]

Ich bin ja wirklich nur selten ein *****, aber - Bist du zufällig im falschen Thread gelandet?
Ich verstehe nicht, was das mit dem Thema vom TE zu tun hat??

Eine Klasse "Graph" habe Methoden, und minzee wollte wissen, "wie mach ich das, wenn eine zusätzliche Funktionalität nur in bestimmten Fällen nötig ist?"
Meine Antwort: in einer abgeleiteten Klasse "SpeziellerGraph".

 

[DarXun]

Aaah, okay.
Das ergibt natürlich einen Sinn ^^
Mi scusi.

 

[minzee]

addNode muss ein Node-Objekt zurückgeben
Inwiefern siehst du das als Unannehmlichkeit?

Ich glaube, mir könnte das ganz gut gefallen, wenn das Hauptprogramm überhaupt nichts davon mitbekommt, welche Node-Instanzen im Graphen erzeugt werden. Eigentlich könnte man die Nodes auch im Hauptprogramm erzeugen und dann dem Graphen übergeben. Aber so etwas scheint man generell nicht gerne machen zu wollen. Darum sehe ich das als Unannehmlichkeit an.

Dabei kann ich aber auch noch nicht ganz nachvollziehen was dich daran stört, dass die Kosten direkt in der Node mit abgespeichert werden

Mich stört das, weil ich die Node-Klasse nicht ständig verändern möchte. Jeder Graph-Algorithmus benötigt irgendwelche anderen Hilfmittel, die man den Knoten zuordnen könnte. Doch mit jedem neuen Algorithmus müsste man eine bereits bestehende und getestete Klasse (die Node-Klasse) umprogrammieren. Auch wird die Node-Klasse mit jedem neuen Graphen-Algorithmus länger. Außerdem hat der Algorithmus nur die Aufgabe, den besten Weg zu finden. Letztendlich interessieren dann niemand mehr die h-Kosten. Sie sind nur ein Hilfsmittel. Und die würd ich eigentlich nicht in Objekt-Eigenschaften verewigen.

Die Graph-Klasse ist mMn nicht für die Suche direkt verantwortlich

Also auf jeden Fall muss es in dieser Klasse eine Methode geben, die die Suche startet. Dann könnte man rein theoretisch unterschiedlich vorgehen. Aber die einfachste Variante ist, wenn sich der Graph darum kümmert. Man könnte diese Suche dann aber auch in die Knoten verlagern. Das wird dann aber schwieriger zu programmieren und schwieriger das zu verstehen und zu testen.

EDIT: Ups, hatte deine Antwort falsch verstanden. Bei dir ging es nicht darum, ob die Graphen-Klasse oder die Knoten-Klasse dafür verantwortlich ist, sondern ob die Graphen-Klasse oder eine spezielle Such-Klasse, der ein Graph übergeben wird. Tja, das kann ich nicht beurteilen. Ich weiß nicht, wie das in anderen ähnlichen Fällen gehandhabt wird. Da bräucht ich irgendwie eine best-practice-Anleitung.

Eine Klasse "Graph" habe Methoden, und minzee wollte wissen, "wie mach ich das, wenn eine zusätzliche Funktionalität nur in bestimmten Fällen nötig ist?"
Meine Antwort: in einer abgeleiteten Klasse "SpeziellerGraph".

Naja, die Graphen-Klassen wären dann doch ziemlich unterschiedlich. Vergleichen wir einfach mal den Dijkstra- mit dem A*-Algorithmus:

- Dijkstra braucht nicht zu jedem Knoten Kostenangaben, A* schon. D. h. die addNode-Methode schaut schon mal anders aus, sofern man die H-Kosten gleich bei addNode mit angibt.

- Bei Dijkstra muss man einen Startknoten angeben, um die Suche zu initialisieren, bei A* jedoch Start- und Zielknoten. D. h. die getShortestPath-Methode hat unterschiedliche Anzahl an Parametern, sofern man nicht extra setter-Methoden definiert.

- Außerdem geben die getShortestPath-Methoden unterschiedliche Daten zurück. Bei Dijkstra kann man ein eigenes Objekt zurückgeben, worüber man dann die unterschiedlichsten kürzesten Pfade bei den unterschiedlichsten Zielknoten ermitteln kann. Bei A* hat man diese Möglichkeit nicht, da ist alles von Beginn an auf einen bestimmten Zielknoten ausgelegt (aufgrund der H-Kosten, die man schon bei den Knoten definiert). Die getShortestPath-Methode liefert also das Endergebnis und damit hat es sich.

Also wenn man alleine diese beiden Algorithmen anschaut, tun sích schon viele Unterschiede auf. Natürlich können alle das gleiche Interface implementieren. Auch könnten sie von einer gemeinsamen abstrakten Klasse erben, aber die wäre dann vielleicht ziemlich leer.