Baum - Algorithmus

Computer: Software & Programmierung Programmierung allgemein
#1

Hi allerseits!

Mich „quält“ folgendes Problem:
Gegeben sei ein Produkt, das aus beliebig vielen Teilen besteht, von denen jeder wiederum selbst aus beliebig vielen Teilen bestehen kann, von denen…(und so weiter und so fort), oder die nicht weiter zerlegbar sind.
Das Ganze bildet also eine Art „Baum“ ausgehend vom ganzen Produkt, jeder Teil bildet eine weiter Verästelung.

Ich suche nun einen Algorithmus, der diesen Baum durchsucht, und alle möglichen Zerlegestufen ausgibt (von „Ganzes Produkt“ über „Teil A ganz lassen, Teil B zerlegen in Teil C und D,…“ bis hin zur Aufspaltung in alle Teile). Außerdem sollte dieser Algorithmus unabhängig von der Anzahl der Teile und Ebenen sein.

Gibt es soetwas und wenn ja wo (am besten in Python oder Pseudocode)?

Danke und LG

Stuffi

#2

Hi.

ich bin mir nicht ganz sicher, was Du meinst…
Aber wenn es das ist wie ich es meine wäre es vergleichbar mit einem Navigationsmenü vergleichbar mit der Ordnerstruktur im Explorer, oder?
Wenn dem so ist dann bräuchtest Du eine rekursive Funktion, die die unterste Ebene aufruft und bei jedem Element nachschaut, ob es für dieses Element (also auf dieser neuen Ebene) untereinträge gibt.
In PHP würde man das normalerweise so lösen, dass es eine id und eine ref_id gibt.
Auf unterster Ebene ist die ref_id = 0.
Diese wird dann aufgerufen und durchsucht
function rekursiv($id)
(select * from bla where ref_id=0)
while result…
rekursiv($result[id])

und dann halt mit rekursiv(0) aufgerufen…
Hoffe das hilft Dir weiter?

#3

Diese wird dann aufgerufen und durchsucht
function rekursiv($id)
(select * from bla where ref_id=0)
while result…
rekursiv($result[id])

Ja, an soetwas habe ich auch gedacht, aber damit bekomme ich nicht alle Möglichkeiten, da ja auch die Möglichkeit besteht, daß ein Teil nicht zerlegt wird, obwohl es möglich wäre.

Ein Beispiel:
Ein Produkt besteht aus den Teilen A und B.
Teil A besteht aus C und D, Teil B besteht aus E und F.

Die möglichen Teile nach der Zerlegung wären:

  1. Ganzes Produkt
  2. A + B
  3. (C + D) + B
  4. A + (E + F)
  5. (C + D) + (E + F)
    (die Klammern haben keine praktische Bedeutung, sondern sollen nur zeigen, daß zB C+D vorher A waren)

Mit dieser Rekursion käme ich AFAIK nur auf Punkt 5) - die Zerlegung in die kleinsten möglichen Einheiten. Ich benötige aber alle möglichen Kombinationen.

Danke und LG
Stuffi

#4

bin mir nicht sicher, ob ichs jetzt richtig im Kopf rekapituliert hab (jedenfalls verstehe ich das Problem jetzt)…

wie wäre es, wenn Du einfach nachdem (oder auch bevor) Du die rekursive Funktion ansteuerst einfach nochmal schaust, ob Du das Ergebnis zerlegen kannst…

in dem Fall wäre dann die Bezeichnung die „id“ und die Zerlegbarkeit die „ref_id“.
Auf dem bisherigem Weg schaust Du nach, aus welchen Teilen etwas besteht, so kriegst Du schon mal Deine 1. bis 4. raus.
Wenn Du dann einfach noch die Ergebnisse auf weitere zerlegbarkeit testest… (hier brech ich mal ab, wegen geistiger verwirrung) *g*

nochmal von vorne…
der Unterschied bei Dir wäre ja quasi, dass Du keine eindeutigen id’s hast… Wenn Du jetzt eine Struktur hast wie
„id“ „ref_id“
ges A+B
A C+D
B E+F
dann kannst Du ja eigentlich doch die Resultate weiter zerlegen…
Allerdings wird es wohl relativ schwer das richtig schön umzusetzen…
am leichtesten wohl mit mehreren Tabellenspalten der Bezeichnung „ref_id“
*grübel*

ich glaub ich lass das jetzt einfach mal so stehen *ggg*

#5

Hi Stuffi!

hab leider erst heute deine Anfrage gesehen. Das Ziel ist mir zwar noch nicht ganz klar, aber zum „halten“ der Daten könnte ich mir sehr gut xml vorstellen. Darauf was xslt und das Ganze sollte laufen. Knoten selektieren und Eltern, Geschwister etc. ausgeben. Du hast zwar andere Sprachen genannt, die ich nicht kenne, aber vielleicht können die xml und xslt behandeln.

Bei Interesse schreib mal genauer was du vorhast!

mfg

Dirk