Prüfen ob ein Graph immer einen von mehren Enden erreicht

Yanko

Mitglied
Hallo zusammen,

dies ist zwar kein Javaspezifisches Problem, sondern eher, was für einen Algorithmus ich verwenden kann, um mein Problem zu lösen.

Für mein Spiel schreibe ich gerade einen Questeditor. Das Spiel läuft Pen&Paper mäßig ab.
Es gibt einen Abschnitt(Knoten) der durch ein oder mehrere Aktionen(Kanten) zum nächsten Abschnitt führt. Man hat also die Wahl zwischen z.B.: 3 Aktionen, die alle zu einem anderen Abschnitt führen können. Dabei können sie auch auf den Aktuellen Abschnitt führen und zu einem vorherigen(auch den Startabschnitt). Dann gibt es beliebig viele Endabschnitte. Sobald ein solcher erreicht wurde, ist das Quest zuende.

Das Modell entspricht eigentlich dem eines gerichteten Graphen, soweit ich mich bisher darüber informiert habe.

Nun will ich beim entgültigen Speichern überprüfen, ob das Quest durch alle möglichen Aktionen zu einem beliebigen Endabschnitt führt. Der Endabschnitt ist die Selbe Klasse wie ein Normaler Abschnitt nur gibt isEnd() true aus statt false.

Die Algorithmen die ich bisher gefunden habe zeigen entweder den kürzesten weg oder die anzahl der Knoten die man von einem punkt aus erreichen kann. Das hilft mir leider bei meinem Problem nicht weiter.

Ich selber bin davor bei meinen Überlegungen einfach alle Aktionen ausgehend vom Start durchgegangen.
Das Problem war zuerst, dass ich in eine Endlosschleife geraten bin. Dies habe ich gelöst indem ich Flags gesetzt habe. Jetzt habe ich aber das Problem, wenn ich einen Abschnitt mit 2 Aktionen habe, bei dem die 1. Aktion immer auf den Abschnitt selbst zeigt und nur Aktion 2 zum nächsten Abschnitt führt, ich wegen Aktion 1 ein false bekomme. Und es gibt ja auch noch die Möglichkeit über mehrere Abschnitte eine Solche endlosschleife zu erzeugen bei dem flags gesetzt werden und dann ein knoten nicht mehr besucht werden kann obwohl es von diesem aus weitergehen würde.

Ich hoffe sehr, dass jemand von euch weiß wie ich das Problem lösen kann.

Yanko
 

Marco13

Top Contributor
Spontan würde ich da auf eine ganz normale Breitensuche tippen. Aber... ein paar Details sind noch unklar.. z.B. gibt es "End"knoten, die ausgehende Kanten haben?
 

Yanko

Mitglied
Nein die Endknoten haben keine Kanten mehr.

Eine Idee wäre noch Von jedem Nicht-Endknoten die Breitensuche mit allen Endknoten durchzuführen, aber das wächst doch dann sehr sehr schnell. Z.B.: 200 Knoten + 10 Endknoten wären dann
2000 mal die Breitensuche.
 
Zuletzt bearbeitet:
S

SlaterB

Gast
selbst wenn es dein Algorithmus wäre, warum von jedem Knoten aus für jeden der 10 Endknoten eine einzelne Suche?
das eine bzw. alle 10 Ziele sind doch nur zufällige Ergebnisse auf dem Weg, davon hängt die Suche doch nicht ab,
maximal eine Suche, welcher Art auch immer, pro Knoten

generell scheint das aber unnötig, reicht folgende EINE Suche insgesamt?:
gehe von den 10 Endknoten aus, suche alle Vorgängerknoten, füge all diese in eine Menge X,
dann suche alle weiteren noch nicht besuchten Vorgängerknoten usw.,
so lange bis nichts mehr dazukommt, am Ende gibt es noch nicht besuchte Knoten des Graphen oder auch nicht

