In mathematics, management science, economics, computer science, and bioinformatics, dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions – ideally, using a memory-based data structure. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of a (hopefully) modest expenditure in storage space. (Each of the subproblem solutions is indexed in some way, typically based on the values of its input parameters, so as to facilitate its lookup.) The technique of storing solutions to subproblems ins

Property Value
dbo:abstract
  • In mathematics, management science, economics, computer science, and bioinformatics, dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions – ideally, using a memory-based data structure. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of a (hopefully) modest expenditure in storage space. (Each of the subproblem solutions is indexed in some way, typically based on the values of its input parameters, so as to facilitate its lookup.) The technique of storing solutions to subproblems instead of recomputing them is called "memoization". Dynamic programming algorithms are often used for optimization. A dynamic programming algorithm will examine the previously solved subproblems and will combine their solutions to give the best solution for the given problem. In comparison, a greedy algorithm treats the solution as some sequence of steps and picks the locally optimal choice at each step. Using a greedy algorithm does not guarantee an optimal solution, because picking locally optimal choices may result in a bad global solution, but it is often faster to calculate. Fortunately, some greedy algorithms (such as Kruskal's or Prim's for minimum spanning trees) are proven to lead to the optimal solution. For example, in the coin change problem of finding the minimum number of coins of given denominations needed to make a given amount, a dynamic programming algorithm would find an optimal solution for each amount by first finding an optimal solution for each smaller amount and then using these solutions to construct an optimal solution for the larger amount. In contrast, a greedy algorithm might treat the solution as a sequence of coins, starting from the given amount and at each step subtracting the largest possible coin denomination that is less than the current remaining amount. If the coin denominations are 1,4,5,15,20 and the given amount is 23, this greedy algorithm gives a non-optimal solution of 20+1+1+1, while the optimal solution is 15+4+4. In addition to finding optimal solutions to some problem, dynamic programming can also be used for counting the number of solutions, for example counting the number of ways a certain amount of change can be made from a given collection of coins, or counting the number of optimal solutions to the coin change problem described above. (en)
  • 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)
  • 25بك المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (فبراير 2016) في الرياضيات وعلم الحاسوب، البرمجة الديناميكية (بالإنجليزية: Dynamic programming) هي طريقة لحل مسائل معقدة عن طريق تقسيمهن لمسائل فرعية أبسط. الفكرة وراء البرمجة الديناميكية بسطية. بشكل عام، لحل مسألة ما، نحن بحاجة إلى حل أجزاء مختلفة من المسألة (مسائل فرعية)، ومن ثم جمع حلول المسائل الفرعية للحصول على حل شامل. في كثير من الأحيان، كثير من هذه المسائل الفرعية هي في الواقع متشابهة. نهج البرمجة الديناميكية هو البحث عن حل كل مسألة فرعية مرة واحدة فقط، وبالتالي تقليل عدد الحسابات: حالما تم حساب حل مسألة فرعية ما، يتم حفظه، وفي المرة القادمة عند الحاجة للحل نفسه، يتم ببساطة استرجاعه. هذا النهج مفيد خصوصا عندما يكون عدد المسائل الفرعية المتكررة يمنو بشكل أسي كعلاقة بحجم المدخل. عندما تطبق هذه الطريقة فإنها تستغرق وقت أقل مما تستغرقه الطرق الأخري التي ليس لها ميزة حل المسائل الثانوية المتداخلة( مثل بحث العمق أولا). لحل مسألة ما، و باستخدام البرمجة الديناميكية نحتاج لحل اجزاء مختلفة من المسألة (مسائل ثانوية) بعدها يتم دمج بينهم للحصول علي الحل للمسالة بشكل عام.في كثير من الاحيان عند استخدام طريقة اكثر سذاجة فانه يكون هناك العديد من المسائل الثانوية التي تحل بشكل متكرر في البرمجة الديناميكية تهدف الي حل كل مسالة ثانوية لمرة واحدة فقط مما يؤدي الي تقليل عدد الحسابات. فانه بمجرد حل مسالة ثانوية فانه يتم تخزينها "، أوتوماتيكية مذكرة" لذا في المرة القادمة عندما نحتاج لنفس الحل فانه ببساطة يتم البحث عنه. هذا النهج مفيد خاصة عندما يكون عدد المسائل المتكررة يزداد بشكل مطرد كدالة في حجم المدخلات. تستخدم خوارزميات البرمجة الديناميكية لتعظيم الاستفادة ( مثلا للحصول علي اقصر طريق بين نقطتين او اسرع طريقه لضرب مصفوفات). خوارزميات البرمجة الديناميكية ستدرس الحلول السابقة للمسائل الثانويه وتقوم بدمجهلا للحصول علي افضل حل للمسائلة المراد حلها. يوجد هناك بدائل كثيرة لهذه الطريقة مثل خوارزمية جشعة والتي بها يتم الحصول علي الخيار الامثل الموضعي في كل فرع في الطريق. الخيار الامثل الموضعي ممكن ان يكون حل سيئ للمسالة بالكامل.بالرغم ان greedy algorithm لا تضمن الحل الامثل فانها في كثير من الاحيان تقدم حسابات اسرع. لحسن الحظ فان بعض من greedy algorithm (minimum spanning trees )اثبت انها تقدم الحل الافضل. علي سبيل, اذا كنا نريد الوصول من النقطة a الي النقطه b في ساعة الزروة فان البرمجة الديناميكية سوف تبحث عن النقاط القريبة من النقطة و a ثم يتم استخدامها للحصول علي اقرب طريق الي النقطة b ز علي الجانب الاخر فان سوف تبدا بالسواقة ومن ثم يتم البحث عن الطريق الاسرع عند كل تقاطع. كل ان تتخيل ان في هذه الطريقة قد لا تؤدي الي اسرع وقت للوصول حيث انه ممكن ان تختار طريق ظنا بانه الطريق الاسرع ثم تجد انك وقعت في ازمة مرورية. 2 -مثال: اقتصاد امثل (ar)
  • En informática, la programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas, como se describe a continuación. El matemático Richard Bellman inventó la programación dinámica en 1953 que se utiliza para optimizar problemas complejos que pueden ser discretizados y secuencializados. (es)
  • En informatique, la programmation dynamique est une méthode algorithmique pour résoudre des problèmes d'optimisation. Le concept a été introduit au début des années 1950 par Richard Bellman. À l'époque, le terme « programmation » signifie planification et ordonnancement. La programmation dynamique consiste à résoudre un problème en le décomposant en sous-problèmes, puis à résoudre les sous-problèmes, des plus petits aux plus grands en stockant les résultats intermédiaires. Elle a d'emblée connu un grand succès, car de nombreuses fonctions économiques de l'industrie étaient de ce type. (fr)
  • In Informatica, la programmazione dinamica è una tecnica di progettazione di algoritmi basata sulla divisione del problema in sottoproblemi e sull'utilizzo di sottostrutture ottimali. (it)
  • 動的計画法(どうてきけいかくほう、英: Dynamic Programming, DP)は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。 (ja)
  • Programowanie dynamiczne jest techniką lub strategią projektowania algorytmów, stosowaną przeważnie do rozwiązywania zagadnień optymalizacyjnych. Jest alternatywą dla niektórych zagadnień rozwiązywanych za pomocą algorytmów zachłannych. Wynalazcą techniki jest amerykański matematyk Richard Bellman, uhonorowany za to odkrycie medalem IEEE (ang. medal of honour) w 1979 roku. Programowanie dynamiczne opiera się na podziale rozwiązywanego problemu na podproblemy względem kilku parametrów. W odróżnieniu od techniki dziel i zwyciężaj podproblemy w programowaniu dynamicznym nie są rozłączne, ale musi je cechować własność optymalnej podstruktury. Zagadnienia odpowiednie dla programowania dynamicznego cechuje również to, że zastosowanie do nich metody siłowej (ang. brute force) prowadzi do ponadwielomianowej liczby rozwiązań podproblemów, podczas gdy sama liczba różnych podproblemów jest wielomianowa. Zazwyczaj jednym z parametrów definiujących podproblemy jest liczba elementów znajdujących się w rozpatrywanym problemie, drugim jest pewna wartość liczbowa, zmieniająca się w zakresie od 0 do największej stałej występującej w problemie. Możliwe są jednak bardziej skomplikowane dobory parametrów, a także większa ich liczba. Ponieważ jednak uzyskiwany algorytm zazwyczaj wymaga pamięci (i czasu) proporcjonalnego do iloczynu maksymalnych wartości wszystkich parametrów, stosowanie większej ilości parametrów niż 3-4 rzadko bywa praktyczne. Klucz do zaprojektowania algorytmu tą techniką leży w znalezieniu równania rekurencyjnego opisującego optymalną wartość funkcji celu dla danego problemu jako funkcji optymalnych wartości funkcji celu dla podproblemów o mniejszych rozmiarach. Programowanie dynamiczne znajduje optymalną wartość funkcji celu dla całego zagadnienia rozwiązując podproblemy od najmniejszego do największego i zapisując optymalne wartości w tablicy. Pozwala to zastąpić wywołania rekurencyjne odwołaniami do odpowiednich komórek wspomnianej tablicy i gwarantuje, że każdy podproblem jest rozwiązywany tylko raz. Rozwiązanie ostatniego z rozpatrywanych podproblemów jest na ogół wartością rozwiązania zadanego zagadnienia. Niejednokrotnie stosowanie techniki programowania dynamicznego daje w rezultacie algorytm pseudowielomianowy. Programowanie dynamiczne jest jedną z bardziej skutecznych technik rozwiązywania problemów NP-trudnych. Niejednokrotnie może być z sukcesem stosowana do względnie dużych przypadków problemów wejściowych, o ile stałe występujące w problemie są stosunkowo nieduże. Na przykład, w przypadku dyskretnego zagadnienia plecakowego jako parametry dynamiczne w metodzie programowania dynamicznego należy przyjąć rozmiar kolejno rozpatrywanych podzbiorów elementów oraz rozmiar plecaka, zmieniający się od 0 do wartości B danej w problemie. Programowanie dynamiczne może być również wykorzystywane jako alternatywna metoda rozwiązywania problemów zaliczanych do klasy P, o ile złożoność algorytmu wielomianowego nie jest satysfakcjonująca, a w praktyce, nawet dla dużych instancji problemu, wartości liczbowe występujące w problemie są niewielkie. (pl)
  • Programação dinâmica é um método para a construção de algoritmos para a resolução de problemas computacionais, em especial os de otimização combinatória. Ela é aplicável a problemas nos quais a solução ótima pode ser computada a partir da solução ótima previamente calculada e memorizada - de forma a evitar recálculo - de outros subproblemas que, sobrepostos, compõem o problema original. O que um problema de otimização deve ter para que a programação dinâmica seja aplicável são duas principais características: subestrutura ótima e superposição de subproblemas. Um problema apresenta uma subestrutura ótima quando uma solução ótima para o problema contém em seu interior soluções ótimas para subproblemas. A superposição de subproblemas acontece quando um algoritmo recursivo reexamina o mesmo problema muitas vezes. (pt)
  • Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой (англ.), выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить. Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико. Метод динамического программирования сверху — это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем. Динамическое программирование снизу включает в себя переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач. (ru)
  • 动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。 动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再合并子问题的解以得出原问题的解。 通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化(en:memoization)存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指數增長时特别有用。 (zh)
