Graph-Algorithmus gesucht

[hans98]

Ist nicht speziell Java, sondern ein algorithmisches Problem:

Ich habe einen ungerichteten Graphen der zusammenhängend und kreisfrei ist (ein ungerichteter Baum).
Ich möchte nun diesen Baum zu einem gerichteten Baum mit einer Wurzel machen.
Welchen Knoten muss ich als Wurzel nehmen, damit der gerichtete Baum möglichst geringe Tiefe hat? Und wie berechne ich diesen möglichst effizient?

Bisher ist mir nur eingefallen, von jedem Knoten aus den Breitensuchbaum zu berechnen und denjenigen Breitensuchbaum auszuwählen, der die geringste Tiefe hat. Dies erfordert aber n^2 Schritte bei n Knoten des Graphen. Es müsste schneller gehen, vermute ich.

Hans

 

[SlaterB]

sollte linear gehen,
laufe die Liste der Knoten einmal ab oder meinetwegen den Baum von irgendwo aus, finde die Blätter mit nur einem Nachbarn,
gib denen Tiefe 1,
sammle von denen alle Nachbarn, gib denen Tiefe 2
und weiter wiederholend: von den neuen Tiefe 2-Elementen alle Nachbarn holen,
wenn schon bekannt (Tiefe 1 oder 2 (edit: gleiche Tiefe wie eigene für Nachbarn dürfte es ohne Kreise nicht geben)), dann ignorieren,
die neuen aber bekommen Tiefe 3

usw. bis irgendwann nix neues mehr, im letzten Schritt hast du auch gleich den/ die tiefsten

 

[hans98]

Also eine Art Breitensuche von den Blättern aus. Das Problem ist, dass es mehrere "tiefste" Knoten geben kann, ich brauche aber "die" Wurzel. Beispielgraph:

O--O
|
O--O
|
O--O
|
O--O

Die links liegenden Knoten bekommen alle die Tiefe 2. Wie finde ich unter denen die Wurzel?

 

[SlaterB]

oha, doch Nachbarn der gleichen Stufe 2, Mist,
und da habe ich es ja einmal mehr viel zu einfach angegangen,
eher die minimale als maximale Tiefe, wie für Baum nötig,

dann schlage ich immer noch spontan vor, ich hoffe das geht dir nicht zu sehr gegen den Sinn deines Threads, vielleicht nur professionelle Links zu bekommen :

etwas in Richtung deiner Breitensuche, nur etwas anders, nur von außen angefangen,
und noch optimiert um hoffentlich die Arbeit etwas zu reduzieren

dein Beispiel vergrößere ich auf
U1--O1
|
U2--O2
|
U3--O3
|
P4--Q4--R4--S4--T4--A4--B4--C4--D4--U4--O4
|
U5--O5
|
U6--O6
|
U7--O7
|
U8--O8
|
U9--O9

die Bezeichungen sind hier nur Deutlichkeit, haben keine Funktion
(zwischendurch auch paar mal am Beispiel geändert, nicht wundern wenn mal falsche Knotennamen genannt werden)

begonnen wird immer noch bei den gefundenen Blättern, O1-O9, Tiefe 1, auch O4,
danach geht es zu allen U, auch U4, eben die Nachbarn,

die neue Nachbarmenge bestimmen, enthält nun zahlreiche bekannte Elemente, die weiter verfolgt werden müssen,
nahe deiner Breitensuche wäre erstmal die Variante, von jedem Startpunkt aus in alle Richtungen zu arbeiten:
etwa von O8 bis runter nach O9 mit Tiefe dort dann 4, auf dem Weg 1, 2, 3,
diese Tiefen müssen mit den Kanten verbunden werden (hier vielleicht noch nicht wichtig,
aber für später, gleich mal eingeführt):
U9 hat von oben (durch die Suche von O8 kommend) her die Tiefe 3, von rechts her Tiefe 2,

später kommt von O7 aus die Suche nach O9 vorbei, U9 bekommt dann überschrieben, da größer,
Tiefe 4 von oben kommend usw.,

zwischen O9 und O4 ist letzlich der längste Weg,
O4 hat von links die höchste Tiefe 17 oder so, O9 von links auch,

das Ziel ist nun der Knoten, welcher von allen Seiten die niedrigsten Eingänge hat,
O4 und O9 mit 17 sicher nicht, U9 und U4 mit Tiefe 16 auch nicht,
das Optimum liegt bei R4 oder so, keine Kante dürfte mehr als 9 haben oder so,