du müsstest in deinem gerichteten Graph auch die Vorgänger-Beziehung eintragen, doppelt verlinken,
interessant wäre ein richtiger Gegengraph, die End-Knoten als neue Start-Knoten

-------

ohne Gegenrichtung nur vom Start aus den gesamten Graphen abwandern kann ich mir auch vorstellen,
die Wege merken, bei jeder denkbaren Verzweigung in zwei Wege aufspalten,
vor allem aber auch wieder zusammenfügen wenn zwei Wege zum selben Knoten kommen, sonst ja endloses Wachstum,

wieder besuchte Knoten merken, nichts unnötig doppelt machen, ergo keine Schleifen,

alle Wege müssen zu einem Endknoten führen

-------


ob es mit 'Abschnitte & Aktionen' jeweils Probleme geben kann ist nicht so leicht erkennen,
Beispiele sind wahres
 

bERt0r

Top Contributor
Hab versucht meinen Gedankengang in Worte zu fassen, habs lieber gleich programmiert (nicht getestet):
Java:
import java.util.*;

public class QuestValidator
{
	class Location
	{
		public List<Location> getLinkedLocations()
		{
			return null;
		}
		
		public boolean isEnd()
		{
			return true;
		}
	}
	
	public QuestValidator()
	{
		visited = new TreeSet<Location>();
		valid = new TreeSet<Location>();
	}
	
	Set<Location> visited, valid, suspicious;
	
	public void canReachEnd(Location loc)
	{
		if (loc.isEnd() || valid.contains(loc))
		{
			valid.add(loc);
			return;
		} else
		{
			visited.add(loc);
			for (Location l : loc.getLinkedLocations())
			{
				if (!visited.contains(l))
				{
					canReachEnd(l);
				}
				if (valid.contains(l))
				{
					valid.add(loc);
				}
			}
		}
	}
	
