重叠子问题和最优子结构之间有什么区别? [英] What is the difference between overlapping subproblems and optimal substructure?
问题描述
我了解这两种方法的目标方法，其中最佳子结构根据输入n计算最佳解决方案，而重叠子问题则针对输入范围(从1到n)的所有解决方案.
针对诸如
您会看到子问题fib(1)在多个分支上重叠"，因此fib(5)的子问题重叠(fib(1)，fib(2)等).
另外，这是否与制表(自上而下)和备忘(自下而上)的解决方法有关?
这又是一个措辞不佳的问题.自上而下(递归)和自下而上(迭代)方法是使用备忘录解决DP问题的不同方法.摘自Wikipedia的Memoization文章:
在计算中，记忆或记忆是一种优化技术，主要用于通过存储昂贵的函数调用的结果并在再次出现相同的输入时返回缓存的结果来加快计算机程序的速度.
对于给定的fibonacci示例，如果我们在第一次遇到fib(1)之后将其存储在 表 中，则无需再次重新计算当我们下次看到它时.我们可以重复使用存储的结果，从而节省了很多计算.
当我们实现迭代解决方案时，表"通常是一个数组(或数组的数组)，而当我们实现递归解决方案时，表"通常是动态数据结构的哈希表(字典).
您可以进一步阅读此链接，以更好地理解这两种方法.
I understand the target approach for both the methods where Optimal Substructure calculates the optimal solution based on an input n while Overlapping Subproblems targets all the solutions for the range of input say from 1 to n.
For a problem like the Rod Cutting Problem. In this case while finding the optimal cut, do we consider each cut hence it can be considered as Overlapping Subproblem and work bottom-up. Or do we consider the optimal cut for a given input n and work top-down.
Hence, while they do deal with the optimality in the end, what are the exact differences between the two approaches.
I tried referring to this Overlapping Subproblem, Optimal Substructure and this page as well.
On a side note as well, does this relate to the solving approaches of Tabulation(top-down) and Memoization(bottom-up)?
This thread makes a valid point but I'm hoping if it could be broken down easier.
To answer your main question: overlapping subproblems and optimal substructure are both different concepts/properties, a problem that has both these properties or conditions being met can be solved via Dynamic Programming. To understand the difference between them, you actually need to understand what each of these term means in regards to Dynamic Programming.
I understand the target approach for both the methods where Optimal Substructure calculates the optimal solution based on an input n while Overlapping Subproblems targets all the solutions for the range of input say from 1 to n.
This is a poorly worded statement. You need to familiarize yourself with the basics of Dynamic Programming. Hopefully following explanation will help you get started.
Let's start with defining what each of these terms, Optimal Substructure & Overlapping Subproblems, mean.
Optimal Substructure: If optimal solution to a problem, S, of size n can be calculated by JUST looking at optimal solution of a subproblem, s, with size < n and NOT ALL solutions to subproblem, AND it will also result in an optimal solution for problem S, then this problem S is considered to have optimal substructure.
Example (Shortest Path Problem): consider a undirected graph with vertices a,b,c,d,e and edges (a,b), (a,e), (b,c), (c,d), (d,a) & (e,b) then shortest path between a & c is a -- b -- c and this problem can be broken down into finding shortest path between a & b and then shortest path between b & c and this will give us a valid solution. Note that we have two ways of reaching b from a:
- a -- b (Shortest path)
- a -- e -- b
Longest Path Problem does not have optimal substructure. Longest path between a & d is a -- e -- b -- c -- d, but sum of longest paths between a & c (a -- e -- b -- c) and c & d (c -- b -- e -- a -- d) won't give us a valid (non-repeating vertices) longest path between a & d.
Overlapping Subproblems: If you look at this diagram from the link you shared:
You can see that subproblem fib(1) is 'overlapping' across multiple branches and thus fib(5) has overlapping subproblems (fib(1), fib(2), etc).
On a side note as well, does this relate to the solving approaches of Tabulation(top-down) and Memoization(bottom-up)?
This again is a poorly worded question. Top-down(recursive) and bottom-up(iterative) approaches are different ways of solving a DP problem using memoization. From the Wikipedia article of Memoization:
In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
For the given fibonacci example, if we store fib(1) in a table after it was encountered the first time, we don't need to recompute it again when we see it next time. We can reuse the stored result and hence saving us lot of computations.
When we implement an iterative solution, "table" is usually an array (or array of arrays) and when we implement a recursive solution, "table" is usually a dynamic data structure, a hashmap (dictionary).
You can further read this link for better understanding of these two approaches.
这篇关于重叠子问题和最优子结构之间有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
