Wenn man an der Spitze des folgenden Dreiecks startet und entlang der angrenzenden Zahlen nach unten geht, dann ist der Weg mit der größten Summe 23:
7 4
2 4 6
8 5 9 3
3 + 7 + 4 + 9 = 23
Finde den Weg mit der größten Summe von der Spitze zur Basis des folgenden Dreiecks:
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
Lösung
Möglichkeit 1
Für den Startpunkt gibt es nur eine Möglichkeit. Von dort aus haben wir in jedem Schritt zwei Auswahlmöglichkeiten, daher ist die Anzahl der möglichen Wege 214 = 16384. Das sind nicht zu viele, um sie alle durchzutesten. Die einfachste Lösung ist daher wieder eine brute-force Variante. Dazu könnte man einen rekursiven Algorithmus schreiben, oder einfach 14 for-Schleifen ineinander schachteln.
Matlab-Code:
d =[75 00 00 00 00 00 00 00 00 00 00 00 00 00 00 95 64 00 00 00 00 00 00 00 00 00 00 00 00 00 17 47 82 00 00 00 00 00 00 00 00 00 00 00 00 18 35 87 10 00 00 00 00 00 00 00 00 00 00 00 20 04 82 47 65 00 00 00 00 00 00 00 00 00 00 19 01 23 75 03 34 00 00 00 00 00 00 00 00 00 88 02 77 73 07 63 67 00 00 00 00 00 00 00 00 99 65 04 28 06 16 70 92 00 00 00 00 00 00 00 41 41 26 56 83 40 80 70 33 00 00 00 00 00 00 41 48 72 33 47 32 37 16 94 29 00 00 00 00 00 53 71 44 65 25 43 91 52 97 51 14 00 00 00 00 70 11 33 28 77 73 17 78 39 68 17 57 00 00 00 91 71 52 38 17 14 91 43 58 50 27 29 48 00 00 63 66 04 68 89 53 67 30 73 16 69 87 40 31 00 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23]; maxWeg = 1; aktWeg = d(1,1); for s2 = 1 : 2 for s3 = s2 : s2 + 1 for s4 = s3 : s3 + 1 for s5 = s4 : s4 + 1 for s6 = s5 : s5 + 1 for s7 = s6 : s6 + 1 for s8 = s7 : s7 + 1 for s9 = s8 : s8 + 1 for s10 = s9 : s9 + 1 for s11 = s10 : s10 + 1 for s12 = s11 : s11 + 1 for s13 = s12 : s12 + 1 for s14 = s13 : s13 + 1 for s15 = s14 : s14 + 1 aktWeg = d(1,1) + d(2,s2) + d(3,s3) + d(4,s4) + d(5,s5) + d(6,s6)... + d(7,s7) + d(8,s8) + d(9,s9) + d(10,s10) + d(11,s11) + d(12,s12)... + d(13,s13) + d(14,s14) + d(15,s15); if aktWeg > maxWeg maxWeg = aktWeg; end end end end end end end end end end end end end end end
Ergebnis: 1074
Rechenzeit: 0.005123 Sekunden
Möglichkeit 2
Die andere Möglichkeit besteht darin, logisch an das Problem heranzugehen. Wir betrachten folgendes Beispieldreieck:
In der letzten Zeile gibt es jeweils keine Entscheidungsmöglichkeit mehr. Wenn wir dort angekommen sind, steht fest, wie lang der Weg ist. In der vorletzten Zeile gibt es jeweils zwei Möglichkeiten. Der Algorithmus soll jeweils die bessere benutzen. Wir können also zu jedem Element der vorletzten Zeile jeweils das bessere der beiden möglichen Nachfolger addieren:
Daraus wird:
Wir fahren fort mit der dritten Zeile:
Daraus wird:
Die zweite Zeile:
Und zuletzt die erste Zeile:
Das Ergebnis ist 27.
Matlab-Code:
d = zeros(15); d(1,1) = 75; d(2,1:2) = [95 64]; d(3,1:3) = [17 47 82]; d(4,1:4) = [18 35 87 10]; d(5,1:5) = [20 04 82 47 65]; d(6,1:6) = [19 01 23 75 03 34]; d(7,1:7) = [88 02 77 73 07 63 67]; d(8,1:8) = [99 65 04 28 06 16 70 92]; d(9,1:9) = [41 41 26 56 83 40 80 70 33]; d(10,1:10) = [41 48 72 33 47 32 37 16 94 29]; d(11,1:11) = [53 71 44 65 25 43 91 52 97 51 14]; d(12,1:12) = [70 11 33 28 77 73 17 78 39 68 17 57]; d(13,1:13) = [91 71 52 38 17 14 91 43 58 50 27 29 48]; d(14,1:14) = [63 66 04 68 89 53 67 30 73 16 69 87 40 31]; d(15,1:15) = [04 62 98 27 23 09 70 98 73 93 38 53 60 04 23]; opt = d; for k = 14 : -1 : 1 for p = 1 : k opt(k, p) = opt(k, p) + max(opt(k + 1, p), opt(k + 1, p + 1)); end end disp(opt(1,1))
Rechenzeit: 0.000105 Sekunden, also Faktor 50 schneller als die erste Version.