| dbo:abstract
|
- Problém v matematické informatice má optimální podstrukturu, pokud lze jeho optimální řešení zkonstruovat z optimálních řešení jeho podproblémů. Pro řešení problémů s optimální podstrukturou lze s výhodou používat metody dynamického programování nebo hladové algoritmy. Hladové algoritmy se pro řešení problémů s optimální podstrukturou používají obvykle tehdy, když lze dokázat, že jsou optimální v každém kroku. Pokud tomu tak není, ale problém má vlastnost , používá se dynamické programování. Pokud problém nevykazuje žádnou z uvedených vlastností, bývá nejlepším způsobem řešení prosté prohledávání stavového prostoru, které může být časově náročné. Při aplikaci dynamického programování na matematickou optimalizaci je Bellmanův založen na myšlence, že pro vyřešení dynamického optimalizačního problému pro interval ts až te je třeba vyřešit podproblémy začínající v časech tm, kde tsme, což je případ optimální podstruktury. Princip optimality se používá pro odvození Bellmanovy rovnice, která popisuje, jak hodnota problému začínajícího v čase ts závisí na hodnotě problému začínajícího v čase tm. (cs)
- In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. This property is used to determine the usefulness of greedy algorithms for a problem. Typically, a greedy algorithm is used to solve a problem with optimal substructure if it can be proven by induction that this is optimal at each step. Otherwise, provided the problem exhibits overlapping subproblems as well, divide-and-conquer methods or dynamic programming may be used. If there are no appropriate greedy algorithms and the problem fails to exhibit overlapping subproblems, often a lengthy but straightforward search of the solution space is the best alternative. In the application of dynamic programming to mathematical optimization, Richard Bellman's Principle of Optimality is based on the idea that in order to solve a dynamic optimization problem from some starting period t to some ending period T, one implicitly has to solve subproblems starting from later dates s, where t. This is an example of optimal substructure. The Principle of Optimality is used to derive the Bellman equation, which shows how the value of the problem starting from t is related to the value of the problem starting from s. (en)
- In informatica, un problema possiede una sottostruttura ottimale se è possibile costruire efficientemente una soluzione ottimale a partire dalle soluzioni ottimali dei suoi sottoproblemi. Questa proprietà è necessaria per poter utilizzare tecniche di programmazione dinamica o algoritmi greedy. Ricerca del cammino minimo in un grafo utilizzando le sottostrutture ottimali. Un esempio di sottostrutture ottimali è la ricerca del cammino minimo tra due vertici in un grafo, come illustrato nella figura accanto: prima si trova il cammino minimo dal vertice di arrivo a tutti i vertici vicini a quello di partenza (ripetutamente e con lo stesso metodo); poi si sceglie il cammino che minimizza il peso totale degli archi. Solitamente, un problema con sottostruttura ottimale viene risolto con un algoritmo greedy. Nel caso in cui il problema possieda anche si può usare un algoritmo dinamico. (it)
- Własność optymalnej podstruktury – własność problemów, które można rozwiązywać za pomocą algorytmów, mówiąca, że dany problem ma własność optymalnej podstruktury, jeżeli jego optymalne rozwiązanie jest funkcją optymalnych rozwiązań podproblemów. Jeżeli problem wykazuje własność optymalnej podstruktury, to zazwyczaj można znaleźć rozwiązujący go algorytm dynamiczny, a czasem (także) zachłanny. (pl)
- Оптимáльна підструктýра — В інформатиці, задача має оптимальну підструктуру, якщо її оптимальній розв'язок можна ефективно одержати з оптимальних розв'язків її підзадач. Оптимальність підстуктури визначає застосовність динамічного програмування та жадібних алгоритмів до задачі. (uk)
|
| rdfs:comment
|
- Własność optymalnej podstruktury – własność problemów, które można rozwiązywać za pomocą algorytmów, mówiąca, że dany problem ma własność optymalnej podstruktury, jeżeli jego optymalne rozwiązanie jest funkcją optymalnych rozwiązań podproblemów. Jeżeli problem wykazuje własność optymalnej podstruktury, to zazwyczaj można znaleźć rozwiązujący go algorytm dynamiczny, a czasem (także) zachłanny. (pl)
- Оптимáльна підструктýра — В інформатиці, задача має оптимальну підструктуру, якщо її оптимальній розв'язок можна ефективно одержати з оптимальних розв'язків її підзадач. Оптимальність підстуктури визначає застосовність динамічного програмування та жадібних алгоритмів до задачі. (uk)
- Problém v matematické informatice má optimální podstrukturu, pokud lze jeho optimální řešení zkonstruovat z optimálních řešení jeho podproblémů. Pro řešení problémů s optimální podstrukturou lze s výhodou používat metody dynamického programování nebo hladové algoritmy. (cs)
- In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. This property is used to determine the usefulness of greedy algorithms for a problem. (en)
- In informatica, un problema possiede una sottostruttura ottimale se è possibile costruire efficientemente una soluzione ottimale a partire dalle soluzioni ottimali dei suoi sottoproblemi. Questa proprietà è necessaria per poter utilizzare tecniche di programmazione dinamica o algoritmi greedy. Ricerca del cammino minimo in un grafo utilizzando le sottostrutture ottimali. Solitamente, un problema con sottostruttura ottimale viene risolto con un algoritmo greedy. Nel caso in cui il problema possieda anche si può usare un algoritmo dinamico. (it)
|