dbo:thumbnail
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 125297 (xsd:integer)
dbo:wikiPageRevisionID
  • 741609164 (xsd:integer)
dct:subject
http://purl.org/linguistics/gold/hypernym
rdf:type
rdfs:comment
  • En informática, la programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas, como se describe a continuación. El matemático Richard Bellman inventó la programación dinámica en 1953 que se utiliza para optimizar problemas complejos que pueden ser discretizados y secuencializados. (es)
  • En informatique, la programmation dynamique est une méthode algorithmique pour résoudre des problèmes d'optimisation. Le concept a été introduit au début des années 1950 par Richard Bellman. À l'époque, le terme « programmation » signifie planification et ordonnancement. La programmation dynamique consiste à résoudre un problème en le décomposant en sous-problèmes, puis à résoudre les sous-problèmes, des plus petits aux plus grands en stockant les résultats intermédiaires. Elle a d'emblée connu un grand succès, car de nombreuses fonctions économiques de l'industrie étaient de ce type. (fr)
  • In Informatica, la programmazione dinamica è una tecnica di progettazione di algoritmi basata sulla divisione del problema in sottoproblemi e sull'utilizzo di sottostrutture ottimali. (it)
  • 動的計画法(どうてきけいかくほう、英: Dynamic Programming, DP)は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。 (ja)
  • 动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。 动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再合并子问题的解以得出原问题的解。 通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化(en:memoization)存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指數增長时特别有用。 (zh)
  • In mathematics, management science, economics, computer science, and bioinformatics, dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions – ideally, using a memory-based data structure. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of a (hopefully) modest expenditure in storage space. (Each of the subproblem solutions is indexed in some way, typically based on the values of its input parameters, so as to facilitate its lookup.) The technique of storing solutions to subproblems ins (en)
  • 25بك المحتوى هنا ينقصه الاستشهاد بمصادر. يرجى إيراد مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (فبراير 2016) في الرياضيات وعلم الحاسوب، البرمجة الديناميكية (بالإنجليزية: Dynamic programming) هي طريقة لحل مسائل معقدة عن طريق تقسيمهن لمسائل فرعية أبسط. عندما تطبق هذه الطريقة فإنها تستغرق وقت أقل مما تستغرقه الطرق الأخري التي ليس لها ميزة حل المسائل الثانوية المتداخلة( مثل بحث العمق أولا). 2 -مثال: اقتصاد امثل (ar)
  • 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)
  • Programowanie dynamiczne jest techniką lub strategią projektowania algorytmów, stosowaną przeważnie do rozwiązywania zagadnień optymalizacyjnych. Jest alternatywą dla niektórych zagadnień rozwiązywanych za pomocą algorytmów zachłannych. Wynalazcą techniki jest amerykański matematyk Richard Bellman, uhonorowany za to odkrycie medalem IEEE (ang. medal of honour) w 1979 roku. (pl)
  • Programação dinâmica é um método para a construção de algoritmos para a resolução de problemas computacionais, em especial os de otimização combinatória. Ela é aplicável a problemas nos quais a solução ótima pode ser computada a partir da solução ótima previamente calculada e memorizada - de forma a evitar recálculo - de outros subproblemas que, sobrepostos, compõem o problema original. (pt)
  • Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой (англ.), выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить. (ru)
rdfs:label
  • Dynamic programming (en)
  • برمجة ديناميكية (ar)
  • Dynamische Programmierung (de)
  • Programación dinámica (es)
  • Programmation dynamique (fr)
  • Programmazione dinamica (it)
  • 動的計画法 (ja)
  • Programowanie dynamiczne (pl)
  • Programação dinâmica (pt)
  • Динамическое программирование (ru)
  • 动态规划 (zh)
owl:differentFrom
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:knownFor of
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is owl:differentFrom of
is foaf:primaryTopic of