das ist dein Ziel, ein erster neuer Algorithmus (edit: unten wird letztlich noch anderes draus, nur zu verstehen (falls überhaupt) wenn alles gelesen),
vielleicht jetzt schon bisschen besser als n^2, kannst du ja evtl. testen, allein durch Zählen,
aber in erster Linie hoffe ich auf Korrektheit

-----

Optimierung:
nicht sklavisch von allen Blättern aus überall hinwandern, sondern anhand der Zwischenergebnisse
überflüssige Arbeit vermeiden, hier werden nun die Tiefen an Kanten wichtig,
vorher hätte wohl doch auch nur eine Tiefe pro Knoten gereicht:

nachdem alle O gefunden sind bekommen alle U auf einer Kante die Tiefe 2,
im nächsten Schritt gibt es auch noch keine Konflikte,
von U8 aus etwa bekommt U7 mit der unteren Kante die Tiefe 3,
von U7 aus bekommt U8 mit der oberen Kante die Tiefe 3 usw.,
alle U sind nun ziemlich 'bedient',
wobei aber etwa U4 von links noch nichts hat, U3 von unten noch nichts usw.

dabei muss irgendwie gemerkt werden, welche Aktionen/ Prozesse noch 'laufen', weiter wandern wollen,
die müssen ihre Richtung und Tiefe kennen usw.,
was war weiter oben vor der Optimierung auch schon nötig, nicht zu genau beschrieben

im nächsten Schritt gibt es jedenfalls erstmals gewisse Kollisionen,
etwa hatte ja U8 von unten aus die Kante mit 3 bezeichnet, das läuft nun weiter nach U7,
dort gibt es bereits einen ProzessO8 der von O8 kommend eine 3 an die Südkante von U7 schrieb,

der neue ProzessO9, von O9 gestartet, ist nun mit 4 an dieser Kante überlegen,
daran muss festgestellt werden, dass ProzessO8 abgebrochen werden kann, muss gar nicht mehr
weit bis O4, O1 usw. laufen, ProzessO9 wird in jedem Fall besser sein,

die ganze Arbeite von ProzessO8 kann eingestampft werden, zumindest in Richtung von U7 nach oben,
alles was in diesem Zusammenhang läuft, vielleicht schon verzweigt mehrere Wege, aber hoffentlich gemerkt
mit U7 als Zwischenstation, wird nicht weiter verfolgt,
die eingetragenen Kantenwerte usw. (wobei ich inzwischen bezweifle, dass man das so direkt umsetzt)
können stehenbleiben, werden bald von ProzessO9 überschrieben,

in diesem, noch nicht gerade 100% genauen Sinne, laufen mit der Zeit immer weniger Prozesse,
ein paar überleben aber, auch sind die Richtungen zu beachten

wenn etwa ProzessO9 bei P4 von unten ankommt, dann sind die ProzesseO5-O8 Geschichte (zumindest in nördliche Richtungen),
von oben aber läuft noch der sich durchgesetzte ProzessO1, ist schon nach rechts bis R4 gelangt,
im nächsten Schritt wird auch der gekillt, ProzessO9 ist besser in diese Richtung,

ProzessO1 läuft aber noch in südliche Richtung nach U5 usw. weiter, das ist wichtig,
wäre der 4er-Strang kürzer, hätte ProzessO1 den Prozess von dort vielleicht gekillt oder andersrum,
ich habe ihn hier extra lang gelassen so dass der noch längst nicht da ist
und erst später ProzessO1 ersetzt

soweit mal wieder ein Punkt, ist viel zu lang geworden, ich kann verstehen falls du das nicht mögen solltest ,
aber ist eine Variante, gibts vielleicht sogar offiziell

-----

und noch länger:

weitere Optimierungen, die mir noch einfallen:
wenn es Ketten wie die 4er hier gibt, mit nur einen Nachfolger jeweils, dann die bevorzugt bis zur
ersten Kreuzung führen, das würde hier verhindern, dass ProzessO1 alles bis nach ganz unten
durchrechnet, bis dann ProzessO4 alles überschreibt,
anderseits tritt das in der Realität wohl nicht so oft auf,

