Mehrere Constraint-Knapsack-Problem

Als ein gutes Beispiel dienen könnte Folgendes problem:

Gegeben ein ungerichteter graph G mit positiven gewichten und N Ecken.

Beginnen Sie mit einer Summe von M Geld. Für die durch einen Eckpunkt i, die Sie zahlen müssen, S[ich] Geld. Wenn Sie nicht genug Geld haben - können Sie nicht passieren, dass vertex. Den kürzesten Weg zu finden vom Eckpunkt 1 zum Eckpunkt N, unter Beachtung der oben genannten Bedingungen; oder der Staat, dass ein solcher Pfad nicht existiert. Wenn es existiert mehr als ein Pfad mit der gleichen Länge, dann die Ausgabe der billigste. Einschränkungen: 1

Pseudocode:

Set states(i,j) as unvisited for all (i,j)
Set Min[i][j] to Infinity for all (i,j)

Min[0][M]=0

While(TRUE)

Among all unvisited states(i,j) find the one for which Min[i][j]
is the smallest. Let this state found be (k,l).

If there wasn't found any state (k,l) for which Min[k][l] is
less than Infinity - exit While loop.

Mark state(k,l) as visited

For All Neighbors p of Vertex k.
   If (l-S[p]>=0 AND
    Min[p][l-S[p]]>Min[k][l]+Dist[k][p])
      Then Min[p][l-S[p]]=Min[k][l]+Dist[k][p]
   i.e.
If for state(i,j) there are enough money left for
going to vertex p (l-S[p] represents the money that
will remain after passing to vertex p), and the
shortest path found for state(p,l-S[p]) is bigger
than [the shortest path found for
state(k,l)] + [distance from vertex k to vertex p)],
then set the shortest path for state(i,j) to be equal
to this sum.
End For

End While

Find the smallest number among Min[N-1][j] (for all j, 0<=j<=M);
if there are more than one such states, then take the one with greater
j. If there are no states(N-1,j) with value less than Infinity - then
such a path doesn't exist.

InformationsquelleAutor der Antwort EFreak

Dort sind gierig wie Heuristiken zur Berechnung einer "Effizienz" für jedes Element, das schnell laufen und Ertrag Ungefähre Lösungen.

Können Sie einen branch-and-bound-Algorithmus. Sie bekommen eine erste untere Schranke mit einem gierig wie die Heuristik, die verwendet werden können, zum initialisieren der vorhandenen Lösung. Sie berechnen können, Obere Grenzen für die verschiedenen sub-Probleme betrachtet man jede der m Nebenbedingungen nacheinander (entspannt die anderen Randbedingungen in das problem), dann verwenden Sie die niedrigste von diesen Grenzen als eine Obere Schranke für das ursprüngliche problem. Diese Technik ist aufgrund Shih. Allerdings ist diese Technik wahrscheinlich nicht gut funktionieren, wenn keine Besondere Einschränkung neigt zu Dominieren, die Lösung, oder wenn die erste Lösung aus, die gierig wie die Heuristik ist nicht in der Nähe des optimalen.

Gibt es bessere modernere algorithmen, die sind schwieriger zu implementieren, finden Sie unter "multidimensional knapsack problem" Papiere von J Puchinger!

InformationsquelleAutor der Antwort tyebillion