# Dynamische Programmierung, komme nicht weiter....



## ModellbahnerTT (8. Jun 2009)

Hallo zusammen,

ich hab mir sogar ein Buch gekauft, welches mir aber bei diesem Problem leider nicht weiter helfen konnte.

Die Aufgabe lautet, man solle eine Matrix erstellen by radom und dann soll Zeile jeweils die höchste Zahl mit der möglichst höchsten Zahl vom nächsten Ergebnis addiert werden. 

Aber jetzt kommt der haken: 

Ein Punkt (i, j ) hat nur drei mögliche Nachfolger (i + 1, j − 1), (i + 1, j ), (i + 1, j + 1). 

Beispiel: Für die Matrix: 
7 2 2 
2 5 6 
4 1 0 
1 5 0 
lautet der optimale Weg (1,1), (2,2), (3,1), (4,2) mit der maximalen Summe 7 + 5 + 4 + 5 = 21. 

Grad kommt mir dann eine kleine Idee:
Ich nehme von der ersten Matrix das höchste Element und dann versuche ich in seinen drei Möglichkeiten das nächst höchste davon zu nehmen.
Jetzt schau ich aber in der 2. Zeile, was dort das höchste wäre und was davon der vorherigste höchste vorgänger und je nachdem welcher es ist, entscheide ich mich dann dafür.
Wäre schonmal ein Anfang.

Für alle Fälle schon mal mein jetziger Code:


```
class Matrix{
int n;
int m;
    void eingabe (int n, int m) {
    this.n=n;
    this.m=m;
    int array[][] = new int [n][m];
    for(int i=0;i<n;i++)
    {
       for(int j=0;j<m;j++)
       {
           array[i][j]=(int)(50*Math.random());
        }
    }
      
    System.out.println("Matrix erstellt:");     
    System.out.println("Zeilen  (m)= " + array.length);
    System.out.println("Spalten (n) = " + array[1].length);
    ausgabe(array);
  }
    
   void ausgabe(int[][] array) {
     int rowSize = array.length;
     int columnSize = array[0].length;
     for(int i = 0; i <= n-1; i++) {
       System.out.print("[");
       for(int j = 0; j <= m-1; j++) {
         System.out.print(" " + array[i][j]);
       }
       System.out.println(" ]");
     }
     System.out.println();
   }
}
```

Besten Dank schonmal
NACHTRAG: Ein Fehler von mir, man soll nicht Backtraking sondern Dynamische Programmierung verwenden.
Zitat vom Tutor:"...berechnet erst eine Teillösungen,
und baut diese dann Stück für Stück zu einer Gesamtlösung zusammen,
quasi "bottom-up"."


----------



## Jay1980 (8. Jun 2009)

Servus,

ich kann dir leider (noch) nicht helfen, wäre aber dankbar wenn du mir Bescheid gibst wenn es mal klappt. Ich wollte zwei Algorithmen implementieren wo ich das ebenfalls brauche (Smith-Waterman, Needleman-Wunsch). Vielleicht findest du unter den Stichworten eine Lösung.

Viel Erfolg.


----------



## Landei (9. Jun 2009)

Dein beschriebener Algorithmus funktioniert so nicht. Nimm die Matrix:

211
217
217
211

Dann würdest du die Folge 2,2,2,2 = 8 liefern, während der optimale Weg 1,7,7,1 = 16 wäre.


----------



## Marco13 (9. Jun 2009)

Geht es dabei um Sequence Alignment (Levenshtein-Distanz o.ä.) ?


----------



## ModellbahnerTT (9. Jun 2009)

Ein Fehler von mir, man soll nicht Backtraking sondern Dynamische Programmierung verwenden.
Zitat vom Tutor:"...berechnet erst eine Teillösungen,
und baut diese dann Stück für Stück zu einer Gesamtlösung zusammen,
quasi "bottom-up"."


----------



## Marco13 (9. Jun 2009)

Ah, dann schon eher. Stichworte wie "Hirschberg" und "Viterbi" sagen dir was?


----------



## ModellbahnerTT (9. Jun 2009)

leider nein...


----------



## programmar (9. Jun 2009)

