Maximale Summe in Zahlendreieck |
| 03.08.2007, 11:45 | GH@NDI | Auf diesen Beitrag antworten » | |||||
| Maximale Summe in Zahlendreieck Ich hoffe mal, dass mein Problem auch in den Bereich der Analysis fällt. 
Das Problem ist schnell und einfach erklärt: Gegeben ist ein Zahlendreieck
und gesucht ist dessen maximaler Summenpfad. Im Beispieldreieck wäre das also der Pfad 3-7-4-9 mit einer Summe von 23. Der eine oder andere wird sich jetzt evtl. an diverse Matheprogrammieraufgaben im Internet erinnert fühlen und damit liegt er vollkommen richtig. Ich knobel nämlich an zweien [1] [2]. Und eben deshalb, weil es um öffentlich zugängliche Aufgaben geht, will ich nicht unbedingt gleich eine komplette Lösung haben (schließlich gehts ja auch ein bisschen darum zu Knobeln). Allerdings wirft mich diese Aufgabe vor ein echtes Problem. Mir fehlt ein grundsätzlicher Ansatz wie man sowas effizient löst. Alles was mir einfallen würde wäre entweder schlicht alles durchzusumieren. Scheitert allerdings an der größe der Dreiecke die im späteren Verlauf auf mich zukommen (50 Zeilen in 4 Sekunden berechnen, 100 Zeilen in einer Minute berechnen). Die andere Idee wäre irgendwas mit Abschätzungen. Jetzt stellt sich nur die Frage, wie kann man in einem solchen Dreieck abschätzungen anstellen? Gibt es da vielleicht irgendwelche Gesetze die in einem solchen Dreieck herschen, anhand derer man eine Abschätzungsregel bestimmen kann? (Schlieslich will ich mich ja nicht verschätzen um einen etwaigen falschen Weg zu gehen) Also hat irgendwer ein paar Tipps oder Hinweise, wie man sowas mathematisch angeht? Mit bestem Dank im vorraus, Sven |
|||||||
| 03.08.2007, 12:04 | kiste | Auf diesen Beitrag antworten » | |||||
Eine Abschätzung fällt mir jetzt nicht ein aber ich würde es dynamisch Programmieren. D.h. du fängst ganz unten an im Dreieck und hast da natürlich als Summe die Elemente. Jetzt gehst du eine Ebene höher und kannst jeweils nach links oder rechts. Die Unterbäume wurden aber bereits berechnen das kannst du also benutzen. Du suchst also den Unterbaum aus der die kleinere Summe hat und addierst diesen Wert mit dem aktuellen Knoten. Dann hast du den Wert für diesen Knoten. Dann gehst du wieder ein Level nach oben solange bis du bei der obersten Zahl bist. Sollte um einiges schneller gehen als alle Wege auszuprobieren
Wie du dann daraus den Weg bekommst kannst du ja einmal selbst überlegen. |
|||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
