Algorithmus für längsten Weg

Majin_Clodan

Hi Leute!
Also bei der jetzigen Aufgabe würde ich gerne wissen, welchen Algorithmus man benutzen sollte, um an das Ziel kommen.

Also wir haben in unserer Aufgabe ein Feld gegeben. Das sieht beispielsweise so aus:
2 1 5 0 4 3 4 2

Hierbei sollen wir die längste Zahlenfolge finden, dessen Werte streng aufsteigend sortiert sein sollen.
Dies wären also z.B. die:
2 3 4(hintere 4)
1 3 4(hintere 4)
0 3 4(hintere 4)

Da wir die "Längsten" Folge berechnen sollen, wäre es also das dasselbe, als wenn man den längsten Weg berechnen würde.
Dementsprechen würde ich mich freuen, wenn man mir einige Algorithmen nennen könnte, da wir bisher nur sehr wenige behandelt haben wie z.B. den Dijkstra-Algorithmus, welcher mir aber nur den kürzesten Weg berechnet.

MFG Majin_Clodan

Edit:
Mir ist nun der Hamilton-Graph eingefallen. Hat da jemand enen Pseudocode o.ä.?? Ich finde das nicht per google.

namespace invader

Das nennt sich "Longest Increasing Subsequence" oder so ähnlich und lässt sich durch Dynamische Programmierung in quadratischer Zeit lösen.

Majin_Clodan

Cool, Danke für den Tipp.
Habe nun sogar fast ein komplettes Programm dazu gefunden.

// Returns the length of the longest increasing subsequence.
// Note that this is looking for the longest strictly increasing subsequence.  
//    This can be easily modified for other situations.
int lcs( int* a, int N ) {
   int *best, *prev, i, j, max = 0;
   best = (int*) malloc ( sizeof( int ) * N );
   prev = (int*) malloc ( sizeof( int ) * N );

   for ( i = 0; i < N; i++ ) best[i] = 1, prev[i] = i;

   for ( i = 1; i < N; i++ )
      for ( j = 0; j < i; j++ )
         if ( a[i] > a[j] && best[i] < best[j] + 1 )
            best[i] = best[j] + 1, prev[i] = j;  // prev[] is for backtracking the subsequence

   for ( i = 0; i < N; i++ )
      if ( max < best[i] )
         max = best[i];

   free( best );
   free( prev );

   return max;
}

// Sample usage.
int main(){
  int b[] = { 1, 3, 2, 4, 3, 5, 4, 6 };
  // the longest increasing subsequence = 13456?
  // the length would be 5, as well lcs(b,8) will return.
  printf("%d\n", lcs( b, 8 ) );
}

Das einzige, was mich hier stutzig macht, ist diese Zeile:

for ( i = 0; i < N; i++ ) best[i] = 1, prev[i] = i;

hierbei stört mich das Komma, welches nach best und vor prev ist. Was bedeutet dieses Komma? Gehört best und prev noch zur for-Schleife oder wie??

MFG Majin_Clodan

volkard

for ( i = 0; i < N; i++ ) best[i] = 1, prev[i] = i;

ist nur ein sehr freakiger dialekt für

for ( i = 0; i < N; i++ ) { best[i] = 1; prev[i] = i; }

siehe "komma-operator"

Majin_Clodan

Mal eine ganz blöde Frage:
Ich fand diesen Algorithmus auf diesem Link(das C-Programm):
http://www.algorithmist.com/index.php/Category:Longest_Increasing_Subsequence

Wenn ich aber nun best oder prev oder max ausgeben zu lassen, bekomme ich total falsche Ergebnisse.
Bin ich nur zu blöd oder ist das wirklich irgendwie ein falsches Programm??
Unten ist sogar eine Lösung für die längste Reihe. O_o

MFG Majin_Clodan

namespace invader

Bei mir kommt als Ergebnis (also max) 5 raus, was richtig ist.

Wenn man die tatsächliche Reihe (und nicht nur ihre Länge) wissen will, muss man sie rückwärts über die prev-Werte verfolgen. Das sollte dann 1-3-4-5-6 ergeben.

Majin_Clodan

Moin!

Also bei mir kommt auch als Länge 5 heraus.
Trotzdem klappt das bei mir mit dem Ausgeben der Werte nicht. Wenn ich nach der Berechnung von "max" das hier zu stehen habe:

for(i = max; i >= 0; i--) printf("%d",prev[i]);

Bekomme ich falsche Werte heraus. Deswegen bin ich stutzig, ob dieses Programm funktioniert. O.o

MFG Majin_Clodan

namespace invader

Die prev-Werte sind doch sozusagen nur Zeiger auf die jeweils vorhergehende Stelle der Ergebnissequenz. Man muss sie also schrittweise zurückverfolgen. Z.B. ersetzt man die letzte Schleife zum Ermitteln von max durch

for ( i = 0; i < N; i++ )
      if ( max < best[i] )
         max = best[j = i];

   while (prev[j] != j) { printf("%d, ", a[j]); j = prev[j]; }
   printf("%d\n", a[j]), j = prev[j];

Dann wird die Sequenz in umgekehrter Reihenfolge ausgegeben, also 6, 5, 4, 3, 1.