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

[Yanko]

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]

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]

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.

 

[SlaterB]

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]

Hab versucht meinen Gedankengang in Worte zu fassen, habs lieber gleich programmiert (nicht getestet):

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();
	}
}