reizvoll wäre andersrum noch, dass ProzessO1 vielleicht schon weit kommt/ fertig ist nach Süden,
beim Kill durch ProzessO4 dann aber alle Ergebnisse 1:1 übernommen werden, nur mit höherer Tiefe,
was anderes kann ja kaum rauskommen wenn ProzessO1 da selber nochmal langläuft,

----

vielleicht ist es generell sinnvoll (um den obigen Ablauf weitgehend auf den Kopf zu stellen!),
erstmal einen Prozess komplett durchlaufen zu lassen:
zufällig gewählt z.B. ProzessO7 als ersten, der hat viele Wege zu alle Ecken,
im wesentlichen drei (wie intern modeliert lasse ich offen), nach O9 im Süden,
nach O4 und nach O1, aber auch zu allen anderen O Teilwege,

danach ist zufällig ProzessO8 dran, der kommt erst normal bis U8, von rechts hatte U8 ja bisher gar nichts,
von U8 nach oben, also die untere Kante von U7, ist auch noch unbesetzt,
nach unten aber, Richtung U9, hat ProzessO7 schon einen stattlichen Weg/ eine Tiefe gesetzt, die ProzessO8
nicht toppen kann, da aufhören,
nach oben zu U7 geht es noch weiter, nach rechts zu O8 auch, weiter nach oben Zu U6 ist jetzt
ProzessO8 'besser' als ProzessO7, sämtliche Wege mit neuer korrekter höherer Tiefe übernehmen,
ProzessO7 kann diese alle vergessen, ruhigen Gewissens durchaus als Objekte abgeben, bleibt aber
nach Süden noch zu O8 und O9 'im Spiel'

so geht das weiter, Wege werden übernommen, neu hinzugefügt, am Ende bleiben durchaus eine Menge über,
daraus ergeben sich die Eingangs-Kanten-Gewichte und immer noch R4 (oder so )

dieses 'Übernehmen von Wegen' kann andererseits auch im laufenden Betrieb geschehen,
wäre nicht so schlimm wenn wie oben alle Prozesse gleichzeitig starten,
falls aber anscheinend nacheinander kein Nachteil ist, dann ist nacheinander sicher übersichtlicher und zu bevorzugen!

puh, rekordverdächtiges Posting, ich hoffe nun auch für dich, dass irgendjemand noch eine Zeile mit Link postet

welche Komplexität da herauskommen würde, wäre anhand eines Beispiels interessant,
formal vielleicht immer noch n^2, aber mit so vielen Abkürzungen, dass es in der Realität deutlich schneller geht

 

[Marco13]

Den Text habe ich jetzt nicht ganz gelesen aber hätte auch einen Ansatz, der SO einfach klingt, dass er vermutlich falsch ist (aber jetzt vor der Mittagspause werde ich da nicht sooo lange drüber nachdenken).

Mein erster Gedanke war, von irgendeinem Knoten R aus eine Breitensuche zu machen. Dann ist R die Wurzel, und man beokmmt einen Baum, der vermutlich nicht die minimale Tiefe hat. Man kennt aber (bzw. kann herausfinden) auf welchem Pfad man von der Wurzel aus zum tiefsten Knoten kommt. Und ... der erste Knoten dieses Pfades ist die neue Wurzel. Das wiederholt man so lange, bis es zwei tiefste Knoten gibt.
...

Bildlich gesprochen: Man hält den Graphen irgendwo fest, und die Kette, die am tiefsten runterbaumelt, fasst man etwas weiter unten an.

...

Das war's eigentlich schon :bahnhof: Man müßte sich noch überlegen, wie man effizient das Update für die Tiefe macht, nachdem man die neue Wurzel "hochgezogen" hat, aber das sollte nicht schwer sein.

 

[SlaterB]

klingt vernünftig für mich,
falls mein Posting das andere mit veranlasst hat, wäre ich schon zufrieden

 

[hans98]

Erstmal vielen Dank für die Diskussion!

@Marco13: Ein schöner Ansatz! Vor allen Dingen das "Baumelnlassen"...
Aber wenn es sich bei dem Graphen um eine Kette von Knoten der Länge n handelt, bräuchte man n/2 Breitensuchen, also hätte man Komplexität n^2.

@SlaterB: "begonnen wird immer noch bei den gefundenen Blättern, O1-O9, Tiefe 1, auch O4,
danach geht es zu allen U, auch U4, eben die Nachbarn, die neue Nachbarmenge bestimmen, ..."