müsste es nicht 
217
211
211
217
sein?


----------



## bygones (9. Jun 2009)

Marco13 hat gesagt.:


> Ah, dann schon eher. Stichworte wie "Hirschberg" und "Viterbi" sagen dir was?


entweder hat mich mein Studium zu sehr beschraenkt oder es gibt mehrere Algorithmen dieser Namen oder meine Dummheit schafft es nicht sie zu transferieren oder du wirfst hier mal n paar Schlagworte einfach so rein...

Viterbi kenn ich nur im Kontext von Hidden Markov Models... wo sind hier die versteckten Zustaende, wo sind hast du Emissionswahrscheinlichkeiten etc... 
Moeglich gibt es hier eine transformierung auf das gegebene Problem, aber fuers erste halte ich das a) falsch und b) oversized.... klaer mich bitte auf.

Hirschberg ist ein Alignment Algorithmus - gut den koennte man recht biegen um das zu loesen...


----------



## Landei (9. Jun 2009)

Dynamisch hin oder her, ich würde es so machen:

7 2 2
2 5 6
4 1 0
1 5 0 

Maximum der Anfangsmatrize ermitteln (hier: 7), alle Werte davon abziehen:
0 5 5
5 2 1
3 6 7
6 2 7

Das Ganze als Graph interpretieren, Start- und Endknoten einfügen:

```
S
 /|\
0 5 5
|X|X|
5 2 1
|X|X|
3 6 7
|X|X|
6 2 7
\ | /
  E
```

Dann einfach einen Algorithmus für den "kürzesten" Weg laufen lassen.


----------



## bygones (9. Jun 2009)

Landei... und rechne nun mal die Laufzeit deiner Loesung aus (maximum ermitteln, werte subtrahieren, Graph bauen, kuerzesten Weg finden) - das will man nicht im grossen Stil

und daher kommt die Idee des dyn. programmierens - damit schaffst du eine akzeptable laufzeit


----------



## ModellbahnerTT (9. Jun 2009)

zu beachten gilt noch:
mxn kann bel. gewählt werden und leider nicht immer so wie in diesem Muster hier.


----------



## Marco13 (9. Jun 2009)

deathbyaclown hat gesagt.:


> entweder hat mich mein Studium zu sehr beschraenkt oder es gibt mehrere Algorithmen dieser Namen oder meine Dummheit schafft es nicht sie zu transferieren oder du wirfst hier mal n paar Schlagworte einfach so rein...



Ja, Viterbi war falsch - hatte den nur im Zusammenhang mit Hirschberg im Kopf, weil man das "Hirschbarg-Schema" AFAIR auch auf den Viterbi anwenden kann, aber was ich eigentlich meinte war natürlich Needleman-Wunsch 

@ModellbahnerTT: Hast du schon mal versucht, den Needleman-Wunsch-Algorithmus ? Wikipedia dafür anzuwenden?


----------



## ModellbahnerTT (9. Jun 2009)

OK, ich weiß jetzt nicht ob das dp ist und wahrscheinlich ist es auch nicht optimal aber hier eine Lösungsmöglichkeit:

Allerdings hat sich irgendwo ein Fehler eingeschlichen, weiß aber nicht wo, die Koordinaten und die Endsumme sind teilweise nicht optimal:


