In der dynamischen Programmierung werden Teilproblemgraphen als gerichtete azyklische Graphen (dag) betrachtet, aber wie löst man, wenn ein Teilproblemgraph einen Zyklus enthält? Beispiels Lösung von Subproblem (a) hängt von den Lösungen von Subproblem (b) undSubproblem (c) wieder Lösung von Subproblem (b) hängt von der Lösung von Subproblem (a) ...Dynamische Programmierung: Der Fall, wenn ein Subproblem-Graph kein azyklischer Graph ist?
In der aktuellen Form ist dieses Problem einfach nicht lösbar. Sie können A nicht lösen, ohne B zu lösen und umgekehrt. Haben Sie ein spezifischeres Problem? Vielleicht war deine Analyse falsch und die Teilprobleme sind nicht zyklisch.
Vielleicht können Sie die Teilprobleme aufteilen, so dass Sie eine critical step lösen können, die die zyklische Abhängigkeit ohne dynamic programming löst.
In einigen Fällen (genau wenn die Werte der Funktion linear voneinander abhängen) können Sie Ihr Problem bei der Lösung eines linearen Gleichungssystems reduzieren. Zum Beispiel, wenn Sie wissen, dass
sub(a) = sub(b) + sub(c)
sub(b) = sub(c) * 2 + 5
sub(c) = sub(a) - 1
dann können Sie ein lineares System, das wie eine Matrix aussieht. In diesem Fall wird es also
a b c value
eq.1 1 -1 -1 0
eq.2 0 1 -2 5
eq.3 -1 0 1 -1
sein, haben Sie eine Matrix A und einen Vektor c, und Sie wollen x dass ein x = c solche zu finden. Vektor x enthält Werte Ihrer Variablen in der Reihenfolge. Dies kann mit Standardalgebraalgorithmen, vermutlich der Gauß'schen Transformation, geschehen.
Ich denke dann ist es nicht anwendbar, dynamische Programmierung zu verwenden ... oder haben Sie ein Beispiel? – shole
@enggiqbal Wenn ein Benutzer Ihre Frage beantwortet, bitte auch ** akzeptieren ** seine Antwort ([Annahme von Antworten: Wie funktioniert es?] (Https://meta.stackexchange.com/questions/5234/how-does-accepting- An-Antwort-Arbeit)). Wenn nicht, geben Sie bitte an, was unbeantwortet bleibt, dies ist ein sehr wichtiger Teil von StackOverflow, vielen Dank. – Zabuza