Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Optimal_substructure> ?p ?o. }
Showing items 1 to 19 of
19
with 100 items per page.
- Optimal_substructure abstract "In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems. This property is used to determine the usefulness of dynamic programming and greedy algorithms for a problem.Typically, a greedy algorithm is used to solve a problem with optimal substructure if it can be proved by induction that this is optimal at each step (Cormen et al. pp. 381–2). Otherwise, providing the problem exhibits overlapping subproblems as well, dynamic programming is 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<s<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.".
- Optimal_substructure thumbnail Shortest_path_optimal_substructure.svg?width=300.
- Optimal_substructure wikiPageID "243102".
- Optimal_substructure wikiPageRevisionID "576549921".
- Optimal_substructure hasPhotoCollection Optimal_substructure.
- Optimal_substructure subject Category:Dynamic_programming.
- Optimal_substructure subject Category:Mathematical_optimization.
- Optimal_substructure comment "In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems. This property is used to determine the usefulness of dynamic programming and greedy algorithms for a problem.Typically, a greedy algorithm is used to solve a problem with optimal substructure if it can be proved by induction that this is optimal at each step (Cormen et al. pp. 381–2).".
- Optimal_substructure label "Optimal substructure".
- Optimal_substructure label "Sottostruttura ottimale".
- Optimal_substructure label "Własność optymalnej podstruktury".
- Optimal_substructure sameAs Sottostruttura_ottimale.
- Optimal_substructure sameAs Własność_optymalnej_podstruktury.
- Optimal_substructure sameAs m.01k89t.
- Optimal_substructure sameAs Q2333568.
- Optimal_substructure sameAs Q2333568.
- Optimal_substructure wasDerivedFrom Optimal_substructure?oldid=576549921.
- Optimal_substructure depiction Shortest_path_optimal_substructure.svg.
- Optimal_substructure isPrimaryTopicOf Optimal_substructure.