Das hat mich auf die Idee gebracht, von dieser Nachbarmenge, den U-Knoten, die "Blätter" zu bestimmen, wobei jetzt die O-Knoten nicht mehr mitspielen (indem ich sie markiere).

Diese "Blätter" sind U1, U4 und U9, d.h. es sind Knoten, die höchstens einen Nachbarn haben, wobei wie gesagt die markierten Knoten nicht als Nachbarn zählen.

Von diesen "Blättern" bestimme ich jetzt wieder die Nachbarmenge: U2, D4 und U8. Anschließend markiere ich die "Blätter" U1, U4 und U9, damit sie ab jetzt nicht mehr mitspielen.

Von der Nachbarmenge U2, D4 und U8 bestimme ich wieder die "Blätter", dies sind sie alle, und anschließend deren Nachbarmenge: U3, C4 und U7.

Und so weiter. So arbeite ich mich an die gesuchte Wurzel heran.
Ich will mal versuchen das zu programmieren und dann mal sehen, ob sich Komplexität O(n) erreichen lässt.

Grüße
Hans

 

[SlaterB]

oje, ne vergiss lieber meinen Vorschlag (edit: aber deiner klingt ja wiederum ganz anders,
edit2: klingt wirklich nicht schlecht, aber da wiederum ist auch Richtung n^2 anzunehmen,
in jeder Runde alle Knoten anschauen und du hast viele Runden, je größer der Graph ist),
(edit3: was selbst die Performance meiner noch aufwendigeren Variante nochmal schlechter aussehen läßt..)

------

man braucht keine n/2 Suchen beim "Baumelnlassen", das ist glaube ich zu vermeiden,

schau dir mein Beispiel an, zufällig beginnend mit O5,
der längste Weg wäre der nach O4, was aber nicht der längste im Graph überhaupt ist (O4 nach O9)

sucht man sich aber allein im ersten Schritt von O5 bis O4 die Mitte aus, also etwa T4, das ist schnell gemacht, bisher linear, n,
dann denke ich dass man spätestens nach diesem ersten Durchgang auf der längsten Linie, nämlich der von O4 nach O9 gelandet ist,

durch die zweite Suche, eben von ~T4 aus findet man diese Linie, und jetzt nur noch die Mitte davon, wieder linearer Aufwand,

wenn ich mich irre, was sicher wahrscheinlich ist.., dann vielleicht noch paar mehr Hopser, aber ich sehe nicht ein,
warum man eine 1000er-Kette in Einzelschritten entlanggehen und jedes Mal eine neue aufwendige Suche starten sollte

 

[Logaff]

da gibst auch lustige Bäume als datenstruktur die automatisch die Höhe balancieren. Ich empfehle dir einfach jeden Knoten ein ein AVL-Baum zu speichern. Brauchst halt nur bei jedem hinzufügen nach balanciertheit betrachten und wenn irg was nich ok ist rotieren^^.

ACHTUNG: kann schief gehen wenn die Knoten irg wie eine bestimmte beziehung zueinander haben (kann man aber auch regeln mit Heaps die balanciert werden durch Rotationen)

Breiten suche von einen Knoten würde im schlimmsten Fall ein Baum mit lineare Höhe bilden da

o-o-o-o-o-o =Breitensuche=> o-o-o-o-o-o
als Ergebniss hat. Breitensuche löst das ganze wirklich nur bescheiden.

Nützliche Links:
Balancierte Bäume
Balanced Search Trees
AVL-Baum
alternativ: Rot-Schwarz-Baum

Wenn du noch Fragen hast meldest dich und ich kann dir auch noch Uni-Folien zum Thema Bäume zukommen lassen (ist auch als nicht Student gut verständlich <- denk ich)

 

[Marco13]

Die Parallelen zu balancierten Bäumen sind offensichtlich, und mein Ansatz hat seinen Grundgedanken sicher in der Nähe des angesprochenen "rotierens". Ich habe das nicht mehr genau genug im Kopf, um es mit Sicherheit sagen zu können, meine aber, dass das in der z.B. bei AVL-Bäumen oder Heaps verwendeten Form NICHT möglich ist, wenn (wie in diesem Fall) die Topologie strikt vorgegeben ist - könnte mich aber auch irren

 

[hans98]

