größst 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

Ich habe mir das nicht angesehen, aber reicht es nicht für jede Zeile den größtmöglichen Wer zu bestimmen?

1 -> 1
4 5 -> 5
1 2 3 -> 3
========= 9

???

int Summe = 0;
for ( int i = 0; i < ANZAHL_ZEILEN; i++ )
{
 Summe += GroessterWert( WERTE_IN_ZEILE[i] );
}

std::cout << "Summe: " << Summe << std::endl;

Christoph

Das sieht doch sehr nach einem Project-Euler-Problem aus. Ich bitte deswegen darum, keinen fertigen Code zu posten, denn das wäre unfair denen gegenüber, die diese Aufgabe noch selbst lösen wollen.

Diejenigen sollten am besten auch nicht in meinem Posting weiterlesen.

@MausFan:
Die Idee hinter der Lösung ist /viel/ einfacher als A*. Dynamic Programming ist ein Stichwort. Du darfst dich nicht darauf fixieren den besten Weg von oben nach unten finden zu wollen.

MausFan

Hallo Christoph,

ich hätte nicht gedacht, dass es diese Fragestellung auch im Internet gibt. Allerdings geht es mir nicht um die Lösung des Problems aus Ehrgeiz, sondern weil ich es für meinen Mathematikunterricht brauche. Meine Schüler (Klasse 6) sollen sich mit einem Zahlendreieck von höchstens 8 Zeilen beschäftigen und dort die größte Summe finden. Und ich hätte gern ein Programm mit denen ich Sie einfach etwas arbeiten lassen kann.

Ich habe hier http://olympiads.win.tue.nl/ioi/ioi94/contest/day1prb1/solution.html einige Programme gefunden, kann Sie aber leider nicht lesen, weil ich mit der verwendeten Programmiersprache nicht vertraut bin. Könnte mir bitte jemand das geeignetste der 4 Programme in einem Pseudocode oder c++ code übersetzen, oder mir in pseudocode beschreiben wie ich das programmieren soll.

Zu Dynamic Programming habe ich mir einiges durchgelsen, bin aber nicht so erfahren in der Programmierung, dass ich das anwenden könnte.

Für Hilfe wäre ich sehr dankbar

Viele Grüsse
MausFan

Christoph

Der Trick ist, den Weg nicht von oben nach unten, sondern genau andersherum zu suchen.

Nimm z.B. das Dreieck:

Nun beginnst du unten. Dort gibt es vier mögliche Startpunkte. Das sind unvollständige Wege, die nur aus einer Zahl bestehen. Im nächsten Schritt erweiterst du diese Wege um jeweils eine Zahl nach oben. Du schaust dir dazu in der vorletzten Zeile das erste Element an, die 4. Zur 4 kannst du über zwei Wege kommen (von unten gesehen): Über die 5 oder über die 2. Weil 5+4 größer ist als 2+4, nimmst du natürlich den Weg über die 5. Den Weg über die 2 zur 4 kannst du jetzt bereits ignorieren, weil der sicher schlechter ist.

Dieses Verfahren wendest du noch für die 1 und für die 5 aus der vorletzten Zeile an. Dann gehst du eine Zeile weiter hoch, und so weiter, bis du bei der obersten Zeile angekommen bist. Weil dort nur eine einzige Zahl steht, bleibt nur ein Weg übrig. Aus der Konstruktion folgt, dass das der Weg mit der größten Summe sein muss.

Black Shadow

@Christoph: bist du dir da sicher?

1
    2    2
  100  3   4
 4   2   7   9
1  1   1   9   5

Du würdest doch jetzt über die 9-9 gehen oder hab ich dich jetzt falsch verstanden? Dann würdest du die 100 nie erreichen.
Außerdem ist mir unklar, warum es, wenn man unten beginnt, erstmal 5 wege geben sollte. bei dir zähle ich 6 wege zur zweit untersten zeile.

Christoph

Black Shadow schrieb:

@Christoph: bist du dir da sicher?
1
    2    2
  100  3   4
 4   2   7   9
