Best Practice Programmierstil Graphen-A*-Suche

minzee

Bekanntes Mitglied
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

Bekanntes Mitglied
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.
 
Zuletzt bearbeitet:

DarXun

Aktives Mitglied
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
 
Zuletzt bearbeitet:

arilou

Bekanntes Mitglied
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".
 

minzee

Bekanntes Mitglied
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.
 
Zuletzt bearbeitet:
Ähnliche Java Themen
  Titel Forum Antworten Datum
Avalon Programmierstil beim Mocken Java Basics - Anfänger-Themen 45
S Zugriff auf protected Fields = guter Programmierstil? Java Basics - Anfänger-Themen 11
K Sauberer Programmierstil? Java Basics - Anfänger-Themen 3
F Erste Schritte Frage zum Programmierstil Java Basics - Anfänger-Themen 11
A OOP Fragen zu Programmierstil Java Basics - Anfänger-Themen 18
I Programmierstil Java Basics - Anfänger-Themen 64
E Richtiger Programmierstil ? Java Basics - Anfänger-Themen 51
M Sind ternäre Operatoren für einen guten Programmierstil wichtig ? Java Basics - Anfänger-Themen 10
M Programmierstil Java Basics - Anfänger-Themen 14
B Frage zu Programmierstil: sollte Hauptklasse nur main enthalten? Java Basics - Anfänger-Themen 6
G Guter Programmierstil? Java Basics - Anfänger-Themen 8
G Guter Programmierstil? Java Basics - Anfänger-Themen 4
D Programmierstil - Bei Vererbung welchen Typ benutzen? Java Basics - Anfänger-Themen 8
Bernasconi Programmierstil / Wann eine neue Datei? Java Basics - Anfänger-Themen 5
K guter Programmierstil Java Basics - Anfänger-Themen 3
C Programmierstil und OOP Java Basics - Anfänger-Themen 7
M Programmierstil Java Basics - Anfänger-Themen 17
D Programmierstil Java Basics - Anfänger-Themen 6
G Algorithmus Graphen Java Basics - Anfänger-Themen 10
M Berechnung der Reststrecke bei Graphen Java Basics - Anfänger-Themen 1
D Zusammenhängenden Graphen für Gleisnetz erstellen Java Basics - Anfänger-Themen 13
S Library fuer Graphen Java Basics - Anfänger-Themen 3
T Collections Methode (Knoten hinzufügen) für Graphen Java Basics - Anfänger-Themen 32
M Dijkstra Algorithmus in Graphen auf mehrere verschiedene Knoten anwenden lassen Java Basics - Anfänger-Themen 11
J Graphen in Java zeichnen Java Basics - Anfänger-Themen 11
L Graphen: Anzahl Knoten // Knoten in Array speichern Java Basics - Anfänger-Themen 4
U Best Practice Graphen Tiefensuche Klassifizierung von Kanten "B","C","F" Java Basics - Anfänger-Themen 2
B Java Graphen zeichnen - Brauche Hilfe Java Basics - Anfänger-Themen 9
M Ungerichtete Graphen Java Basics - Anfänger-Themen 21
V Graphen Java Basics - Anfänger-Themen 1
F Graphen-Algorithmen Java Basics - Anfänger-Themen 1
D Graphen abspeichern (Gewichte) Java Basics - Anfänger-Themen 9
W Funktions-Graphen "zeichnen" Java Basics - Anfänger-Themen 2
kulturfenster Graphen zeichnen Java Basics - Anfänger-Themen 5
0x7F800000 zwei adjazenzlisten für jeden knoten eines graphen sinnvoll? Java Basics - Anfänger-Themen 17
F Graphen Bibliothek Java Basics - Anfänger-Themen 38
T Graphen Java Basics - Anfänger-Themen 11
G Graphen Java Basics - Anfänger-Themen 3
M Graphen zusammenfügen Java Basics - Anfänger-Themen 2
E Zu einem Graphen die Kantenbewertung geben Java Basics - Anfänger-Themen 2
J Aus Graphen einen Spannbaum erzeugen Java Basics - Anfänger-Themen 5
M Graphen (Tiefensuche) Java Basics - Anfänger-Themen 2
I Reflection: Suche Feld + in Unterklassen Java Basics - Anfänger-Themen 7
LimDul Suche Java Stream Tutorial Java Basics - Anfänger-Themen 2
M Suche Resteasy Example Java Basics - Anfänger-Themen 24
B Beliebiger String gegeben Suche Datum in String Java Basics - Anfänger-Themen 6
M binäre Suche im Intervall Java Basics - Anfänger-Themen 6
M binäre Suche Java Basics - Anfänger-Themen 4
H Suche Java3D 32 bit Java Basics - Anfänger-Themen 20
amelie123456 Lineare Suche / Binäre Suche Java Basics - Anfänger-Themen 2
F Suche nach betreuender Person für eine Jahresarbeit der 12. Klasse. Java Basics - Anfänger-Themen 6
K Warum ist die binäre Suche bei der verketteten Liste nicht so effektiv? Java Basics - Anfänger-Themen 3
H Suche jemanden für kleine Uni-Abgabe/ mit Vergütung Java Basics - Anfänger-Themen 1
RudiRüssel Binäre Suche, unsortiert, lokales Maximum Java Basics - Anfänger-Themen 15
Y Suche von Studenten anhand Ihrer Eigenschaften. Java Basics - Anfänger-Themen 1
F Auf der Suche in π Java Basics - Anfänger-Themen 13
C Suche Nachhilfe in Java Java Basics - Anfänger-Themen 5
T Binärbaum-Suche Implementation Java Basics - Anfänger-Themen 6
A suche dringend Hilfe!! Java Basics - Anfänger-Themen 6
N Operatoren Schreibtischtest der Reihen-Suche nach Aufschluss in die Basics Java Basics - Anfänger-Themen 1
B Suche free SVN Hosting Java Basics - Anfänger-Themen 12
S Binäre-Suche Algorithmus Java Basics - Anfänger-Themen 1
S Java Lineare-Suche Zeitmessung Java Basics - Anfänger-Themen 5
S Java Lineare Suche Java Basics - Anfänger-Themen 1
S Binäre-Suche bei unsortierten Daten Java Basics - Anfänger-Themen 7
E Die richtige Suche in der API Java Basics - Anfänger-Themen 1
S suche nach varible POSITION ... fuer das pixel-maennchen Java Basics - Anfänger-Themen 4
E Weg-Suche-Problem rekursiv Java Basics - Anfänger-Themen 12
B Suche Programme mit Fehlern Java Basics - Anfänger-Themen 9
jaleda100 Component für Suche Java Basics - Anfänger-Themen 4
L Suche ein sampel Projekt Java Basics - Anfänger-Themen 2
P Suche Aufwandsgenerator (o-notation) Java Basics - Anfänger-Themen 1
S Suche aktuelles 2D Grafik Tutorial Java Basics - Anfänger-Themen 5
M Suche hilfe bei Array Java Basics - Anfänger-Themen 4
L Binäre Suche mit Comparator Java Basics - Anfänger-Themen 5
J Methoden Suche effiziente Implementierung für eine Methode Java Basics - Anfänger-Themen 3
D Ich suche nach einer Möglickeit den Webseiten Inhalt per Java zu analysieren Automatisch Java Basics - Anfänger-Themen 3
B String: suche nach Wörter und in List<String> speichern Java Basics - Anfänger-Themen 3
D Erste Schritte Suche Quelltext Java Basics - Anfänger-Themen 7
M Rekursion Minimums Suche Java Basics - Anfänger-Themen 12
J Suche Hilfestellung Java Basics - Anfänger-Themen 10
G Erste Schritte Suche Java Programmierer für kleines Projekt Java Basics - Anfänger-Themen 1
J Suche die Emailadresse Java Basics - Anfänger-Themen 6
H Suche in Text und Markierung Java Basics - Anfänger-Themen 14
H Suche in einem Text Java Basics - Anfänger-Themen 17
H Erste Schritte Binäre Suche Java Basics - Anfänger-Themen 37
J Suche simples Beispiel für die EOFException Java Basics - Anfänger-Themen 1
H Rekursion Binäre Suche Java Basics - Anfänger-Themen 2
L Binäre Suche Java Basics - Anfänger-Themen 2
L Linerae Suche in einem sortierten Array Java Basics - Anfänger-Themen 2
N Array, lineare Suche, binäre Suche, Programm bleibt unerwartet stehen... Java Basics - Anfänger-Themen 6
I Innerhalb einer Methode suchen und hinzufügen. Neues Objekt in Suche dann? Java Basics - Anfänger-Themen 8
B Binäre Suche - Junit Test Java Basics - Anfänger-Themen 6
L Einfache Lineare Suche Java Basics - Anfänger-Themen 7
J Binäre Suche eines Array Java Basics - Anfänger-Themen 5
M Methoden Binäre Suche als rekursive Variante Java Basics - Anfänger-Themen 5
D Suche nach der Anzahl von Zonen zwischen zwei Punkten Java Basics - Anfänger-Themen 2
M Benutzerdefinierte Suche in einem String - outofbounds Java Basics - Anfänger-Themen 7
X Best Practice SUCHE ein gutes Javabuch! (kein Anfang von 0) Java Basics - Anfänger-Themen 5
B Binäre Suche in einem String Array Java Basics - Anfänger-Themen 10

Ähnliche Java Themen

Neue Themen


Oben