algo:knapsack - Backtracking

[Dobias]

Hallo zusammen,

ich habe mich heute mit dem Knapsack-Tutorial (http://www.proggen.org/doku.php?id=algo:knapsack) beschäftigt, was mir gut gefallen hat.

Eine Frage zum Backtracking habe ich noch, und zwar zu folgendem Code-Teil:

Code: Alles auswählen

    if( r - w[i] == results[i + 1][currentVolume - v[i]] )
    {
      // Gegenstand war im Rucksack
      fprintf( stdout, "selecting %d (%d / %d)\n", i + 1, v[i], w[i] );
      r -= w[i];
    }

Wenn ich das Ganze richtig verstanden habe, müsste es auch so gehen:

Code: Alles auswählen

    if( results[i][currentVolume] != results[i + 1][currentVolume] )
    {
      // Gegenstand war im Rucksack
      fprintf( stdout, "selecting %d (%d / %d)\n", i + 1, v[i], w[i] );
      currentVolume -= v[i];
    }

(vollständiger Code: http://codepad.org/xJttghi1)
Ich persönlich finde das so etwas einfacher, was aber natürlich Geschmackssache sein kann.

Meine Frage ist nur, ob ich richtig liege und das so auch korrekt ist, oder ob meine Variante nur zufällig bei den Eingabewerten, die ich getestet habe (incl. denen aus dem Tutorial) funktioniert, und mir bei anderen um die Ohren fliegen kann.

[Dobias]

Vielleicht sollte ich zusätzlich in Worten beschreiben, was ich anders mache.
Also ich teste nicht, ob der Wert noch passt wenn ich den Gegenstand mit aktuellem Index aus dem Rucksack nehmen würde, sondern ich geh einfach so lange nach rechts (++index) in der Tabelle, bis der Wert sich ändert. Wenn es soweit ist, ziehe ich das Gewicht des aktuellen Gegenstands vom Gewichtsindex ab.

[cloidnerux]

Hi und Willkommen im Forum

Meine Frage ist nur, ob ich richtig liege und das so auch korrekt ist, oder ob meine Variante nur zufällig bei den Eingabewerten, die ich getestet habe (incl. denen aus dem Tutorial) funktioniert, und mir bei anderen um die Ohren fliegen kann.

Ich musste mich gerade erst in die Sache einlesen.

Der im Tutorial verwendet Algorithmus geht die Dynamisierungstabelle von hinten durch und sucht ein Element, dass zwei Bedingungen erfüllt:
V_m = Momentanes Gesamtvolumen
W_m = Momentaner Wert
V = Volumen des Elementes i
W = Wert des Elementes i
D[a] = Dynamisierungsmatrix
Bedingung:
D[V_m - V] = W_m - W
Oder ausgesprochen: Ein Element kann nur dann im Rucksack sein, wenn ich es herausnehmen kann und das neue Volumen und Wert noch immer zu den Gegenständen im Rucksack passen.

Deinen Code kann ich gerade nicht bewerten. Welche Mathematische Grundlage hast du dafür?
Nach der Tabelle im Artikel müsste dein Algorithmus doch egt falsche Ergebnisse produzieren, oder irre ich mich?
Man fängt unten Links an, geht nach Rechts und wird Element 2 finden. Man zieht das Volumen von Element 2 ab, kommt in Zeile 25, geht nach Rechts und findet Element 5, zieht 10 vom Volumen ab, geht also in Zeile 15, merkt das D[15][5] != D[15][6], nimmt also auch Element 6 als Element aus dem Rucksack und kommt in Zeile 4 wo man nichts mehr finden wird?

Ansonsten teste es über zufällige werte, generiert durch einen Zufallsgenerator gegen den Algorithmus aus dem Wiki. So Automatisiert kann man mal eben eine gute Anzahl Werte testen, wobei das auch nur ein Pseudo-Beweis ist.

[Dobias]

Nach der Tabelle im Artikel müsste dein Algorithmus doch egt falsche Ergebnisse produzieren, oder irre ich mich?

Über die Tabelle im Artikel läuft der gegebene Algo folgenden Weg:

Code: Alles auswählen

x y
0 30
1 25
2 25
3 25
4 25
5 15
6 15
7 15
8 15
9 0

Damit landen dann die Gegenstände 1, 5 und 9 im Rucksack.

Mein Also nimmt diesen Weg:

Code: Alles auswählen

x y
0 30
1 30
2 25
3 25
4 25
5 15
6 15
7 15
8 15
9 0

Damit landen dann die Gegenstände 2, 5 und 9 im Rucksack.
Das Ergebnis ist zwar ein anderes, aber ebenfalls ein Optimum. Mit diesen Werten ist es also korrekt.

Deinen Code kann ich gerade nicht bewerten. Welche Mathematische Grundlage hast du dafür?

Gar keine, deshalb frag ich ja nach.
Es sah für mich halt gut aus. Die Gültigkeit des Verfahrens im Artikel ist dort aber übrigens auch nicht bewiesen.

Ansonsten teste es über zufällige werte, generiert durch einen Zufallsgenerator gegen den Algorithmus aus dem Wiki. So Automatisiert kann man mal eben eine gute Anzahl Werte testen, wobei das auch nur ein Pseudo-Beweis ist.

Sehr gute Idee. Hab ich direkt mal gemacht (http://codepad.org/s0jb6ilB).
Dabei sieht man tatsächlich, dass es Fälle gibt, in denen beide Verfahren unterschiedliche Ergebnisse liefern!
Als ich mir ein paar einfache Fälle von Hand angucken wollte, ist mir allerdings aufgefallen, dass der Algorithmus aus dem Tutorial oft in undefiniertes Verhalten läuft. Z.b mit folgenden Testdaten:

Code: Alles auswählen

5 2
17 13
3 13

gilt in dieser Zeile

Code: Alles auswählen

if( r - w[i] == results[i + 1][currentVolume - v[i]] )

Code: Alles auswählen

currentVolume - v[i] == -12

und dann kann ja bekanntlich irgendwas passieren (http://codepad.org/oGIwQSRH).
Ich konnte also leider nicht überprüfen, ob mein Verfahren korrekt läuft, weil das gegebene bereits fehlerhaft ist.

[cloidnerux]

Dabei sieht man tatsächlich, dass es Fälle gibt, in denen beide Verfahren unterschiedliche Ergebnisse liefern!

Was aber entweder daran liegt, das du zwei Äquivalente Objekte hast, oder die Algorithmen nicht funktionieren.

Als ich mir ein paar einfache Fälle von Hand angucken wollte, ist mir allerdings aufgefallen, dass der Algorithmus aus dem Tutorial oft in undefiniertes Verhalten läuft. Z.b mit folgenden Testdaten:

Das liegt daran, dass deine Initialisierung fehlerhaft ist.

Code: Alles auswählen

V = rand() % maxV + 1;
  n = rand() % maxN + 1;

Das ist nicht sinnvoll. Wähle ein Konstantes V und n und variiere nur die Objekte.
So treibst du deinen Algorithmus schnell in die mathematischen Grenzen.

Damit landen dann die Gegenstände 2, 5 und 9 im Rucksack.

Kann es sein, dass die Tabelle im Wiki-Artikel einen Fehler hat?

Code: Alles auswählen

15	 -1	 -1	 -1	 -1	 -1	->20	30<-	30	30	 0

Wenn dein Algorithmus da durch läuft, dann müsste es doch 30-30 sein?

[Dobias]

Was aber entweder daran liegt, das du zwei Äquivalente Objekte hast, oder die Algorithmen nicht funktionieren.

Wenn es mehrere gültige Gegenstandskombinationen gibt, um zum Optimum zu kommen (wie im Beispiel aus dem Tutorial) ist das ja ok. Bei meinem Vergleichstest liefern beide Algorithmen aber unterschiedliche Volumensummen und Wertesummen.

Der Algorithmus aus dem Tutorial hat aber wenn ich das richtig sehe einen Bug. Er liest über die Arraygrenzen hinaus (negativer Index, wie oben beschrieben) und kommt deshalb bei bestimmten Eingabedaten zu zufälligen Ergebnissen, die manchmal einfach Unfug sind. Aber das ist bei undefiniertem Programmverhalten ja normal. Und ich halte es nicht für sinnvoll, dass ich mein Verfahren gegen diese Implementierung teste, was natürlich nicht bedeutet, dass meine keinen Fehler hat.

Das liegt daran, dass deine Initialisierung fehlerhaft ist.
Das ist nicht sinnvoll. Wähle ein Konstantes V und n und variiere nur die Objekte.
So treibst du deinen Algorithmus schnell in die mathematischen Grenzen.

Ich weiß zwar nicht, wieso du das für sinnvoller hälst, aber OK, gemacht: http://codepad.org/7uitgNk5
Ein Beispiel daraus:

Code: Alles auswählen

Rucksackvolumen: 5
Objekte: 2
Volumen Wert
2       10
2       3

Mein Algorithmus nimmt den Gegenstand mit Wert 10, also den richtigen: Der Algorithmus aus dem Tutorial nimmt den Gegenstand mit Wert 3, also den falschen.

Kann es sein, dass die Tabelle im Wiki-Artikel einen Fehler hat?

Code: Alles auswählen

15     -1  -1  -1  -1  -1 ->20    30<-    30  30   0

Wenn dein Algorithmus da durch läuft, dann müsste es doch 30-30 sein?

Ja, die Tabelle im Tutorial ist an der von dir gezeigten Stelle fehlerhaft. Auf dieser falschen Tabelle würde mein Algo tatsächlich Mist machen, aber das ist dann ja nicht seine Schuld.

Hab ich das mit dem undefinierten Verhalten der Implementierung aus dem Tutorial (ganz unabhängig von dem Fehler in der gezeigten Tabelle) denn richtig erkannt?

[cloidnerux]

Ich weiß zwar nicht, wieso du das für sinnvoller hälst, aber OK, gemacht: http://codepad.org/7uitgNk5
Ein Beispiel daraus:

Vlt solltest du die Anzahl der Objekte und Volumen groß genug wählen, dass der gesamte Algorithmus überhaupt sinn macht.
Setzte mal V = 50 und Anzahl Objekte = 20,
weise dann den Objekten zufällige Volumen und Werte zu, wobei das Volumen < V sein muss.
Dann solltest du in die Größenordnungen kommen, wo Fehler deutlich werden.

Ja, die Tabelle im Tutorial ist an der von dir gezeigten Stelle fehlerhaft. Auf dieser falschen Tabelle würde mein Algo tatsächlich Mist machen, aber das ist dann ja nicht seine Schuld.

Fehler in den Artikel sollten immer Angeprangert werden Aber nur damit sie Korrigiert werden können.

Hab ich das mit dem undefinierten Verhalten der Implementierung aus dem Tutorial (ganz unabhängig von dem Fehler in der gezeigten Tabelle) denn richtig erkannt?

Ja, ein negativer Index ist ein Bug. In die Funktion muss noch eine Abfrage, ob der Gegenstand überhaupt noch in den Rucksack passen kann, damit das nicht mehr Passiert.

[Dobias]

Vlt solltest du die Anzahl der Objekte und Volumen groß genug wählen, dass der gesamte Algorithmus überhaupt sinn macht.
Setzte mal V = 50 und Anzahl Objekte = 20,
weise dann den Objekten zufällige Volumen und Werte zu, wobei das Volumen < V sein muss.
Dann solltest du in die Größenordnungen kommen, wo Fehler deutlich werden.

Ich hatte die Werte vorhin extra klein gehalten, weil ich Fehler sehen wollte, die man im Kopf ohne viel Aufwand nachrechnen kann. Aber hier wie gewünscht mit größeren Mengen. http://codepad.org/S06zgnDk

Ja, ein negativer Index ist ein Bug. In die Funktion muss noch eine Abfrage, ob der Gegenstand überhaupt noch in den Rucksack passen kann, damit das nicht mehr Passiert.

Als ich gerade versucht habe, diese Abfrage einzubauen, ist mir ein weiterer Fehler im Tutorial-Code aufgefallen. In den Beispieldaten sind 10 Objekte, das Backtracking schaut den letzten aber nie an.

Code: Alles auswählen

selecting 1 (5 / 8)
NOT selecting 2 (5 / 8)
NOT selecting 3 (6 / 6)
NOT selecting 4 (8 / 5)
selecting 5 (10 / 10)
NOT selecting 6 (11 / 5)
NOT selecting 7 (12 / 10)
NOT selecting 8 (15 / 17)
selecting 9 (15 / 20)

Da fehlt also ein

Code: Alles auswählen

NOT selecting 10 (30 / 20)

Wenn Gegenstand 10 in den Rucksack gehören würde, würde er ihn also nicht reintun.

So ganz einfach lösen konnte ich das aber auch nicht, denn einfach aus dem hier

Code: Alles auswählen

for( int i = 0; i < n-1; i++ )

das hier

Code: Alles auswählen

for( int i = 0; i < n; i++ )

machen, geht auch nicht, weil man dann beim Index über die Arraygrenzen hinaus liest.

Vielleicht sollte dani93 den Backtracking-Teil also nochmal überarbeiten.

[cloidnerux]

Ich hatte die Werte vorhin extra klein gehalten, weil ich Fehler sehen wollte, die man im Kopf ohne viel Aufwand nachrechnen kann. Aber hier wie gewünscht mit größeren Mengen. http://codepad.org/S06zgnDk

Sieht doch schon besser aus
Wobei du dich hier bei den Indices vertan hast:

Code: Alles auswählen

      normalBTWSum += w[i+1];
      normalBTVSum += v[i+1];

Ich denke, da sollte w und v stehen. Dann passen auch die Werte die du ausgibst
Edit: Es fehlt auch das subtrahieren von currentVolume. Ich habe es so gelöst:

Code: Alles auswählen

  int cV = currentVolume;
  // Über alle Gegenstände iterieren (-1, weil mit i+1 gerechnet wird)
  for( int i = 0; i < maxN - 1; i++ )
  {
    // Versuchen den aktuellen Gegenstand aus dem Rucksack zu nehmen.
    // Stimmt der Wert an der neuen Position?
    // aktueller Wert im Rucksack - Wert des aktuellen Gegenstands 
    //       == Maximum für diesen Gegenstand mit dem neuen Volumen
    if( r - w[i] == results[i + 1][cV - v[i]] )
    {
      // Gegenstand war im Rucksack
      r -= w[i];
      normalBTWSum += w[i];
      normalBTVSum += v[i];
	  cV -= v[i];
    }
  }

Vielleicht sollte dani93 den Backtracking-Teil also nochmal überarbeiten.

Das sollte er machen, ja.

[cloidnerux]

Ich hab da noch ein wenig dran herum gespielt, folgender Code:

Code: Alles auswählen

#include <cstdio>
#include <cstring>
#include <iostream>

int knapsack( const int currentVolume, const int i );
 
const int maxN = 20;
const int maxV = 50;
const int resultLength = ( maxV + 1 ) * sizeof( int );
 
int V;
int n;
int v[maxN];
int w[maxN];
int results[maxN][maxV + 1];
 
int test();

int main()
{
	for ( int i = 0; i < 100; ++i )
	{
		test();
	}
	getchar();
	return 0;
}

int test()
{
  V = maxV;
  n = maxN;
  for( int i = 0; i < n; i++ )
  {
    v[i] = rand() % 30;
    w[i] = rand() % 20;
  }
  for( int i = 0; i < maxN; i++ )
    memset( results[i], -1, resultLength );
  int r = knapsack( V, 0 );
  int currentVolume = -1;
  for( int i = 0; i <= maxV && currentVolume == -1; i++ )
  {
    if( results[0][i] == r )
      currentVolume = i;
  }


  // Backtracking aus dem Tutorial.
  int normalBTWSum( 0 );
  int normalBTVSum( 0 );
  int cV = currentVolume;
  for( int i = 0; i < maxN - 1; i++ )
  {
    if( r - w[i] == results[i + 1][cV - v[i]] )
    {
      r -= w[i];
      normalBTWSum += w[i];
      normalBTVSum += v[i];
	  cV -= v[i];
    }
  }


  // Dem Dobias sein Backtracking.
  int otherBTWSum( 0 );
  int otherBTVSum( 0 );
   
  for( int i = 0; i < n - 1; i++ )
  {
    if( results[i][currentVolume] != -1 && results[i][currentVolume] != results[i + 1][currentVolume] )
    {
      currentVolume -= v[i];
      otherBTWSum += w[i];
      otherBTVSum += v[i];
    }
  }
  if ( otherBTWSum != normalBTWSum || otherBTVSum != normalBTVSum || normalBTVSum > V || otherBTVSum > V)
  {  
	  if ( otherBTWSum && normalBTWSum && otherBTVSum && normalBTVSum )
	  {
		  fprintf( stdout, "------------------\n" );
		  fprintf( stdout, "tut: %d/%d\n", normalBTVSum, normalBTWSum );
		  fprintf( stdout, "new: %d/%d\n", otherBTVSum, otherBTWSum );
	  fprintf( stdout, "\n" );
	  }
  }

  return 0;
}
 
int knapsack( const int currentVolume, const int i )
{
  if( i < n )
  {
    if( results[i][currentVolume] != -1 )
      return results[i][currentVolume];
    return results[i][currentVolume] = std::max( knapsack( currentVolume, i + 1 ),
                                                 ( currentVolume - v[i] >= 0 )
                                                 ? ( w[i] + knapsack( currentVolume - v[i], i + 1 ) ) 
                                                 : 0 );
  }
  return 0;
}

Zeigt auf, dass das Backtracking hier, das egt so wie im Artikel sein sollte, mitunter falsche Ergebnisse liefert. Das Volumen ist zu groß. Dani93?