1  1   1   9   5
Du würdest doch jetzt über die 9-9 gehen oder hab ich dich jetzt falsch verstanden? Dann würdest du die 100 nie erreichen.

Ich betrachte die Wege parallel. Wenn der Algorithmus die zweite Zeile von unten abgearbeitet hat, sind noch vier Wege übrig (von links nach rechts und unten nach oben): 1-4, 1-2, 9-7, 9-9.
Im nächsten Schritt bleiben die folgenden Wege übrig: 1-4-100, 9-7-3, 9-9-4.
Im nächsten Schritt: 1-4-100-2, 9-9-4-2
Im letzten Schritt: 1-4-100-2-1

Ganz vollständig war meine Beschreibung in dem Punkt nicht: Man muss die Summe der bisherigen Wege betrachten um festzustellen, welchen man weiterführt. Der große Vorteil dieses Algorithmus ist aber, dass die getroffenen Entscheidungen nicht zu einer Vervielfachung der Wege führen, sondern zu einer Verringerung. Dafür beginnt man anders als beim direkten Wegsuchen nicht mit einem Startpunkt, sondern mit so vielen wie Zahlen in der untersten Reihe stehen.

Außerdem ist mir unklar, warum es, wenn man unten beginnt, erstmal 5 wege geben sollte. bei dir zähle ich 6 wege zur zweit untersten zeile.

Ist jetzt hoffentlich klarer formuliert, ich hab den Satz verbessert.

Bashar

*zulangsam*

Black Shadow

Danke, jetzt isses klar

MausFan

Vielen vielen Dank,

mir ist jetzt klar, was ich machen muss. Mir fehlt jetzt nur noch das "WIE". Da ich nicht so erfahren in der Programmierung bin, wäre ich sehr erfreut, wenn mir jemand einen pseudocode schreiben könnte, wo ich dann sehe, wie man das Programmieren muss.

Tut mir wirklich leid, dass ich euch hier so schinde.

Viele Grüsse und nochmals Danke
MausFan

Ben04

Nummerier die Stellen im Dreieck:

So nun kannst du das ganze ohne weiteres in einem Array speichern, du nimmst die Zahlen oben als Index. Im Array speicherst du die größte Summe die man von dort an bilden kann und den Index des nächsten Elements drunter.

Für das Beispiel :

würdest du also speichern:

2/14
      3/11    5/13
   6/9    8/4     8/8
?/5   ?/2     ?/3    ?/1

Mit Index/Wert. Da man auf der untersten Ebene nicht mehr runter geht gibt es da auch keinen sinnvollen Wert.

So um die beste Summe auszulesen fängst du an der Spitze an. Den Wert 14 hast du eh schon. Um die Summanden zu finden folgst du einfach den Indexen. Also 0->2->5->8 und da daraus kannst du die maximale Summe herleiten : 14 = 1 + 5 + 5 + 3

So nun fragt sich nur noch wie dieses Array gefüllt wird. Dafür läuft man es einfach von hinten nach vorne durch. Auf der untersten Ebene ist es einfach : Mit nur einem Term lässt sich nur eine Summe bilden welche dann natürlich auch größte ist. Auf den höheren Ebenen ist der Summenwert gleich

summe = Wert im Dreieck + max(Summe im 1sten Kind, Summe im 2ten Kind)

So nun fragt sich nur noch wie man die Indexe der beiden Kinder feststellt. Dies sollte aber für einen Mathematiker nicht schwer sein falls er weiß, dass (n^2+n)/2 den Index des ersten Elements der nthen Ebene darstellt. Also

Dreieck | Ebene | Index des ersten Elements
   [b]0[/b]      0       (0^2+0)/2 = [b]0[/b]
  [b]1[/b] 2     1       (1^2+1)/2 = [b]1[/b]
 [b]3[/b] 4 5    2       (2^2+2)/2 = [b]3[/b]
[b]6[/b] 7 8 9   3       (3^2+3)/2 = [b]6[/b]