	public boolean hasDeadEnd()
	{
		suspicious = new TreeSet<Location>();
		suspicious.addAll(visited);
		
		boolean repeat = true;
		while (repeat)
		{
			repeat = false;
			suspicious.removeAll(valid);
			
			for (Location loc : suspicious)
			{
				for (Location l : loc.getLinkedLocations())
				{
					if (valid.contains(l))
					{
						repeat = true;
						valid.add(loc);
					}
				}
			}
		}
		return !suspicious.isEmpty();
	}
}
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
8u3631984 Prüfen ob min. ein Element eines Sets in einem anderen Set enh Allgemeine Java-Themen 4
OnDemand Prüfen ob Bild defekt ist Allgemeine Java-Themen 4
N Prüfen, ob ein String 2x das selbe Zeichen hat Allgemeine Java-Themen 10
W Classpath Reflexion - Prüfen ob man auf ein Feld ändern kann Allgemeine Java-Themen 2
OnDemand Bild prüfen ob defekt Allgemeine Java-Themen 3
B Java Mail: Prüfen, ob Email hat ein Anhang oder nicht Allgemeine Java-Themen 2
Bluedaishi Prüfen ob Datei noch geöffnet ist Allgemeine Java-Themen 59
Stonie Prüfen von direkter Implementierung eines Interfaces Allgemeine Java-Themen 7
J Mit Lombok Integer Range prüfen Allgemeine Java-Themen 6
S Prüfen ob Textfile existiert Allgemeine Java-Themen 9
E Programm auf Installation prüfen Allgemeine Java-Themen 1
S Binärbaum prüfen Allgemeine Java-Themen 0
L String auf zahlenwert prüfen Allgemeine Java-Themen 13
W Datum prüfen + zweistellig Allgemeine Java-Themen 11
perlenfischer1984 Functionsparameter prüfen und eine Exception werfen !? Allgemeine Java-Themen 11
Z Java Exceptions - Auf leeres Feld prüfen Allgemeine Java-Themen 10
F Wie kann ich auf einem System prüfen, ob eine lib verfügbar ist? Allgemeine Java-Themen 2
P Prüfen ob es Variable mit Namen gibt der als String übergeben wird Allgemeine Java-Themen 7
M .jar nach Datei prüfen Allgemeine Java-Themen 2
B Existenz eines Files max 30 sec prüfen Allgemeine Java-Themen 5
B Prüfen, ob ein Element in der Liste nicht existiert Allgemeine Java-Themen 3
F Cardlayout prüfen ob schon vorhanden, keine doppelten Allgemeine Java-Themen 3
turmaline Regex gegen Regex prüfen Allgemeine Java-Themen 4
S Lambda Ausdrücke: @FunctionalInterface Instanzen auf null prüfen Allgemeine Java-Themen 9
D ArrayList index auf gültigkeit prüfen Allgemeine Java-Themen 12
C Best Practice [Arrays] Wie sinnvoll prüfen, ob Array primitive Datentypen enthält? Allgemeine Java-Themen 6
L Prüfen, ob Programm über 32bit oder 64bit Java ausgeführt wird Allgemeine Java-Themen 4
K Methoden Arrays auf true Werte prüfen Allgemeine Java-Themen 4
O Prüfen ob String eine Zahl mit maximal 2 Nachkommastellen ist Allgemeine Java-Themen 4
M datei aufruf prüfen Allgemeine Java-Themen 9
D Best Practice Prüfen ob jar nachträglich geändert wurde Allgemeine Java-Themen 2
B Dateien prüfen auf Gleichheit Allgemeine Java-Themen 5
H String auf Zahlen prüfen Allgemeine Java-Themen 4
T auf Valides Datum prüfen Allgemeine Java-Themen 12
N Java Version Prüfen lassen Allgemeine Java-Themen 11
S Variablen Prüfen ob Number vom Typ Integer, Float, Double, ... ist Allgemeine Java-Themen 2
E selber Klassen kompilieren/ prüfen Allgemeine Java-Themen 5
O Variablen Originalname einer übergebenen Variable prüfen Allgemeine Java-Themen 9
T Methoden Zahlenpalindrom laufzeitoptimiert prüfen Allgemeine Java-Themen 4
U ResourceBundles auf vollständigkeit prüfen Allgemeine Java-Themen 2
C jollyday: prüfen, ob Datum = Feiertag Allgemeine Java-Themen 8
C Prüfen ob sich ein Punkt innerhalb einer Kugel befindet (Java3D,nicht-lineare GLS) Allgemeine Java-Themen 5
M Objekt prüfen auf null ->Invocation Target Exception??? Allgemeine Java-Themen 2
E Prüfen ob Fenster mit Namen offen ist Allgemeine Java-Themen 2
M Binärbaum auf vollständigkeit prüfen Allgemeine Java-Themen 4
S Mail Adressen Syntax prüfen Allgemeine Java-Themen 22
O Text mit Wildcard gegen regulären Ausdruck prüfen Allgemeine Java-Themen 3
N List auf null prüfen Allgemeine Java-Themen 2
B generischen Typ prüfen Allgemeine Java-Themen 7
D prüfen, ob Enums bestimmte Elemente enthalten Allgemeine Java-Themen 3
N Prüfen ob Methode ausgeführt wird und diese ggf. abbrechen? Allgemeine Java-Themen 8
B Prüfen ob ein Programm gestartet wurde Allgemeine Java-Themen 23
N ArrayList nach Reihenfolge prüfen Allgemeine Java-Themen 2
C Prüfen auf Zahl und 6 stellig fehlerhaft? warum? Allgemeine Java-Themen 7
D Wie prüfen, ob ein String Teil eines Enum Types ist? Allgemeine Java-Themen 12
H Prüfen, ob doppete Werte in int-Array vorhanden sind Allgemeine Java-Themen 16
data89 Bilder mit Java prüfen - suche dringend Hilfe Allgemeine Java-Themen 8
S Prüfen auf Hex-Wert fester Länge! Allgemeine Java-Themen 5
M Prüfen, welche anderen Programme laufen Allgemeine Java-Themen 5
K Zip dateien prüfen Allgemeine Java-Themen 3
G ZIP Archiv auf Konsistenz prüfen Allgemeine Java-Themen 2
T Parameter einer Klasse auf Interface prüfen Allgemeine Java-Themen 6
L Passwort mit Regulärem Ausdruck prüfen Allgemeine Java-Themen 6
P Sound Buffer prüfen Allgemeine Java-Themen 12
B PrintService - Wie prüfen ob Drucker online ist? Allgemeine Java-Themen 2
A Textfeld prüfen, ob ein Punkt eingegeben wurde Allgemeine Java-Themen 8
flashfactor Prüfen ob bereits eine Instanz gestartet ist Allgemeine Java-Themen 2
C Prüfen, ob eine Methode eine andere überschreibt! WIE? Allgemeine Java-Themen 8
T Prüfen, ob Char ein Quantifier ist Allgemeine Java-Themen 6
N Prüfen ob Objekt in Liste enthalten ist Allgemeine Java-Themen 17
G Prüfen welche JRE-Version gebraucht wird Allgemeine Java-Themen 19
J Mit Patternmatching einen Satz prüfen Allgemeine Java-Themen 12
G Prüfen ob Ziffern einer Zahl pandigital sind? Allgemeine Java-Themen 15
M Prüfen ob Variable vorhanden / initalisiert ist Allgemeine Java-Themen 4
J Wie prüfen ob eine Datei vom OS fertig geschrieben wurde? Allgemeine Java-Themen 6
TheJavaKid Zeile auf existenz von String prüfen. Allgemeine Java-Themen 19
A Weshalb man Parameter auf Gültigkeit prüfen sollte Allgemeine Java-Themen 6
N Prüfen ob ein String in einen Integer umgewandelt werden kan Allgemeine Java-Themen 4
O String auf zahlen prüfen (java 1.3) Allgemeine Java-Themen 4
G Datei Zugriffsrechte prüfen Allgemeine Java-Themen 2
Linad Bilder auf Gleichheit prüfen Allgemeine Java-Themen 6
G ResultSet auf Inhalt prüfen? Allgemeine Java-Themen 2
H Prüfen, ob es sich um ein Integer handelt Allgemeine Java-Themen 4
C String str prüfen Allgemeine Java-Themen 3
H Prüfen ob ein String grösser als 4 Zeichen ist Allgemeine Java-Themen 3
F Prüfen, ob Windows oder UNIX Allgemeine Java-Themen 2
B Sehr großen Graph mit Verbindungen bauen und minimieren? Allgemeine Java-Themen 35
N Graph Visualizition Allgemeine Java-Themen 5
B Type mismatch: cannot convert from Graph.Edge to ArrayList<Graph.Edge> Allgemeine Java-Themen 21
T Graph/Adjazenzliste programmieren Allgemeine Java-Themen 10
F Framework/Plugin für Tree-Darstellung in Graph Allgemeine Java-Themen 0
J Breitensuche in Graph rekursiv Allgemeine Java-Themen 2
H Graph-Algorithmus gesucht Allgemeine Java-Themen 21
M Jaxb und JPA: A cycle is detected in the object graph Allgemeine Java-Themen 5
T Algorithmus Graph Allgemeine Java-Themen 10
Mike90 Graph in einer Mail verschicken Allgemeine Java-Themen 7
N Graph mit JUNG-Framework erstellen Allgemeine Java-Themen 2
as182005 Bibliothek für Graph Visualisierung gesucht Allgemeine Java-Themen 3
dru Graph aus Ascii Daten erstellen Allgemeine Java-Themen 2
P Graph Permutationen Allgemeine Java-Themen 29

Ähnliche Java Themen

Neue Themen


Oben