| dbo:abstract
|
- 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é (cs)
- 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. (ca)
- البرمجة الديناميكية (بالإنجليزية: Dynamic programming) في الرياضيات وعلم الحاسوب، هي طريقة لحل مسائل معقدة وصعبة الحل عن طريق تقسيمها لمسائل فرعية أبسط وسهلة الحل. الفكرة وراء البرمجة الديناميكية بسيطة. بشكل عام، لحل مسألة ما، نحن بحاجة إلى حل أجزاء مختلفة من المسألة (مسائل فرعية)، ومن ثم جمع حلول المسائل الفرعية للحصول على حل شامل. في كثير من الأحيان، كثير من هذه المسائل الفرعية هي في الواقع متشابهة. نهج البرمجة الديناميكية هو البحث عن حل كل مسألة فرعية مرة واحدة فقط، وبالتالي تقليل عدد الحسابات: حالما يتم حساب حل مسألة فرعية ما، يتم حفظه، وفي المرة القادمة عند الحاجة للحل نفسه، يتم ببساطة استرجاعه. هذا النهج مفيد خصوصاً عندما يكون عدد المسائل الفرعية المتكررة ينمو بشكل أُسي كعلاقة بحجم المدخل. عندما تطبق هذه الطريقة فإنها تستغرق وقتاً أقل مما تستغرقه الطرق الأخرى التي ليس لها ميزة حل المسائل الثانوية المتداخلة (مثل بحث العمق أولا). لحل مسألة ما، وباستخدام البرمجة الديناميكية نحتاج لحل أجزاء مختلفة من المسألة (مسائل ثانوية) بعدها يتم الدمج بينهم للحصول على الحل للمسألة بشكل عام. في الكثير من الأحيان عند استخدام طريقة خوارزمية جشعة فإنه يكون هناك العديد من المسائل الثانوية التي تحل بشكل متكرر. البرمجة الديناميكية تهدف إلى حل كل مسألة ثانوية لمرة واحدة فقط مما يؤدي إلى تقليل عدد الحسابات. فإنه بمجرد حل مسألة ثانوية فإنه يتم تخزينها «أوتوماتيكية مذكرة» لذا في المرة القادمة عندما نحتاج لنفس الحل فإنه ببساطة يتم البحث عنه. هذا النهج مفيد خاصةً عندما يكون عدد المسائل المتكررة يزداد بشكل مفرط كدالة في حجم المدخلات. تستخدم خوارزميات البرمجة الديناميكية لتعظيم الإستفادة (مثلاً للحصول على أقصر طريق بين نقطتين أو أسرع طريقة لضرب مصفوفات). خوارزميات البرمجة الديناميكية ستدرس الحلول السابقة للمسائل الثانويه وتقوم بدمجها للحصول على أفضل حل للمسألة المراد حلها. يوجد هناك بدائل كثيرة لهذه الطريقة مثل خوارزمية جشعة والتي بها يتم الحصول على الخيار الأمثل الموضعي في كل فرع في الطريق. الخيار الأمثل الموضعي ممكن أن يكون حل سيئ للمسألة بالكامل.بالرغم ان greedy algorithm لا تضمن الحل الامثل فإنها في كثير من الأحيان تقدم حسابات أسرع. لحسن الحظ فإن بعض من greedy algorithm (minimum spanning trees) أثبت أنها تقدم الحل الأفضل. على سبيل المثال، إذا كنا نريد الوصول من النقطة a إلى النقطة b في ساعة الذروة فإن البرمجة الديناميكية سوف تبحث عن النقاط القريبة من النقطة وa ثم يتم استخدامها للحصول على أقرب طريق إلى النقطة b على الجانب الآخر فإنك سوف تبدأ بالقيادة ومن ثم يتم البحث عن الطريق الأسرع عند كل تقاطع. لك أن تتخيل أن هذه الطريقة قد لا تؤدي إلى أسرع وقت للوصول حيث إنه من الممكن أن تختار طريقاً ظناً بأنه الطريق الأسرع ثم تجد أنك وقعت في أزمة مرورية. 2- مثال: اقتصاد أمثل (ar)
- Ο δυναμικός προγραμματισμός αποτελεί μία υπολογιστική μέθοδο η οποία εφαρμόζεται σε προβλήματα που δεν είναι δυνατόν να λυθούν με "άπληστες μεθόδους" (βλ. Greedy algorithm) ή τη μέθοδο "διαίρει και βασίλευε". Θεμέλιο του δυναμικού προγραμματισμού αποτελεί η αρχή βελτιστοποίησης. Είναι μία μέθοδος που είναι εφαρμόσιμη όταν τα υποπροβλήματα που υπάρχουν δεν είναι ανεξάρτητα μεταξύ τους. Ένας αλγόριθμος που είναι προϊόν του δυναμικού προγραμματισμού, επιλύει μία φορά κάθε υποπρόβλημα και αποθηκεύει αυτή τη λύση σε έναν πίνακα, στον οποίον θα καταφεύγει κάθε φορά που συναντά το συγκεκριμένο πρόβλημα. Αποτελεί μία πολύ ισχυρή τεχνική για αλγοριθμική επίλυση προβλημάτων. (el)
- 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 der Zielfunktion zu einem bestimmten Zeitpunkt betrachten. Man fragt sich dann, welche Gleichung die optimale Lösung erfüllen muss, damit das Funktional 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. (de)
- 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. (en)
- 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. (eu)
- 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. (fr)
- 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. (es)
- Pemrograman dinamis (bahasa Inggris: dynamic programming) adalah metode dan metode pemrograman komputer. Metode ini dikembangkan oleh pada 1950-an dan telah digunakan di berbagai bidang, mulai dari teknik kedirgantaraan hingga ekonomi. Dalam kedua konteks ini mengacu pada penyederhanaan masalah yang rumit dengan memecahnya menjadi sub-masalah yang lebih sederhana secara rekursif. Meskipun beberapa masalah keputusan tidak dapat dipisahkan dengan cara ini, keputusan yang mencakup beberapa titik waktu sering kali pecah secara rekursif. Begitu pula dalam ilmu komputer, jika suatu masalah dapat diselesaikan secara optimal dengan memecahnya menjadi sub-sub masalah dan kemudian secara rekursif mencari solusi optimal untuk sub masalah tersebut, maka dikatakan memiliki . Jika sub-masalah dapat disarangkan secara rekursif di dalam masalah yang lebih besar, sehingga metode pemrograman dinamis dapat diterapkan, maka ada hubungan antara nilai masalah yang lebih besar dengan nilai-nilai sub-masalah tersebut. Dalam literatur optimasi, hubungan ini disebut . (in)
- 수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. (ko)
- 動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。 (ja)
- 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)
- Programowanie dynamiczne – technika lub strategia projektowania algorytmów, stosowana 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 (ang. IEEE Medal of Honor) przez IEEE 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)
- Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико. Метод динамического программирования сверху — это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем. Динамическое программирование снизу включает в себя переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач. (ru)
- 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. (pt)
- 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. (sv)
- 动态规划（英語：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和性质的问题，动态规划方法所耗时间往往远少于朴素解法。 动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指數增長时特别有用。 (zh)
- Динамічне програмування — розділ математики, який присвячено теорії та методам розв'язання багатокрокових задач оптимального управління. У динамічному програмуванні, для керованого процесу серед множини усіх допустимих управлінь шукають оптимальне, у сенсі деякого критерію, тобто таке, яке призводить до екстремального (найбільшого або найменшого) значення цільової функції — деякої числової характеристики процесу. Під багатоступеневістю розуміють або багатоступеневу структуру процесу, або розподілення управління на ряд послідовних етапів (ступенів, кроків), що відповідають, як правило, різним моментам часу. Таким чином, в назві «Динамічне програмування» під «програмуванням» розуміють «ухвалення рішень», «планування», а слово «динамічне» вказує на суттєве значення часу та порядку виконання операцій в процесах і методах, що розглядаються. Методи динамічного програмування є складовою частиною методів, які використовуються при дослідженні операцій, і використовуються як у задачах оптимального планування, так і при розв'язанні різних технічних проблем (наприклад, у задачах визначення оптимальних розмірів ступенів багатоступеневих ракет, у задачах оптимального проектування прокладення доріг та ін.) Методи динамічного програмування використовуються не лише в дискретних, але і в неперервних керованих процесах, наприклад, в таких процесах, коли в кожен момент певного проміжку часу необхідно ухвалювати рішення. Динамічне програмування також дало новий підхід до задач варіаційного числення. Хоча метод динамічного програмування суттєво спрощує вихідні задачі, та безпосереднє його використання, як правило, пов'язане з громіздкими обчисленнями. Для подолання цих труднощів розробляються наближені методи динамічного програмування. (uk)
|
| rdfs:comment
|
- 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é (cs)
- Ο δυναμικός προγραμματισμός αποτελεί μία υπολογιστική μέθοδο η οποία εφαρμόζεται σε προβλήματα που δεν είναι δυνατόν να λυθούν με "άπληστες μεθόδους" (βλ. Greedy algorithm) ή τη μέθοδο "διαίρει και βασίλευε". Θεμέλιο του δυναμικού προγραμματισμού αποτελεί η αρχή βελτιστοποίησης. Είναι μία μέθοδος που είναι εφαρμόσιμη όταν τα υποπροβλήματα που υπάρχουν δεν είναι ανεξάρτητα μεταξύ τους. Ένας αλγόριθμος που είναι προϊόν του δυναμικού προγραμματισμού, επιλύει μία φορά κάθε υποπρόβλημα και αποθηκεύει αυτή τη λύση σε έναν πίνακα, στον οποίον θα καταφεύγει κάθε φορά που συναντά το συγκεκριμένο πρόβλημα. Αποτελεί μία πολύ ισχυρή τεχνική για αλγοριθμική επίλυση προβλημάτων. (el)
- 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. (eu)
- 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. (fr)
- 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. (es)
- 수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. (ko)
- 動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。 (ja)
- 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)
- 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. (sv)
- 动态规划（英語：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和性质的问题，动态规划方法所耗时间往往远少于朴素解法。 动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指數增長时特别有用。 (zh)
- البرمجة الديناميكية (بالإنجليزية: Dynamic programming) في الرياضيات وعلم الحاسوب، هي طريقة لحل مسائل معقدة وصعبة الحل عن طريق تقسيمها لمسائل فرعية أبسط وسهلة الحل. الفكرة وراء البرمجة الديناميكية بسيطة. بشكل عام، لحل مسألة ما، نحن بحاجة إلى حل أجزاء مختلفة من المسألة (مسائل فرعية)، ومن ثم جمع حلول المسائل الفرعية للحصول على حل شامل. في كثير من الأحيان، كثير من هذه المسائل الفرعية هي في الواقع متشابهة. نهج البرمجة الديناميكية هو البحث عن حل كل مسألة فرعية مرة واحدة فقط، وبالتالي تقليل عدد الحسابات: حالما يتم حساب حل مسألة فرعية ما، يتم حفظه، وفي المرة القادمة عند الحاجة للحل نفسه، يتم ببساطة استرجاعه. هذا النهج مفيد خصوصاً عندما يكون عدد المسائل الفرعية المتكررة ينمو بشكل أُسي كعلاقة بحجم المدخل. (ar)
- 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:
*
*
* (ca)
- 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. (en)
- 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. (de)
- Pemrograman dinamis (bahasa Inggris: dynamic programming) adalah metode dan metode pemrograman komputer. Metode ini dikembangkan oleh pada 1950-an dan telah digunakan di berbagai bidang, mulai dari teknik kedirgantaraan hingga ekonomi. Jika sub-masalah dapat disarangkan secara rekursif di dalam masalah yang lebih besar, sehingga metode pemrograman dinamis dapat diterapkan, maka ada hubungan antara nilai masalah yang lebih besar dengan nilai-nilai sub-masalah tersebut. Dalam literatur optimasi, hubungan ini disebut . (in)
- Programowanie dynamiczne – technika lub strategia projektowania algorytmów, stosowana 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 (ang. IEEE Medal of Honor) przez IEEE 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. Problemas de programação dinâmica podem ser abordados de forma top-down ou bottom-up. (pt)
- Динамічне програмування — розділ математики, який присвячено теорії та методам розв'язання багатокрокових задач оптимального управління. У динамічному програмуванні, для керованого процесу серед множини усіх допустимих управлінь шукають оптимальне, у сенсі деякого критерію, тобто таке, яке призводить до екстремального (найбільшого або найменшого) значення цільової функції — деякої числової характеристики процесу. Під багатоступеневістю розуміють або багатоступеневу структуру процесу, або розподілення управління на ряд послідовних етапів (ступенів, кроків), що відповідають, як правило, різним моментам часу. Таким чином, в назві «Динамічне програмування» під «програмуванням» розуміють «ухвалення рішень», «планування», а слово «динамічне» вказує на суттєве значення часу та порядку виконання о (uk)
- Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить. (ru)
|