@Logaff: Die Struktur oder Topologie meines ungerichteten Graphen ist vorgegeben und soll nicht verändert werden - also beispielsweise eine Kette wie 1--2--3--4--5 bleibt in dieser Weise verbunden. Es geht nicht darum, 5 Knoten als balancierten Baum zu organisieren. Es geht darum, den ungerichteten Baum 1--2--3--4--5 in einen gerichteten Baum mit Wurzel umzuwandeln, indem einer der Knoten zur Wurzel erklärt wird, so dass alle Kanten von der Wurzel in Richtung Blätter gerichtet sind. Und zwar so, dass ein gerichteter Baum minimaler Tiefe herauskommt, also so:

3
/ \
2 4
| |
1 5

Also das von Marco13 angesprochene "Baumelnlassen"

Hans

 

[Marco13]

Bist du da eigentlich weitergekommen? (Hatte mal angesetzt da einen Test dafür zu schreiben, ist aber zeitlich gerade schlecht und nicht sooo weit oben auf meine Prioritätenliste )

 

[SlaterB]

einmal mehr mich zu korrigieren, oder?:
die Streichen-Variante sollte doch (auch) linear sein, am Anfang linear die Blätter suchen,
danach für jeden Knoten konstanten Aufwand:
die meiste Zeit nicht betrachtet, irgendwann kommt er mal dran, einmalig die Nachbarn ermitteln und ihn streichen, danach wieder Ruhe

einzelne Brennpunkt-Knoten können zwar viele Verknüpfungen haben, theoretisch bis zu n-1, öfter nicht in der Nachbar-Menge zu bearbeiten sein,
aber dann würde es gleich viele Blätter geben, das sollte sich ausgleichen, im Durchschnitt linear bleiben,
nur n-1 Kanten im Graph

 

[Ark]

Habe mir gerade auch mal Gedanken gemacht, und ich glaube, bei mir läuft's auf den gleichen/ähnlichen Algorithmus hinaus, den SlaterB schon vorgeschlagen hat. Zwar noch völlig ungetestet, aber ungefähr so könnte es aussehen (Pseudocode):

BLÄTTER := {Menge aller Blätter}
ABGEARBEITET := {}
KANDIDATEN := {}

solange |BLÄTTER| > 0
	KANDIDATEN := BLÄTTER
	NEUE_BLÄTTER := {}
	für alle b in BLÄTTER:
		ABGEARBEITET := ABGEARBEITET.plus(b)
		n := nachbar(b)
		falls n = NIL
			Abbruch des Algorithmus
		falls grad(n ohne ABGEARBEITET) <= 1
			NEUE_BLÄTTER := NEUE_BLÄTTER.plus(n)
	BLÄTTER := NEUE_BLÄTTER

KANDIDATEN sollte dann die Menge aller Knoten enthalten, die in Frage kommen. "grad(n ohne ABGEARBEITET)" meint den Grad, den der Knoten n hätte, wenn die Knoten in der Menge ABGEARBEITET nicht mehr zum Graphen gehören würden.

Ich schätze ebenfalls auf O(n), wenn "grad(n ohne ABGEARBEITET) <= 1" mit konstantem Aufwand feststellbar ist. Ansatz dazu: Beim Ermitteln der Blätter den Grad jedes Knotens gleich aufschreiben und den Grad entsprechend der abgearbeiteten Knoten anpassen. (Dann braucht man auch keine eigene Menge ABGEARBEITET mehr.)

Aber wie gesagt: alles noch völlig ungetestet. Und außerdem ist es schon spät.

Ark

 

[Marco13]

einmal mehr mich zu korrigieren, oder?:

Es geht natürlich nicht ums Korrigieren Es geht ums Übertrumpfen wenn schon nicht mit der Qantität, dann doch mit der Qualität :smoke:

:joke:

Mal im Ernst, der Text war schon SEHR lang, und ich habe ihn nicht gelesen bzw. das Verfahren nicht nachvollzogen, und das SO weit zu tun, dass man dann sagen könnte, welche Laufzeit es hätte, wäre wohl sehr aufwändig. Ich finde nur, dass das Problem sich (wenn man sich das so bildlich vorstellt, mit dem Baumeln) so einfach aussieht, dass ich denke, dass es auch einfach lösbar sein müßte - natürlich kann man sich da gewaltig täuschen, aber gerade bei Graphenalgorithmen kommt dazu, dass sie
- oft sehr anschaulich sind
- man viele verschiedene kennt, und ggf. auch ihre Laufzeit, und man da ein Bauchgefühl entwickeln kann
- es viele gibt, die sich VIEL schwieriger anhören, und die trotzdem nur linear oder nlogn sind.