```
public class Matrix
    {
        int n,m;
        int i,j;
        int MatrixArray[][];
        int xKoordinate[];

        int xBestKoordinate[];
        
        int current;
        int summe;
        int besteSumme;
        int richtung;
        int help;
        boolean dleft,dright;
//---------------------------------------------------------------------------
        void ErstelleMatrix(int m,int n)
        {
            this.n=n;
            this.m=m;
            xKoordinate= new int[m];
            xBestKoordinate= new int[m];
            
            dleft=false;
            dright=false;
            
            MatrixArray = new int[n][m];
            
            for(i=0;i<n;i++)
            {
                for(j=0;j<m;j++)
                    {
                        MatrixArray[i][j]=(int)(60*Math.random());
                    }
                }   
                i=0;
                j=0;
            }
//---------------------------------------------------------------------------      
            void MatrixAusgabe()
            {
                int k,l;
                for(k=0;k<m;k++)
                {
                    System.out.println();
                    for(l=0;l<n;l++)
                        {
                            System.out.print(MatrixArray[l][k]);
                            System.out.print("  ");
                        }
                    }
                }
//---------------------------------------------------------------------------
   
 void WegSuche()
    {
     besteSumme=0;
     for(i=0;i<n;i++)
        {
         help=i;
         xKoordinate[i]=i;

         while(j<m-1)
            {
              current=MatrixArray[i][j];
              PruefeWeg();
              summe=current+MaxWert();
              dleft=false;
              dright=false;
              WegSpeichern();
              
            }

            
              if (summe > besteSumme)
            {
                for(int p=0;p<xKoordinate.length;p++)
                {
                   xBestKoordinate[p]=xKoordinate[p];
                   xKoordinate[p]=0;
                 }
                
                besteSumme=summe;
                
            }
                summe=0;
                i=help;
                j=0;
        }
        BesteAusgabe();
           
    }
            
              
              
              
                
 void PruefeWeg()
 {
     
     if(i==0)
     {
        dleft=false;
        dright=true;
     }
     
     if(i==n)
     {
         dleft=true;
         dright=false;
     }
    
 }
 
int MaxWert()
 {
     int wert_left=0;
     int wert_down=0;
     int wert_right=0;
     int max;
     
     
     if(dleft==true) wert_left=MatrixArray[i-1][j+1];
     if(dright==true) wert_right=MatrixArray[i+1][j+1];
     wert_down=MatrixArray[i][j+1];
     
     max=wert_down; richtung=0;
 
     if ((dleft==true)&(wert_left>max)) 
     {
         max=wert_left;richtung=-1;
        }
     if ((dright==true)&(wert_right>max)) 
     {
         max=wert_right;richtung=1;
        }
     
        
        
 return max;
}

    void WegSpeichern()
    {
        xKoordinate[j]=i;
        i=i+richtung;
        j++;
    } 
    
 void BesteAusgabe()
    {
        System.out.println("");
        System.out.println("Beste Summe:"+"   "+besteSumme);
        for(int p=0;p<m;p++)
        {
            System.out.println("Koordinate: "+"("+p+"|"+xKoordinate[p]+")");
        }
    }
}
    
   

        
//---------------------------------------------------------------------------
```


----------



## Marco13 (10. Jun 2009)

Hm. So ganz hab' ich das jetzt nicht sofort nachvollziehen können ... mit dem dleft und dright... aber sieht grundsätzlich eigentlich nicht sooo falsch aus (abgesehen davon, dass es ihn bei nicht-Quardatischen Matrizen anscheinend raushaut).

Ich versuch' das gerade mal durchzudenken (ignorier' mich einfach  )
Gegeben

```
7 2 2
2 5 6
4 1 0
1 5 0
```
In der "Summen-Matrix" kann in Zeile 2 stehen:
- In Spalte 1 eine 9, wenn man von oben kommt
- In Spalte 1 eine 4, wenn man von oben rechts kommt

- In Spalte 2 eine 12, wenn man von oben links kommt XXX
- In Spalte 2 eine 7, wenn man von oben kommt
- In Spalte 2 eine 7, wenn man von oben rechts kommt

- In Spalte 3 eine 8, wenn man von oben links kommt
- In Spalte 3 eine 8, wenn man von oben kommt

D.h. die "Summen-Matrix" sieht bis dahin so aus

```
7  2  2
 9 12  8
 4  1  0
 1  5  0
```

In der nächsten Zeile kann
- In Spalte 1 eine 13, wenn man von oben kommt
- In Spalte 1 eine 16, wenn man von oben rechts kommt XXX

- In Spalte 2 eine 10, wenn man von oben links kommt
- In Spalte 2 eine 13, wenn man von oben kommt
- In Spalte 2 eine 9, wenn man von oben rechts kommt

- In Spalte 3 eine 12, wenn man von oben links kommt
- In Spalte 3 eine 8, wenn man von oben kommt

D.h. die "Summen-Matrix" sieht bis dahin so aus

