Talk:Optimal substructure

This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Computing 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.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing ??? This article has not yet received a rating on the project's importance scale.

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)Reply

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)Reply

"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)Reply

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)Reply

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)Reply

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)Reply

I have tried to hunt the term down, but I couldn't find any reference to the term "optimal substructure" earlier than 1990 - Google Books has a couple hits, but they all seem to be misclassifications (dating papers to 1976 because that's when the first issue of the journal was published). And seeing as the book doesn't cite anyone for coining the term, it is possible that the term itself was coined in the CLR book in its first edition in the 90s. --185.125.224.20 (talk) 15:55, 10 December 2021 (UTC)Reply

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)Reply

Is the graphic even correct here? The optimal decision at the start node would be the middle line with cost 2, yet 5 is chosen. If I understood this correctly this means that this task does not have optimal substructure: selecting the local optimum does not lead to the global optimum (total cost of 27 instead of 25). — Preceding unsigned comment added by 62.80.17.92 (talk) 09:19, 23 July 2019 (UTC)Reply