| Property |
Value |
| dbo:abstract
|
- Dynamische Programmierung ist eine Methode zum algorithmischen Lösen von Optimierungsproblemen. Der Begriff wurde in den 1940er Jahren von dem amerikanischen Mathematiker Richard Bellman eingeführt, der diese Methode auf dem Gebiet der Regelungstheorie anwandte. In diesem Zusammenhang wird auch oft von Bellmans Prinzip der dynamischen Programmierung gesprochen. Dynamische Programmierung kann dann erfolgreich eingesetzt werden, wenn das Optimierungsproblem aus vielen gleichartigen Teilproblemen besteht und eine optimale Lösung des Problems sich aus optimalen Lösungen der Teilprobleme zusammensetzt. Dies nennt man Optimalitätsprinzip von Bellman. In der dynamischen Programmierung werden zuerst die optimalen Lösungen der kleinsten Teilprobleme direkt berechnet und dann geeignet zu einer Lösung eines nächstgrößeren Teilproblems zusammengesetzt. Dieses Verfahren setzt man fort, bis das ursprüngliche Problem gelöst wurde. Einmal berechnete Teilergebnisse werden in einer Tabelle gespeichert. Bei nachfolgenden Berechnungen gleichartiger Teilprobleme wird auf diese Zwischenlösungen zurückgegriffen, anstatt sie jedes Mal neu zu berechnen, was zu einer Senkung der Laufzeit führt. Wird die dynamische Programmierung konsequent eingesetzt, vermeidet sie kostspielige Rekursionen, weil bekannte Teilergebnisse wiederverwendet werden. In der Regelungstheorie und verwandten Gebieten kann man das Prinzip der dynamischen Programmierung einsetzen, um etwa eine Gleichung herzuleiten (Hamilton-Jacobi-Bellman-Gleichung), deren Lösung den optimalen Wert ergibt. Die Argumentation ist dabei etwa folgende: Wenn das Problem zeitabhängig ist, kann man den optimalen Wert des Zielfunktionals zu einem bestimmten Zeitpunkt betrachten. Man fragt sich dann, welche Gleichung die optimale Lösung erfüllen muss, damit das Zielfunktional auch zu einem späteren Zeitpunkt optimal bleibt, dies führt zur Hamilton-Jacobi-Bellman-Gleichung. Damit kann man das Problem in Zeitschritte einteilen, anstatt es auf einmal lösen zu müssen. In der Physik war dieses Prinzip schon seit Langem bekannt, allerdings nicht unter diesem Namen. Der Übergang von einer globalen (alle Zeitpunkte gleichzeitig) zu einer zeitabhängigen (dynamischen) Betrachtungsweise entspricht dort der Transformation des Lagrange-Funktionals in das Hamilton-Funktional mit Hilfe der Legendre-Transformation. (de)
- Dynamische Programmierung ist eine Methode zum algorithmischen Lösen von Optimierungsproblemen. Der Begriff wurde in den 1940er Jahren von dem amerikanischen Mathematiker Richard Bellman eingeführt, der diese Methode auf dem Gebiet der Regelungstheorie anwandte. In diesem Zusammenhang wird auch oft von Bellmans Prinzip der dynamischen Programmierung gesprochen. Dynamische Programmierung kann dann erfolgreich eingesetzt werden, wenn das Optimierungsproblem aus vielen gleichartigen Teilproblemen besteht und eine optimale Lösung des Problems sich aus optimalen Lösungen der Teilprobleme zusammensetzt. Dies nennt man Optimalitätsprinzip von Bellman. In der dynamischen Programmierung werden zuerst die optimalen Lösungen der kleinsten Teilprobleme direkt berechnet und dann geeignet zu einer Lösung eines nächstgrößeren Teilproblems zusammengesetzt. Dieses Verfahren setzt man fort, bis das ursprüngliche Problem gelöst wurde. Einmal berechnete Teilergebnisse werden in einer Tabelle gespeichert. Bei nachfolgenden Berechnungen gleichartiger Teilprobleme wird auf diese Zwischenlösungen zurückgegriffen, anstatt sie jedes Mal neu zu berechnen, was zu einer Senkung der Laufzeit führt. Wird die dynamische Programmierung konsequent eingesetzt, vermeidet sie kostspielige Rekursionen, weil bekannte Teilergebnisse wiederverwendet werden. In der Regelungstheorie und verwandten Gebieten kann man das Prinzip der dynamischen Programmierung einsetzen, um etwa eine Gleichung herzuleiten (Hamilton-Jacobi-Bellman-Gleichung), deren Lösung den optimalen Wert ergibt. Die Argumentation ist dabei etwa folgende: Wenn das Problem zeitabhängig ist, kann man den optimalen Wert des Zielfunktionals zu einem bestimmten Zeitpunkt betrachten. Man fragt sich dann, welche Gleichung die optimale Lösung erfüllen muss, damit das Zielfunktional auch zu einem späteren Zeitpunkt optimal bleibt, dies führt zur Hamilton-Jacobi-Bellman-Gleichung. Damit kann man das Problem in Zeitschritte einteilen, anstatt es auf einmal lösen zu müssen. In der Physik war dieses Prinzip schon seit Langem bekannt, allerdings nicht unter diesem Namen. Der Übergang von einer globalen (alle Zeitpunkte gleichzeitig) zu einer zeitabhängigen (dynamischen) Betrachtungsweise entspricht dort der Transformation des Lagrange-Funktionals in das Hamilton-Funktional mit Hilfe der Legendre-Transformation. (de)
|
| dbo:author
| |
| dbo:individualisedGnd
| |
| dbo:originalTitle
|
- Dynamic Programming (de)
- Richard Bellman on the birth of Dynamic Programming (de)
- Dynamic Programming (de)
- Richard Bellman on the birth of Dynamic Programming (de)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageRevisionID
| |
| prop-de:autor
| |
| prop-de:band
| |
| prop-de:jahr
|
- 1957 (xsd:integer)
- 2002 (xsd:integer)
|
| prop-de:nummer
| |
| prop-de:online
| |
| prop-de:remark
|
- Ansetzungsform GND „Dynamische Optimierung“.
|
| prop-de:typ
| |
| dc:publisher
|
- Princeton University Press
|
| dct:subject
| |
| bibo:pages
| |
| rdf:type
| |
| rdfs:comment
|
- Dynamische Programmierung ist eine Methode zum algorithmischen Lösen von Optimierungsproblemen. Der Begriff wurde in den 1940er Jahren von dem amerikanischen Mathematiker Richard Bellman eingeführt, der diese Methode auf dem Gebiet der Regelungstheorie anwandte. In diesem Zusammenhang wird auch oft von Bellmans Prinzip der dynamischen Programmierung gesprochen. (de)
- Dynamische Programmierung ist eine Methode zum algorithmischen Lösen von Optimierungsproblemen. Der Begriff wurde in den 1940er Jahren von dem amerikanischen Mathematiker Richard Bellman eingeführt, der diese Methode auf dem Gebiet der Regelungstheorie anwandte. In diesem Zusammenhang wird auch oft von Bellmans Prinzip der dynamischen Programmierung gesprochen. (de)
|
| rdfs:label
|
- Dynamische Programmierung (de)
- Dynamische Programmierung (de)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is prop-de:paradigma
of | |
| is foaf:primaryTopic
of | |
