China
Africa
Explore chapters and articles related to this topic
Signature Generation Algorithms for Polymorphic Worms
Published in Mohssen Mohammed, Al-Sakib Khan Pathan, Automatic Defense Against Zero-day Polymorphic Worms in Communication Networks, 2016
Mohssen Mohammed, Al-Sakib Khan Pathan
Optimal substructure means that the solution to a given optimization problem can be obtained by the combination of optimal solutions to its subproblems. The preliminary step toward devising a dynamic programming solution is to check whether the problem exhibits such optimal substructure, which is usually described by means of recursion. For example, given a graph G = (V, E), the shortest path p from a vertex u to a vertex v exhibits optimal substructure: Take any intermediate vertex w on this shortest path p. If p is truly the shortest path, then the path p1 from u to w and p2 from w to v are indeed the shortest paths between the corresponding vertices.
Basic Algorithmic Techniques
Published in Charles J. Alpert, Dinesh P. Mehta, Sachin S. Sapatnekar, Handbook of Algorithms for Physical Design Automation, 2008
Vishal Khandelwal, Ankur Srivastava
Now the term optimal substructure means that the optimal solution to the subproblems can be used to generate the optimal solution to the overall problem. If indeed this is true then the above-mentioned sequence of steps for solving a problem must generate the optimal solution to the overall problem. DP also generates the optimal solution using the same principle. Let us illustrate the DP philosophy using an example.
Aggregating disjoint partial sub-orders – an internal logistics application
Published in International Journal of Systems Science: Operations & Logistics, 2023
Blandine Vacher, Antoine Jouglet, Dritan Nace, Marwane Bouznif
We have used the dynamic programming paradigm (Cormen et al., 2001) to build the second solution method. This paradigm is based on the Bellman's principle of optimality, and means decomposing the initial problem into sub-problems which are solved recursively until all possibilities have been explored and the optimal solution obtained. Each sub-problem has an optimal substructure in accordance with the Bellman's principle. The Bellman's principle, which is formalised by the dynamic programming Bellman's equation, consists in preserving the optimality through stages that is, each substrategy of an optimum strategy must be itself an optimum strategy with regard to the initial and the terminal states. Remind that our problem is to build an aggregating sequence that minimises the disorder with respect to the preferred order, while respecting the precedence constraints set by the order of loads present in the buffer aisles. A sub-problem can be expressed as follows: given a set of loads composed of the first loads present in buffer aisles , respectively, what would be the best aggregating sequence, with respect to the disorder defined above? Here indicates the number of first loads placed in the head of the buffer aisle .