Blog

018 – Weg mit maximaler Summe in Dreieck

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:

3
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:

75
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:

\begin{array}{*{20}{c}} 5 \\ {\begin{array}{*{20}{c}} 2 & 4 \\ \end{array} } \\ {\begin{array}{*{20}{c}} 7 & 7 & 2 \\ \end{array} } \\ {\begin{array}{*{20}{c}} 8 & 5 & 4 & 1 \\ \end{array} } \\ {\begin{array}{*{20}{c}} 1 & 4 & 2 & 7 & 5 \\ \end{array} } \\ \end{array}

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:

\begin{array}{*{20}{c}} 5 \\ {\begin{array}{*{20}{c}} 2 & 4 \\ \end{array} } \\ {\begin{array}{*{20}{c}} 7 & 7 & 2 \\ \end{array} } \\ {\begin{array}{*{20}{c}} {8 + \max \left\{ {1,4} \right\}} & {5 + \max \left\{ {4,2} \right\}} & {4 + \max \left\{ {2,7} \right\}} & {1 + \max \left\{ {7,5} \right\}} \\ \end{array} } \\ {\begin{array}{*{20}{c}} 1 & 4 & 2 & 7 & 5 \\ \end{array} } \\ \end{array}

Daraus wird:

\begin{array}{*{20}{c}} 5 \\ {\begin{array}{*{20}{c}} 2 & 4 \\ \end{array} } \\ {\begin{array}{*{20}{c}} 7 & 7 & 2 \\ \end{array} } \\ {\begin{array}{*{20}{c}} {12} & 9 & {11} & 8 \\ \end{array} } \\ {\begin{array}{*{20}{c}} 1 & 4 & 2 & 7 & 5 \\ \end{array} } \\ \end{array}

Wir fahren fort mit der dritten Zeile:

\begin{array}{*{20}{c}} 5 \\ {\begin{array}{*{20}{c}} 2 & 4 \\ \end{array} } \\ {\begin{array}{*{20}{c}} {7 + \max \left\{ {12,9} \right\}} & {7 + \max \left\{ {9,11} \right\}} & {2 + \max \left\{ {11,8} \right\}} \\ \end{array} } \\ {\begin{array}{*{20}{c}} {12} & 9 & {11} & 8 \\ \end{array} } \\ {\begin{array}{*{20}{c}} 1 & 4 & 2 & 7 & 5 \\ \end{array} } \\ \end{array}

Daraus wird:

\begin{array}{*{20}{c}} 5 \\ {\begin{array}{*{20}{c}} 2 & 4 \\ \end{array} } \\ {\begin{array}{*{20}{c}} {19} & {18} & {13} \\ \end{array} } \\ {\begin{array}{*{20}{c}} {12} & 9 & {11} & 8 \\ \end{array} } \\ {\begin{array}{*{20}{c}} 1 & 4 & 2 & 7 & 5 \\ \end{array} } \\ \end{array}

Die zweite Zeile:

\begin{array}{*{20}{c}} 5 \\ {\begin{array}{*{20}{c}} {2 + \max \left\{ {19,18} \right\}} & {4 + \max \left\{ {18,13} \right\}} \\ \end{array} } \\ {\begin{array}{*{20}{c}} {19} & {18} & {13} \\ \end{array} } \\ {\begin{array}{*{20}{c}} {12} & 9 & {11} & 8 \\ \end{array} } \\ {\begin{array}{*{20}{c}} 1 & 4 & 2 & 7 & 5 \\ \end{array} } \\ \end{array} \quad \Rightarrow \quad \begin{array}{*{20}{c}} 5 \\ {\begin{array}{*{20}{c}} {21} & {22} \\ \end{array} } \\ {\begin{array}{*{20}{c}} {19} & {18} & {13} \\ \end{array} } \\ {\begin{array}{*{20}{c}} {12} & 9 & {11} & 8 \\ \end{array} } \\ {\begin{array}{*{20}{c}} 1 & 4 & 2 & 7 & 5 \\ \end{array} } \\ \end{array}

Und zuletzt die erste Zeile:

\begin{array}{*{20}{c}} {5 + \max \left\{ {21,22} \right\}} \\ {\begin{array}{*{20}{c}} {21} & {22} \\ \end{array} } \\ {\begin{array}{*{20}{c}} {19} & {18} & {13} \\ \end{array} } \\ {\begin{array}{*{20}{c}} {12} & 9 & {11} & 8 \\ \end{array} } \\ {\begin{array}{*{20}{c}} 1 & 4 & 2 & 7 & 5 \\ \end{array} } \\ \end{array} \quad \Rightarrow \quad \begin{array}{*{20}{c}} {27} \\ {\begin{array}{*{20}{c}} {21} & {22} \\ \end{array} } \\ {\begin{array}{*{20}{c}} {19} & {18} & {13} \\ \end{array} } \\ {\begin{array}{*{20}{c}} {12} & 9 & {11} & 8 \\ \end{array} } \\ {\begin{array}{*{20}{c}} 1 & 4 & 2 & 7 & 5 \\ \end{array} } \\ \end{array}

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.

Leave a Reply

Close Menu