Dynamische Programmierung, komme nicht weiter....

Status
Nicht offen für weitere Antworten.

ModellbahnerTT

Bekanntes Mitglied
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:

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"."
 
Zuletzt bearbeitet:

Jay1980

Bekanntes Mitglied
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

Top Contributor
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.
 

ModellbahnerTT

Bekanntes Mitglied
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"."
 
B

bygones

Gast
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

Top Contributor
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:
Code:
  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.
 
B

bygones

Gast
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
 

Marco13

Top Contributor
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 :oops:

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

ModellbahnerTT

Bekanntes Mitglied
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:

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

Top Contributor
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
Code:
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
Code:
 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
Code:
 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
Code:
 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
Code:
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

Top Contributor
Hier meine Lösung, Performance ist ganz gut:

Java:
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.
 
Zuletzt bearbeitet:
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
districon Rekursion und Dynamische Programmierung Allgemeine Java-Themen 2
Ernesto95 HTTP Mit JavaScript erzeugte dynamische Webseite auslesen und nach einem Schlüsselwort durchsuchen Allgemeine Java-Themen 6
hello_autumn Statistische/dynamische Tests Allgemeine Java-Themen 10
E Socket Dynamische Klasse von ObjectOutputStream lesen. Allgemeine Java-Themen 8
P Erste Schritte Dynamische Anzahl von verschachtelten Schleifen Allgemeine Java-Themen 5
J Dynamische Rückgabewerte Allgemeine Java-Themen 2
K Dynamische Webseiten auslesen Allgemeine Java-Themen 6
S Variablen Dynamische Arrays Allgemeine Java-Themen 2
N Dynamische Objekte / DB Allgemeine Java-Themen 5
B dynamische Java Slideshow Allgemeine Java-Themen 4
SuperSeppel13 Dynamische Bibliotheken einbinden Allgemeine Java-Themen 16
B Script Problem "Dynamische Datenstruktur" Allgemeine Java-Themen 13
A Dynamische PDF Erstellung mit iText Allgemeine Java-Themen 4
C dynamische imports? Allgemeine Java-Themen 13
hdi dynamische return-Werte Allgemeine Java-Themen 15
M JUnit und dynamische Tests Allgemeine Java-Themen 11
X dynamische bindung - Typsystem :?: Allgemeine Java-Themen 5
C dynamische variablen Namen! Allgemeine Java-Themen 4
D dynamische Objekte erzeugen? Allgemeine Java-Themen 16
G eigener logger mittels classe (dynamische logfilename) log4j Allgemeine Java-Themen 15
R Dynamische Sorten-Prüfung? Allgemeine Java-Themen 8
F dynamische ArrayListen? Allgemeine Java-Themen 8
C kann man dynamische variablen namen vergeben? Allgemeine Java-Themen 2
H "dynamische Ladegrafik" Allgemeine Java-Themen 2
C Dynamische Varibalen Allgemeine Java-Themen 3
C dynamische Vererbung Allgemeine Java-Themen 6
H Java Rechner Programmierung der Mathematik Allgemeine Java-Themen 33
D Vigenere Chiffre Programmierung Allgemeine Java-Themen 5
G Thread-Programmierung Allgemeine Java-Themen 5
R Input/Output Programmierung mithilfe der Robot Bibliothek Allgemeine Java-Themen 15
MiMa Programmierung von Bibliotheksklassen Allgemeine Java-Themen 3
zhermann Grundsatzfrage zur strukturierter Programmierung Allgemeine Java-Themen 5
S Kaffemaschine Programmierung Probleme Allgemeine Java-Themen 2
P jCheckBox auf der zusammengeknüpften Programmierung anzeigen lassen Allgemeine Java-Themen 3
K Test-Frist Programmierung - wie vorgehen Allgemeine Java-Themen 5
C Programmierung von Fotoeffekten mit Java möglich? Allgemeine Java-Themen 3
J Rekursive Programmierung-Zählen von Ziffern Allgemeine Java-Themen 5
L Designfrage: Dispatcher-Programmierung - redundante Auslegung Allgemeine Java-Themen 1
E Sonderzeichen nicht setzbar: Großes Problem bei Programmierung unter Linux Mint mit Virtual Box Allgemeine Java-Themen 5
C BlackBox-Framework - Plugin Programmierung Allgemeine Java-Themen 4
S Objekt orientierte Programmierung Allgemeine Java-Themen 7
E Socket Client-Server-Programmierung Allgemeine Java-Themen 44
M Parallele Programmierung: volatile Variable nimmt ungewöhnlichen Wert an Allgemeine Java-Themen 3
C Open Soure Projekte für parallele Programmierung Allgemeine Java-Themen 6
E Thread Programmierung Allgemeine Java-Themen 2
K Multithread Programmierung...ExecutionCompletionService Allgemeine Java-Themen 7
E objektorientierte Programmierung Allgemeine Java-Themen 3
C Hilfe bei Adressbuch-Programmierung, wie am Besten mit JList implementieren Allgemeine Java-Themen 2
J Problem mit der Thread Programmierung Allgemeine Java-Themen 2
T Fehler bei der Programmierung eines Universaldienstbrowsers Allgemeine Java-Themen 3
J 3d-Programmierung Allgemeine Java-Themen 7
S BlueJ BlueJ - Geldautomat-Programmierung Allgemeine Java-Themen 2
G Funktionale Programmierung, OO- Programmierung, ... Allgemeine Java-Themen 9
J Hardware Programmierung Allgemeine Java-Themen 3
Kr0e Atomic / Lockfree Programmierung Allgemeine Java-Themen 11
6 Java - Threads - parallele Programmierung - Tutorial Allgemeine Java-Themen 6
I parallele Programmierung mit Java Allgemeine Java-Themen 3
X Error bei der Programmierung eines Sortieralgorithmus Allgemeine Java-Themen 2
J Modul/Komponenten/Addon-Programmierung Allgemeine Java-Themen 3
S Applet Programmierung in Eclipse Allgemeine Java-Themen 12
B Observer vs Listener (GUI-Programmierung) Allgemeine Java-Themen 5
Developer_X Batch Programmierung Allgemeine Java-Themen 4
Developer_X Datei Programmierung Allgemeine Java-Themen 18
hdi Suche nach Begriff aus der Programmierung Allgemeine Java-Themen 11
K Programmierung einer Hilfe Allgemeine Java-Themen 6
G Threads programmierung Allgemeine Java-Themen 7
F Frage zu JSP / Java Programmierung Allgemeine Java-Themen 2
L Brauche Hilfe bei Memory Programmierung Allgemeine Java-Themen 2
G Framework für Multi-Prozessor-Programmierung? Allgemeine Java-Themen 4
tomtailor Mobiltelefon - Programmierung Allgemeine Java-Themen 8
O Oberfläche und "richtige" Programmierung Allgemeine Java-Themen 8
ven000m Constraint Programmierung Allgemeine Java-Themen 6
X Langsames Java im Bereich der GUI-Programmierung Allgemeine Java-Themen 8
F Klausuraufgaben Java-Programmierung Allgemeine Java-Themen 10
D Elegante Programmierung. Allgemeine Java-Themen 7
G Software für Java programmierung Allgemeine Java-Themen 5
J Frage zu Objektorientierter Programmierung Allgemeine Java-Themen 9
K Bubblesort Programmierung, finde Fehler nicht . Allgemeine Java-Themen 25
bernd Hardwarenahe Programmierung Allgemeine Java-Themen 14
S Taschenrechner und Programmierung Allgemeine Java-Themen 4
D Fraen zur Programmierung einer Volltextsuche Allgemeine Java-Themen 8
P Datentypen String-Daten zu Byte-Zahlen konvertieren - Komme nicht weiter nach vielem versuchen :-/ Allgemeine Java-Themen 7
timomeinen Java Generics - Wie komme ich an die <T>.class? Allgemeine Java-Themen 13
L Wie komme ich an folgende Java-Sachen von Sun Allgemeine Java-Themen 2
G Wie komme ich an den Pfad zu meinem Programm? Allgemeine Java-Themen 2

Ähnliche Java Themen

Neue Themen


Oben