Talk:Optimal substructure

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computing (Rated Start-class)
WikiProject icon This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 

Wavy lines?[edit]

This article has a similar caption to the one in dynamic programming -- and the same problems. If the wavy lines are the shortest paths between two nodes, why aren't all the nodes wavy, since the graph is only singly connected? -- Mikeblas 09:44, 31 March 2007 (UTC)

Each wavy line indicates that there exists a shortest path, with the indicated weight, from the goal to the node. However this path may be composed of multiple edges and nodes, and the three shortest paths may have many edges and / or nodes in common other than the goal (so it's not necessarily singly connected, even though it kind of looks like it). I think these wavy lines are meant to represent the subproblem solutions. The straight lines, on the other hand, are actual edges.
By the way, is that mikeblas from [H]? --203.206.183.160 13:11, 7 June 2007 (UTC)
"Kind of" looks like it? It's intentionally drawn to be completely singly connected. There's not more than one shortest path; there's a single shortest path. Why would the illustration be working backward, form the goal back to the start, then? How is a reader to know that the wavy lines don't represent edges when the caption nor the article provide no such description?
As it stands, I think the illustrtation does far more harm than good, and should be removed until it can be repaired (or the article brought up to snuff so that it supports the illustration).
BTW, yes. -- Mikeblas 13:24, 7 June 2007 (UTC)
I also find the figure mysterious. It needs more work. (I added to the caption that the numbers represent the path length, though that is just a guess.)--Christopher King (talk) 20:04, 15 January 2009 (UTC)

How get Minima?[edit]

In the middle of the formal definition, it mentions a minima, but it doesn't say what variable is being changed to form that minimum. I couldn't figure out what that variable is, so I couldn't follow the formal definition.--Christopher King (talk) 20:04, 15 January 2009 (UTC)

Origin of term?[edit]

It would be helpful if someone could include information about the origin of the term "optimal substructure". As far as I can tell it is a more general version of the "principle of optimality", which is Richard Bellman's term for the fact that finding the optimal choice in a multi-step decision problem ordinarily requires finding optimal choices inside shorter subproblems too. Did Bellman also coin the term "optimal substructure", when he started to do work on computer algorithms? Or was the term originally coined by the Cormen, Leiserson, Rivest, and Stein textbook, or by some other computer scientists? --Rinconsoleao (talk) 15:11, 25 May 2009 (UTC)

"Definition" section[edit]

I tried a careful read of the "Definition" section, and still found it completely impenetrable. I suggest that we either remove it or rewrite it.--Clevera (talk) 23:49, 24 February 2013 (UTC)