```
7  2  2
 9 12  8
16 13 12
 1  5  0
```

In der nächsten Zeile kann
- In Spalte 1 eine 17, wenn man von oben kommt
- In Spalte 1 eine 14, wenn man von oben rechts kommt

- In Spalte 2 eine 21, wenn man von oben links kommt XXX
- In Spalte 2 eine 18, wenn man von oben kommt
- In Spalte 2 eine 17, wenn man von oben rechts kommt

- In Spalte 3 eine 13, wenn man von oben links kommt
- In Spalte 3 eine 12, wenn man von oben kommt

D.h. die "Summen-Matrix" sieht bis dahin so aus

```
7  2  2
 9 12  8
16 13 12
17 21 13
```

Wenn man dann von der höchsten Zahl der letzten Zeile aus die Schritte rückwärts läuft, die man dort hin gegangen ist (d.h. die mit XXX markierten) hat man den Weg...

Das ist ja grob das, was du hast, oder? (Ja, jetzt hör' auf, mich zu ignorieren  )

Bis morgn noch ein Tipp:Mit 
System.out.print(String.format("%3d", MatrixArray[l][k]));
kann man die Matrix schön "ausgerichtet" ausgeben, und mit

```
import java.util.Random;

            Random random = new Random(0);
            for(i=0;i<n;i++)
            {
                for(j=0;j<m;j++)
                    {
                        MatrixArray[i][j]=random.nextInt(60);
                    }
```
Bekommt man immer die gleichen Zufallszahlen - das ist immer besser zum Fehlersuchen. Um es mit anderen Zufallszahlen zu testen, kann man dann "new Random(1)", "new Random(2)" usw. verwenden - und wenn alles funktioniert, schließlich "new Random()"


----------



## Landei (10. Jun 2009)

Hier meine Lösung, Performance ist ganz gut:


```
import java.util.*;

public class MaximumPath {
  private static Random random = new Random();
  
  private static int[][] randomMatrix(int width, int height, int maxVal) {
     int[][] result = new int[width][height];
     for(int x = 0; x < width; x++) {
       for(int y = 0; y < height; y++) {
          result[x][y] = random.nextInt(maxVal);
       }
     }
     return result;
  }
  
  private static Path[] calculate(int[][] m, int y) {
    Path[] result = new Path[m.length];
    if (y == 0) {
      for (int x = 0; x < m.length; x++) {
        List<Integer> list = new ArrayList<Integer>();
        list.add(x);
        result[x] = new Path(list, m[x][y]);
      }
    } else {
      Path[] previous = calculate(m, y-1);
      for (int x = 0; x < m.length; x++) {
        Path maxPath = new Path(null,0);
        List<Integer> pred = new ArrayList<Integer>();
        pred.add(x);
        if(x > 0) { pred.add(x-1); }
        if(x < m.length - 1) { pred.add(x+1); }
        for(int px : pred) {
          Path path = previous[px];
          if (path.length > maxPath.length) {
            maxPath = path;
          }  
        }
        List<Integer> newList = new ArrayList<Integer>(maxPath.path);
        newList.add(x);
        result[x] = new Path(newList, maxPath.length + m[x][y]);
      }
    }
    return result;
  }
  
  
  public static void main(String... args) {
    int[][] m = randomMatrix(5,10,20);
    for(int y = 0; y < m[0].length; y++) {
      for(int x = 0; x < m.length; x++) {
        System.out.printf("%02d ",m[x][y]);
      }
      System.out.println();
    }
    Path[] paths = calculate(m, m[0].length - 1);
    Path maxPath = new Path(null,0);
    for(Path path : paths) {
       if (path.length > maxPath.length) {
         maxPath = path;
       }  
    }
    System.out.println("\nmaximale Länge " + maxPath.length);
    System.out.println("maximaler Pfad " + maxPath.path);
  }
  
  private static class Path {
    private List<Integer> path;
    private int length;
    private Path(List<Integer> path, int length) {
      this.path = path;
      this.length = length;
    }
  }
}
```

Ich bin auch ziemlich sicher, dass es wirklich immer den längsten Pfad findet.


----------

