Größt mögliche Summe

MausFan

Hallo liebes Forum,

Ich möchte folgendes tun:
In einem Zahlendreick:

a 
       b  c 
    d   e   f 
  g   h    i   j 
k   l    m   n   o 
...... 
usw.

stehen zufällige Zahlen. Nun soll die größtmögliche Summe gebildet werden, die man nur durch Verbindung mit den unteren nächstliegenden zwei Zahlen bilden darf, bis man dann ganz unten angekommen ist.

Beispiel:

http://www.abload.de/thumb/bild23wr.gif

Nach Internetrecherchen habe ich den A*-Algorithmus entdeckt, der mir als nicht Informatik Student nicht viel nützt, da ich kaum etwas davon verstehe was mir da gezeigt wird. Darum, habe ich mir folgendes überlegt, weis aber nicht wie ich das umsetzen kann:

Gehe alle möglichen Pfade nach unten durch und speichere die erreicht Summe und die Zahlenwerte die dabei zurückgelegt wurden.

Vergleiche welcher Pfad die größte Summe ergibt und gebe diese und den Weg der dorthin führt aus.

Das geht hoffentlich ohne, dass ich die ganzen Inhalte der Textfelder einzeln addieren muss und dabei jede erdenkliche möglichkeit in betracht ziehen muss.

Kann mir bitte jemand erklären wie ich den Pseudocode umsetzen kann und wenn es wirklich nur mit diesem A*-Algorithmus funktioniert mir vlt. erklären, wie ich diesen in meinem Fall anwenden muss und vor allem wie ich ihn dann anwenden kann. Oder vielleicht hat jemand noch eine ganz andere Idee.

Viele Grüsse und vielen Dank für die Hilfe
MausFan

MausFan schrieb:

Das geht hoffentlich ohne, dass ich die ganzen Inhalte der Textfelder einzeln addieren muss und dabei jede erdenkliche möglichkeit in betracht ziehen muss.

Möglicherweise, aber was spricht dagegen, das genauso zu machen, wie es in dem Algorithmus beschrieben wurde. Du kannst das ja auch relativ schön rekursiv formulieren. Und immer wenn du ganz unten angekommen bist, vergleichst du, ob deine neue Summe größer ist als die Schon vorgegebene Summe. Wenn das der Fall ist, speicherst du einfach deinen Pfad als Zeichenkette oder so ab.

SG1

ProgChild schrieb:

MausFan schrieb:

Das geht hoffentlich ohne, dass ich die ganzen Inhalte der Textfelder einzeln addieren muss und dabei jede erdenkliche möglichkeit in betracht ziehen muss.

Möglicherweise, aber was spricht dagegen, das genauso zu machen, wie es in dem Algorithmus beschrieben wurde.

Exponentielle Komplexitaet?

MausFan

Hallo und vielen Dank,

könnte mir jemand bitte die Rekursive Methode in einem Pseudocode etwas näher ausformulieren.

Das wäre echt super.

Vielen Dank
MausFan

Bashar

Man kann das als Graphenproblem betrachten (der Graph ist sogar azyklisch). Jede Zahl ist ein Knoten, es gibt von jedem Knoten, der kein Blatt ist, zwei Kanten zu seinen beiden Nachfolgern. Es geht jetzt darum, zu jedem Blatt den Pfad zu finden, bei dem die Summe der Zahlen am größten ist. Dazu speichert man in jedem Knoten zwei Dinge:

die maximal erreichbare Summe bis dorthin
von welchem Vorgängerknoten man dorthin gekommen ist (diese Information entfällt beim Startknoten a)

Jetzt geht man den Baum ebenenweise durch:
maximal erreichbare Summe bei a ist a
bei b: a+b, bei c: a+c (soweit noch uninteressant)
bei d: a+b+d
bei e: a+b+e oder a+c+e, je nachdem welches größer ist. Entsprechend wird in e vermerkt, ob der Vorgänger b oder c ist, so dass man später den Pfad zurückverfolgen kann.
bei f: a+c+f.
usw., die maximal erreichbare Summe bei einem Knoten x ist immer das Maximum der erreichbaren Summen der beiden Vorgänger von x plus x.

Es ist wichtig zu erkennen, dass, egal was weiter unten noch passiert, sich die maximal erreichbare Summe weiter oben nicht mehr ändern kann. Man kann also unbesorgt Ebene für Ebene abarbeiten und hat irgendwann die maximal erreichbare Summe für jedes Blatt, sowie über die Rückwärtskanten den Pfad, der auf diese Summe führt.

Das ist übrigens eine einfache Variante von Dijkstras Algorithmus zur Bestimmung kürzester Pfade in Graphen.