Dynamické programování
Dynamisk programmering
Динамічне програмування
Pemrograman dinamis
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. Problemas de programação dinâmica podem ser abordados de forma top-down ou bottom-up.
Динамічне програмування — розділ математики, який присвячено теорії і методам розв'язання багатокрокових задач оптимального управління. У динамічному програмуванні для керованого процесу серед множини усіх допустимих управлінь шукають оптимальне у сенсі деякого критерію тобто таке яке призводить до екстремального (найбільшого або найменшого) значення цільової функції — деякої числової характеристики процесу. Під багатоступеневістю розуміють або багатоступеневу структуру процесу, або розподілення управління на ряд послідовних етапів (ступенів, кроків), що відповідають, як правило, різним моментам часу. Таким чином, в назві «Динамічне програмування» під «програмуванням» розуміють «ухвалення рішень», «планування», а слово «динамічне» вказує на суттєве значення часу та порядку виконання операц
Ο δυναμικός προγραμματισμός αποτελεί μία υπολογιστική μέθοδο η οποία εφαρμόζεται σε προβλήματα που δεν είναι δυνατόν να λυθούν με "άπληστες μεθόδους" (βλ. Greedy algorithm) ή τη μέθοδο "διαίρει και βασίλευε". Θεμέλιο του δυναμικού προγραμματισμού αποτελεί η αρχή βελτιστοποίησης. Είναι μία μέθοδος που είναι εφαρμόσιμη όταν τα υποπροβλήματα που υπάρχουν δεν είναι ανεξάρτητα μεταξύ τους. Ένας αλγόριθμος που είναι προϊόν του δυναμικού προγραμματισμού, επιλύει μία φορά κάθε υποπρόβλημα και αποθηκεύει αυτή τη λύση σε έναν πίνακα, στον οποίον θα καταφεύγει κάθε φορά που συναντά το συγκεκριμένο πρόβλημα. Αποτελεί μία πολύ ισχυρή τεχνική για αλγοριθμική επίλυση προβλημάτων.
Informatikan, programazio dinamikoa algoritmo baten exekuzio denbora murrizteko metodoa da. Horretarako azpi-problema gainjarriak eta azpi-egitura optimoak erabiltzen ditu. matematikariak programazio dinamikoa asmatu zuen 1953. urtean, problema konplexuak optimizatzeko, hauek sekuentzializatuz eta diskretatuz.
動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。
Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.
في الرياضيات وعلم الحاسوب، البرمجة الديناميكية (بالإنجليزية: Dynamic programming) هي طريقة لحل مسائل معقدة عن طريق تقسيمها لمسائل فرعية أبسط. الفكرة وراء البرمجة الديناميكية بسيطة. بشكل عام، لحل مسألة ما، نحن بحاجة إلى حل أجزاء مختلفة من المسألة (مسائل فرعية)، ومن ثم جمع حلول المسائل الفرعية للحصول على حل شامل. في كثير من الأحيان، كثير من هذه المسائل الفرعية هي في الواقع متشابهة. نهج البرمجة الديناميكية هو البحث عن حل كل مسألة فرعية مرة واحدة فقط، وبالتالي تقليل عدد الحسابات: حالما تم حساب حل مسألة فرعية ما، يتم حفظه، وفي المرة القادمة عند الحاجة للحل نفسه، يتم ببساطة استرجاعه. هذا النهج مفيد خصوصا عندما يكون عدد المسائل الفرعية المتكررة ينمو بشكل أسي كعلاقة بحجم المدخل.
Dynamisk programmering är en generell metod för att lösa kombinatoriska optimeringsproblem och kan lättsamt beskrivas som "rekursion plus tabellering". Genom att systematiskt beräkna lösningar till delproblem, spara dessa på ett effektivt sätt, samt att låta alla dellösningar beräknas genom att utnyttja andra dellösningar, kan man hitta effektiva algoritmer för annars svårlösta problem. Ett klassiskt exempel är som har en effektiv lösning med hjälp av dynamisk programmering, och har kommit att bli viktig inom bioinformatiken där molekylära sekvenser jämförs med hjälp av en linjering.
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 y , 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.
Pemrograman dinamis (bahasa Inggris: dynamic programming) adalah sebuah metode pemecahan masalah yang digunakan dalam ilmu komputer, matematika dan ekonomi. Inti dari metode ini adalah membuat sebuah masalah kompleks menjadi masalah kecil yang lebih sederhana, dan menyelesaikan masalah kecil tersebut. Lalu, menggunakan solusi dari masalah kecil tersebut, seseorang dapat menyelesaikan masalah awal. Pemrograman dinamis dapat digunakan ketika masalah yang didapatkan agar dapat dipecah lagi menjadi masalah-masalah kecil yang seluruhnya mirip. — Bellman, 1957
Dynamické programování je metoda pro efektivní řešení určitých optimalizačních úloh. Lze jej použít pro řešení úloh, které lze rozdělit na podúlohy, jejichž optimální řešení lze použít při řešení původní úlohy. Princip dynamického programování spočívá v rekurzivním dělení úlohy na menší části, které se řeší ve vhodném pořadí, jejich výsledky se zaznamenávají a jsou použity pro řešení složitějších podúloh včetně původní úlohy. Dělíme je na: * diskrétní vs. spojité * deterministické vs. nedeterministické (stochastické) * jednoparametrické vs. víceparametrické
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, comme la conduite et l'optimisation de procédés chimiques, ou la gestion de stocks.
In Informatica la programmazione dinamica è una tecnica di progettazione di algoritmi basata sulla divisione del problema in sottoproblemi e sull'utilizzo di sottostrutture ottimali.
수학과 컴퓨터 공학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
Dynamische Programmierung ist eine Methode zum algorithmischen Lösen eines Optimierungsproblems durch Aufteilung in Teilprobleme und systematische Speicherung von Zwischenresultaten. 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.
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. If sub-problems can be nested recursively inside larger problems, so that dynamic programming methods are applicable, then there is a relation between the value of the larger problem and the values of the sub-problems. In the optimization literature this relationship is called the Bellman equation.
动态规划（英語：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和性质的问题，动态规划方法所耗时间往往远少于朴素解法。 动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指數增長时特别有用。
Dins de l'entorn de la informàtica, la programació dinàmica és un mètode per a reduir el temps d'execució d'un algorisme mitjançant la utilització de i , com es descriu a continuació. El matemàtic Richard Bellman va inventar la programació dinàmica el 1953. 1. * Dividir el problema en subproblemes més petits. 2. * Resoldre aquests problemes de manera òptima fent servir aquest procés de tres passos recursivament. 3. * Emprar aquestes solucions òptimes per a construir una solució òptima al problema original. En resum, la programació dinàmica fa ús de: * * *
Dynamische Programmierung ist eine Methode zum algorithmischen Lösen eines Optimierungsproblems durch Aufteilung in Teilprobleme und systematische Speicherung von Zwischenresultaten. 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 erfolgreich eingesetzt werden, wenn ein 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 . 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 der Lagrange-Funktion in die Hamilton-Funktion mit Hilfe der Legendre-Transformation.
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. Problemas de programação dinâmica podem ser abordados de forma top-down ou bottom-up.
في الرياضيات وعلم الحاسوب، البرمجة الديناميكية (بالإنجليزية: Dynamic programming) هي طريقة لحل مسائل معقدة عن طريق تقسيمها لمسائل فرعية أبسط. الفكرة وراء البرمجة الديناميكية بسيطة. بشكل عام، لحل مسألة ما، نحن بحاجة إلى حل أجزاء مختلفة من المسألة (مسائل فرعية)، ومن ثم جمع حلول المسائل الفرعية للحصول على حل شامل. في كثير من الأحيان، كثير من هذه المسائل الفرعية هي في الواقع متشابهة. نهج البرمجة الديناميكية هو البحث عن حل كل مسألة فرعية مرة واحدة فقط، وبالتالي تقليل عدد الحسابات: حالما تم حساب حل مسألة فرعية ما، يتم حفظه، وفي المرة القادمة عند الحاجة للحل نفسه، يتم ببساطة استرجاعه. هذا النهج مفيد خصوصا عندما يكون عدد المسائل الفرعية المتكررة ينمو بشكل أسي كعلاقة بحجم المدخل. عندما تطبق هذه الطريقة فإنها تستغرق وقت أقل مما تستغرقه الطرق الأخرى التي ليس لها ميزة حل المسائل الثانوية المتداخلة( مثل بحث العمق أولا). لحل مسألة ما، و باستخدام البرمجة الديناميكية نحتاج لحل أجزاء مختلفة من المسألة (مسائل ثانوية) بعدها يتم دمج بينهم للحصول على الحل للمسألة بشكل عام.في كثير من الأحيان عند استخدام طريقة أكثر سذاجة فإنه يكون هناك العديد من المسائل الثانوية التي تحل بشكل متكرر في البرمجة الديناميكية تهدف إلي حل كل مسالة ثانوية لمرة واحدة فقط مما يؤدي إلى تقليل عدد الحسابات. فإنه بمجرد حل مسالة ثانوية فإنه يتم تخزينها "، أوتوماتيكية مذكرة" لذا في المرة القادمة عندما نحتاج لنفس الحل فإنه ببساطة يتم البحث عنه. هذا النهج مفيد خاصة عندما يكون عدد المسائل المتكررة يزداد بشكل مطرد كدالة في حجم المدخلات. تستخدم خوارزميات البرمجة الديناميكية لتعظيم الاستفادة ( مثلا للحصول علي أقصر طريق بين نقطتين أو أسرع طريقة لضرب مصفوفات). خوارزميات البرمجة الديناميكية ستدرس الحلول السابقة للمسائل الثانويه وتقوم بدمجها للحصول على أفضل حل للمسألة المراد حلها. يوجد هناك بدائل كثيرة لهذه الطريقة مثل خوارزمية جشعة والتي بها يتم الحصول على الخيار الأمثل الموضعي في كل فرع في الطريق. الخيار الأمثل الموضعي ممكن أن يكون حل سيئ للمسألة بالكامل.بالرغم ان greedy algorithm لا تضمن الحل الامثل فإنها في كثير من الأحيان تقدم حسابات أسرع. لحسن الحظ فان بعض من greedy algorithm (minimum spanning trees )اثبت انها تقدم الحل الأفضل. علي سبيل المثال, إذا كنا نريد الوصول من النقطة a إلى النقطة b في ساعة الذروة فإن البرمجة الديناميكية سوف تبحث عن النقاط القريبة من النقطة و a ثم يتم استخدامها للحصول على أقرب طريق إلى النقطة b على الجانب الآخر فإنك سوف تبدأ بالسواقة ومن ثم يتم البحث عن الطريق الأسرع عند كل تقاطع. كل ان تتخيل ان في هذه الطريقة قد لا تؤدي الي اسرع وقت للوصول حيث انه ممكن ان تختار طريق ظنا بأنه الطريق الاسرع ثم تجد أنك وقعت في أزمة مرورية. 2- مثال: اقتصاد امثل
Pemrograman dinamis (bahasa Inggris: dynamic programming) adalah sebuah metode pemecahan masalah yang digunakan dalam ilmu komputer, matematika dan ekonomi. Inti dari metode ini adalah membuat sebuah masalah kompleks menjadi masalah kecil yang lebih sederhana, dan menyelesaikan masalah kecil tersebut. Lalu, menggunakan solusi dari masalah kecil tersebut, seseorang dapat menyelesaikan masalah awal. Pemrograman dinamis dapat digunakan ketika masalah yang didapatkan agar dapat dipecah lagi menjadi masalah-masalah kecil yang seluruhnya mirip. , seorang matematikawan Amerika Serikat menggunakan istilah ini pada tahun 1940-an, ketika dia ingin menyelesaikan sebuah masalah di bidang . Dia juga menyatakan Bellman's Principle of Optimality: apapun keadaan awal dan keputusan awal, keputusan optimum selanjutnya membentuk kebijakan optimum dengan memperhatikan keadaan yang dihasilkan oleh keputusan awal. — Bellman, 1957
Динамічне програмування — розділ математики, який присвячено теорії і методам розв'язання багатокрокових задач оптимального управління. У динамічному програмуванні для керованого процесу серед множини усіх допустимих управлінь шукають оптимальне у сенсі деякого критерію тобто таке яке призводить до екстремального (найбільшого або найменшого) значення цільової функції — деякої числової характеристики процесу. Під багатоступеневістю розуміють або багатоступеневу структуру процесу, або розподілення управління на ряд послідовних етапів (ступенів, кроків), що відповідають, як правило, різним моментам часу. Таким чином, в назві «Динамічне програмування» під «програмуванням» розуміють «ухвалення рішень», «планування», а слово «динамічне» вказує на суттєве значення часу та порядку виконання операцій в процесах і методах, що розглядаються. Методи динамічного програмування є складовою частиною методів, які використовуються при дослідженні операцій, і використовуються як у задачах оптимального планування, так і при розв'язанні різних технічних проблем (наприклад, у задачах визначення оптимальних розмірів ступенів багатоступеневих ракет, у задачах оптимального проектування прокладення доріг та ін.) Методи динамічного програмування використовуються не лише в дискретних, але і в неперервних керованих процесах, наприклад, в таких процесах, коли в кожен момент певного проміжку часу необхідно ухвалювати рішення. Динамічне програмування також дало новий підхід до задач варіаційного числення. Хоча метод динамічного програмування суттєво спрощує вихідні задачі, та безпосереднє його використання, як правило, пов'язане з громіздкими обчисленнями. Для подолання цих труднощів розробляються наближені методи динамічного програмування.
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. While some decision problems cannot be taken apart this way, decisions that span several points in time do often break apart recursively. Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure. If sub-problems can be nested recursively inside larger problems, so that dynamic programming methods are applicable, then there is a relation between the value of the larger problem and the values of the sub-problems. In the optimization literature this relationship is called the Bellman equation.
Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить. Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико. Метод динамического программирования сверху — это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем. Динамическое программирование снизу включает в себя переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач.
Dins de l'entorn de la informàtica, la programació dinàmica és un mètode per a reduir el temps d'execució d'un algorisme mitjançant la utilització de i , com es descriu a continuació. El matemàtic Richard Bellman va inventar la programació dinàmica el 1953. El concepte de Subestructura òptima vol dir que es poden fer servir solucions òptimes de subproblemes per a trobar la solució òptima del problema en el seu conjunt. Per exemple, el camí més curt entre dos vèrtexs d'un graf es pot trobar calculant primer el camí més curt a l'objectiu des de tots els vèrtexs adjacents al de partida, i després fent servir aquestes solucions per a triar el millor camí de tots ells. En general, es poden resoldre problemes amb subestructures òptimes seguint aquests tres passos: 1. * Dividir el problema en subproblemes més petits. 2. * Resoldre aquests problemes de manera òptima fent servir aquest procés de tres passos recursivament. 3. * Emprar aquestes solucions òptimes per a construir una solució òptima al problema original. Els subproblemes es resolen al seu torn dividint-los en subproblemes més petits fins que s'assoleixi el cas fàcil, on la solució al problema és trivial. Direm que un problema té subproblemes superposats quan fem servir un mateix subproblema per a resoldre diferents problemes majors. Per exemple, en la successió de Fibonacci (F 3 = F 1 +F 2 i F 4 = F 2 +F 3 ) calcular cada terme suposa calcular F 2 . Com que per a calcular F 5 calen tant F 3 com F 4 , aleshores una mala implementació per a calcular F 5 acabarà calculant F 2 dues o més vegades. Això passa sempre que hi hagi subproblemes superposats: una mala implementació pot acabar desaprofitant temps recalculant les solucions òptimes a subproblemes que ja han estat resolts anteriorment. Això es pot evitar guardant les solucions que ja hem calculat. Llavors, si necessitem resoldre el mateix problema més tard, podem obtenir la solució de la llista de solucions calculades i reutilitzar-la. Aquest acostament al problema es diu (en anglès ""). Si estem segurs que no tornarem a necessitar una solució en concret, la podem descartar per estalviar espai. En alguns casos, podem calcular les solucions d'aquells problemes que sabem que més endavant necessitarem. En resum, la programació dinàmica fa ús de: * * * La programació dinàmica pren base normalment d'un dels dos següents enfocaments: * Top-down : El problema es divideix en subproblemes, els quals es resolen emmagatzemant les solucions per si més endavant fessin falta. És una combinació de i recursió. * Bottom-up : Tots els subproblemes que prèviament ens calgui resoldre, es resolen per endavant i després es fan servir per resoldre les solucions a problemes majors. Aquest enfocament és lleugerament millor en consum d'espai i trucades (crides) a funcions, però de vegades resulta poc intuïtiu trobar tots els subproblemes que ens calen per a resoldre un problema donat. Originalment, el terme de programació dinàmica es referia a la resolució de certs problemes i operacions fora de l'àmbit de l'Enginyeria Informàtica, de la mateixa manera que feia la programació lineal. Aquell context no té relació amb la programació d'ordinadors en absolut, el nom és una coincidència. El terme també el va fer servir en els anys 40 Richard Bellman, un matemàtic nord-americà, per descriure el procés de resolució de problemes on cal calcular la millor solució consecutivament. Alguns llenguatges de programació , sobretot Haskell, poden fer servir la automàticament sobre funcions amb un conjunt concret d'arguments, per accelerar-ne el procés d'avaluació. Això només és possible en funcions que no tinguin , una cosa que passa a Haskell però no tant en altres llenguatges.