Talk:Optimal substructure

From Wikipedia, the free encyclopedia

[edit] Wavy lines?

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)