Ich habe auch kurz überlegt, ob man es nicht schon durch die Frage beantworten könnte, wann ein Knoten wieder "verlassen" wird, nämlich mit den Besuchsmarkierungen, wie sie z.B. beim Berechnen von Strongly connected component - Wikipedia, the free encyclopedia erstellt werden - aber wie gesagt, bisher hab' ich da noch nicht wirklich näher drüber nachgedacht

 

[SlaterB]

@Ark
> und ich glaube, bei mir läuft's auf den gleichen/ähnlichen Algorithmus hinaus, den SlaterB schon vorgeschlagen hat.

leider zuviel des Lobs, das ist doch die Idee von hans98 aus #7 (Blätter streichen)?

@Marco13:
stimmt, so kann man meinen zitierten Satz lesen, aber war in diesem Fall gar nicht so gemeint,
ich wollte nur meine Aussage, die 'Idee von hans98 aus #7 (Blätter streichen)' wäre in n^2, mal selber korrigieren,
der Satz bezog sich allein auf das weitere Posting (Doppelpunkt), ohne Bezug auf irgendwen

mein langes Postings aus #4 würde ich aus der Geschichte streichen, wenn die Zeit zurückzudrehen wäre,
aber ist jetzt eben so, vielleicht lerne ich was draus

 

[Logaff]

ich glaub ich hatte gerade die blödeste idee

wenn du einen baum hast mit mit

Tree = Node(Tree,Tree)|Null

und du merkst dir den Startknoten....wie wärs einfach den Startknoten auf einen Knoten zu pointern der ca mittig im Baum liegt. Auf welchen genau...keine Ahnung müsste mir da paar Gedanken machen und man kann es sicher auch graphtheoretisch Zeigen.

mfg,
Andreas

 

[Ark]

So, habe gerade mal unter der Dusche den Beweis geführt, dass mein Algorithmus nur höchstens zwei Kandidaten ausspucken wird, grob dürfte der Beweis ungefähr so aussehen:

Angenommen, es wird ein Baum B mit mehr als zwei Knoten eingegeben. Dann hat B mindestens zwei Blätter und Kandidaten sind höchstens zwei Knoten, die keine Blätter sind (und ein solcher Kandidat existiert, da B laut Annahme mehr als zwei Knoten hat), weil der Algorithmus im nächsten Schritt alle Blätter entfernen (bzw. als abgearbeitet markieren) wird. Beim Entfernen aller Blätter aus B entsteht ein neuer Graph B', der wieder ein Baum ist und echt weniger Knoten hat als B. (Den Beweis dazu spare ich mir, die Argumentation ist aber etwa die, dass man mit dem umgekehrten Fall, als "eine Kante und einen Knoten an einen Baum anhängen", wieder einen Baum erzeugt.) B' wird dann wieder eingegeben (als neues B usw.), bis der Baum nur noch höchstens zwei Knoten hat. Dann ist einer der Knoten in B ein Kandidat (oder B ist leer, dann gibt es auch keine Kandidaten), q.e.d.

Damit ist natürlich noch nicht gesagt, dass der Algorithmus überhaupt das macht, was er soll.

So, hier also eine leicht modifizierte Version, die (unter der Annahme, dass alles bisher korrekt war/ist), nur höchstens einen Kandidaten ausspuckt:

BLÄTTER := {Menge aller Blätter}
ABGEARBEITET := {}

solange |BLÄTTER| > 2
	NEUE_BLÄTTER := {}
	für alle b in BLÄTTER:
		ABGEARBEITET := ABGEARBEITET.plus(b)
		n := nachbar(b)
		falls grad(n ohne ABGEARBEITET) <= 1
			NEUE_BLÄTTER := NEUE_BLÄTTER.plus(n)
	BLÄTTER := NEUE_BLÄTTER

falls BLÄTTER = {}
	wurzel := NIL
sonst
	wurzel := [beliebiges Element aus BLÄTTER]

Zwecks Vorstellung der Vorgehensweise: Man entferne alle Blätter des Baumes und erhält daraus einen neuen Baum, aus dem entfernt man wieder alle Blätter usw., bis der Baum nur noch höchstens zwei Knoten enthält. Das sind dann die Kandidaten. Im Prinzip ist der Algorithmus also ein umgekehrter Dijkstra-Algorithmus. Insofern denke ich, dass der Algorithmus passt.

