Hallo, mal etwas Theoretisches, ich hab echt Schwierigkeiten damit.
Gegeben sei ein Graph mit Zyklen: (a, b), (b, a), (b, c), (c, b), (c, d), (d, c), (d, a), (a, d).
Wie generiert man daraus den Suchgraph?
Was ist ein Suchgraph?
Ist ein Suchgraph eine “Abfolge von Schritten welche ein Algorithmus tatsächlich macht”?
Zur Überschrift: Ein Suchbaum kann man natürlich als DAG auffassen, also als gerichteten (wenn man z.B. definiert, dass die Kanten immer von der Wurzel weg “zeigen”) azyklischen (was alle Bäume sind) Graphen.
Zum Beitrag: Keine Ahnung, was du damit sagen willst. Was wird gesucht? Von welchem Algorithmus redest du? Außerdem sollte ein wie auch immer gearteter Suchgraph natürlich keine Zyklen haben (sonst könnte die Suche ziemlich lange dauern). Also bitte etwas ausführlicher, wir können nicht hellsehen.
Das was du als „Suchgraph“ bezeichnet ergibt sich doch von alleine beim Ablauf des Suchalgorithmus. Falls der Algorithmus dabei Kreise nicht beachtet, wird er, wie Landei schon sagte, recht lange laufen.
Wie dieser Graph dann aussieht, hängt natürlich vom Suchalgorithmus ab. Der Baum eines depth first search wird sich deutlich vom Baum eines breadth first search unterscheiden.
Es gibt natürlich noch Haufenweise andere Algorithmen auf Graphen (zum Beispiel um diese einzufärben). Aber da du von Suchen sprachst…
Ist ein Suchgraph eine „Abfolge von Schritten welche ein Algorithmus tatsächlich macht“?
Da ich den Begriff „Suchgraph“ als solchen nicht kenne, kann ich diese Frage nicht beantworten. Aber wenn du damit meinst, welche Knoten nacheinander und auf welchem Weg besucht wurden, zeigt dies die Tätigkeit des Algorithmus imho nur teilweise.
Denn er wird dann nicht die untersuchten, aber verworfenen Nachbarn enthalten (ansonsten wären ggf. wieder lauter Kreise drin).
Da kommt es vermutlich darauf an, wie genau man diesen Suchgraph definiert bzw. wie man ihn im Suchalgorithmus denn erzeugt. Wenn du ihn gerichtet erzeugst und dabei doch alle untersuchten, verworfenen Nachbarn aufnimmst, wird es wenigstens keine gerichteten Kreise geben, wenn auch das Ergebnis „plüschiger“ aussehen wird, als wenn der Suchgraph nur die „wirklich“ besuchten Ecken und deren dabei durchlaufenen Verbindungen enthält.
Mal als Beispiel ein ungerichteter, liegender Diamand (oder auch ein K4 mit fehlender Kante):
b
/ | \
a | d
\ | /
c
G = (E, K) mit
E = (a, b, c, d)
K = ((a, b), (a, c), (b, c), (b, d), (c, d))
Der Suchgraph könnte etwa so aussehen:
S1 = (E1, K1) mit
E1 = (a, b, d, c)
K1 = ((a, b), (b, d), (b, c))
oder auch so:
S2 = (E2, K2) mit
E2 = (a, b, c, d)
K2 = ((a, b), (a, c), (b, d))
Wenn man nun alle anderen besuchten Nachbarn mit aufnimmt:
S1’ = (E1’, K1’) mit
E1’ = (a, b, d, c)
K1’ = ((a, b), (b, d), (d, c), (b, c), (c, d), (c, a), (b, a))
oder so ähnlich, je nach Algorithmus halt.
MIIIIST!!! Hab ich Suchgraph geschrieben? Ich meinte Suchbaum!
Also, damit ich es verstehe, ein (Such-)Algorithmus arbeitet auf einem Problemgraph und kümmert sich auch um Zyklen usw.
Konkrete Schritte, die ein bestimmter Algorithmus macht, kann durch einen Suchbaum dargestellt werden???
Bei einer Tiefensuche wird der Suchbaum tief (u. U.), bei einer Breitensuche wird er breit??
Tiefensuche und Breitensuche generieren unterschiedliche Suchbäume / arbeiten nicht mit dem gleichen Suchbaum?
HINTERGRUND der ganzen Sache ist… Ich hab Algos implementiert für einen bestimmten (mittelgroßen, auf Wikipedia befindlichen) Problemgraph,
gleichzeitig hab ich mir Suchbäume durch die Algos generieren lassen und mit Graph Visualization Software dargestellt (sieht toll aus),
AAAABER, der Suchbaum sei FALSCH!!!
Nehmen wir das:
b
/ | \
a | d
\ | /
c
Ein Suchbaum irgendeines Algos, beginnend mit b, sähe so aus:
→
b – a
b – c
b – d
(a – b)
a – c
(d – b)
d – c
[c – a]
[c – b]
[c – d]
Gilt das auch für Tiefensuche?
Gehört das in ( )-Klammern dazu?
Gehört das in [ ]-Klammern dazu?
Ist ein Suchbaum in jeder Ebene vollständig?
Danke für jeden Hinweis… Es ist bestimmt nicht schwer, aber ich nicht checken 
Wie der konkrete „Suchgraph“ (also der „Weg“, den der Algorithmus im Problemgraphen zurücklegt) aussieht, hängt eben, wie du schon schreibst, vom Algorithmus ab.
Und ja, Tiefensuche und Breitensuche liefern andere Suchgraphen (in diesem Sinne).
Wenn dir jemand sagt, der Suchgraph sei falsch, dann ist das vielleicht ein fester definierterer Begriff als ich das intuitiv dachte, ich kenne den so nicht aus meinem Studium.
*** Edit ***
[QUOTE=CyborgBeta]Nehmen wir das:
b
/ | \
a | d
\ | /
c
Ein Suchbaum irgendeines Algos, beginnend mit b, sähe so aus:
→
b – a
b – c
b – d
(a – b)
a – c
(d – b)
d – c
[c – a]
[c – b]
[c – d]
Gilt das auch für Tiefensuche?
Gehört das in ( )-Klammern dazu?
Gehört das in [ ]-Klammern dazu?
Ist ein Suchbaum in jeder Ebene vollständig?
Danke für jeden Hinweis… Es ist bestimmt nicht schwer, aber ich nicht checken :([/QUOTE]
Wie gesagt, abhängig vom Algorithmus (und der Art und Weise, wie man denn den Suchgraphen bei Abarbeiten des Algorithmus bilden möchte):
Schauen wir uns den Anfang an (sieht nach Breitensuche aus):
b – a
b – c
b – d
Vermutlich hat der Algorithmus die Ecken a, b, c, d als bekannt markiert und die Ecke a als abgearbeitet. (oder die anderen drei als zu untersuchen, wie auch immer).
Nun geht er zur ersten neuen Ecke: Der Ecke a.
Von dieser aus untersucht er alle Nachbarn: a und c
Er bemerkt, dass die Ecke a schon abgearbeitet ist. Untersucht hat er die Verbindung b → a aber dennoch. Hier hängt es nun davon ab, ob (a–b) in dem Suchgrapgh mit abgespeichert wird, ob man an dieser Stelle eben einen solchen Besuch einer bereits bekannten und vollständig abgearbeiteten Ecke mit erwähnt, oder nicht.
Wenn du eine konkrete Definition eines Suchgraphen hast (wenn schon jemand sagt, der sei falsch, muss derjenige zumindest eine haben), wäre das recht interessant für mich.
Ich hoffe, du hast wirklich mit dem Thema zu tun und beschäftigst uns nicht nur. 