Zur Implementierung: Ich würde die Blätter in einer Liste speichern und über diese Liste mit einem Schreib- und einem Lesezeiger iterieren, die vor jeder Iteration auf den Anfang der Liste zeigen. Wenn die Bedingung "grad(n ohne ABGEARBEITET) <= 1" erfüllt ist, wird mit dem Schreibzeiger in die Liste geschrieben und der Schreibzeiger weiterbewegt. (Dabei kann es vorkommen, dass der gerade mit dem Lesezeiger erfasste Knoten in der Liste überschrieben wird, aber das kann uns ja egal sein.) Auf jeden Fall wird der Lesezeiger immer weiterbewegt (um alle Knoten in der Blätterliste abzuarbeiten, logisch). Wenn so alle Knoten abgearbeitet wurden, gibt der Schreibzeiger die tatsächliche Länge der neuen Liste (für die nächste Iteration) an usw. So braucht man keine eigene NEUE_BLÄTTER-Menge. Durch was man die ABGEARBEITET-Menge ersetzen kann, schrieb ich ja schon weiter oben.


(Mann, ich sehe gerade erst, dass hier wieder richtig was los ist. )

@SlaterB: Hm, stimmt. Blätter streichen, mehr ist es bei mir auch nicht. Insofern hat der TO ja schon den Algorithmus beschrieben.

Ark

 

[Logaff]

Damit ist natürlich noch nicht gesagt, dass der Algorithmus überhaupt das macht, was er soll.

Schreib ein Programm was das Überprüft und du hast ca 50Jahre Theoretische Informatik zerstört (Satz von Rice^^)

 

[hans98]

Hallo alle zusammen, ich glaube wir sind am Ziel mit dem Algorithmus von Ark (wie lange hast du geduscht???) in folgender Form:

BLÄTTER := {Menge aller Blätter}
ABGEARBEITET := {}

wiederhole
	NEUE_BLÄTTER := {}
	für alle b in BLÄTTER:
		ABGEARBEITET := ABGEARBEITET.plus(b)
		falls ABGEARBEITET = ALLE_KNOTEN
			gib b zurück
		n := nachbar_ohne_die_abgearbeiteten(b)
		falls grad_ohne_die_abgearbeiteten(n) <= 1
			NEUE_BLÄTTER := NEUE_BLÄTTER.plus(n)
	BLÄTTER := NEUE_BLÄTTER

Die Schleifenbedingung |BLÄTTER| > 2 ist nicht korrekt, denn eine Kette wie 1--2--3--4--5 hat nur zwei Blätter, aber wir sind noch nicht fertig. n ist nur eindeutig, wenn man die schon abgearbeiteten Knoten nicht mehr als Nachbarn berücksichtigt (Umbenennung nur zur Klarstellung).
Wenn alle Knoten abgearbeitet sind, ist das letzte gefundene Blatt die Wurzel des gesuchten gerichteten Baums.

Die Komplexität ist in O(n), denn jeder Knoten wird genau einmal in die Menge ABGEARBEITET eingefügt. Die Bestimmung von n und die Berechnung des Grades sollte sich in konstanter Zeit durchführen lassen.

 

[Hans98]

Also mein Problem betrachte ich als gelöst - nochmal vielen Dank euch allen.
Sollen wir den Thread als beendet erklären?

 

[Ark]

Die Schleifenbedingung |BLÄTTER| > 2 ist nicht korrekt, denn eine Kette wie 1--2--3--4--5 hat nur zwei Blätter, aber wir sind noch nicht fertig.

Mist, stimmt natürlich, was du sagst! (Ich sollte länger duschen. ) Und dabei habe ich noch selbst in meinem Beweis gesagt: "Angenommen, es wird ein Baum B mit mehr als zwei Knoten eingegeben."

Man müsste also wohl nur noch die Bedingung von "|BLÄTTER| > 2" auf "|KNOTEN| > 2" ändern, wobei |KNOTEN| zu Beginn ermittelt werden kann und fortlaufend aktualisiert werden muss (einfach für jeden abgearbeiteten Knoten 1 abziehen). Oder man verwendet einfach deinen Algorithmus.

… na ja, bin halt ein bisschen doof. Egal. Sorgen wir lieber dafür, dass man auch in Klausuren duschen darf.

Ark