Talk:Greedy algorithm

The page says that Kruskal's Algorithm is also a Greedy Algorithm. Tho actually this does not work locally, instead Kruskal always takes the smallest weight of all to add an edge to the set. It knows the whole set of edges and in opposite to Prim it takes the smallest weight - shouldnt we remove Kruskal from this page?

--- User:WhiteCrow 7/24/2005

I would find Kruskal's algorithm a more natural example of what I understand to be a greedy algorithm than Prim's. In fact, the phrasing seems somewhat unlucky: I'd describe a greedy algorithm as "an algorithm that repeatedly extends a partial solution in the way that increases the objective function most" (in the case of a maximization problem). In Prim's algorithm we maintain the invariant that the partial solution is a tree; in Kruskal's algorithm we're already happy with a forest. — Preceding unsigned comment added by 131.155.68.93 (talk) 4 October 2005

My PhD computer scientist wife read this over and says the article is basically OK. We looked at the algorithms book that I reference (a standard book on the subject) and it agrees with the article's content. About Kruskal's: the book also specifically ch{| class="wikitable"

|- ! header 1 ! header 2 ! header 3 |- | row 1, cell 1 | row 1, cell 2 | row 1, cell 3 |- | row 2, cell 1 | row 2, cell 2 | row 2, cell 3 |}.e. 22:35, 10 November 2007 (UTC)

It looks like an anatomy list. --Thinboy00 ^talk/_contribs @985, i.e. 22:38, 10 November 2007 (UTC)[reply]

Actually, an anonymous user messed it up here and no one spotted it... I've fixed it now. —ZeroOne (talk / @) 12:25, 11 November 2007 (UTC)[reply]

Opposite

Can someone mention what the name is for the "opposite" or "antonym" of the greedy algorithm, if there is one?

Well the most obvious "opposite" if there could be said to be such a thing would be an algorithm that selects a globally optimal solution, rather than a locally optimal one. In practice, though, non-greedy algorithms include a lot more than just globally optimal algorithms. Dcoetzee 18:02, 30 May 2008 (UTC)[reply]

"ungreedy" is sometimes used for algorigtms that take the most conservative choice at each step rather than the one that increases the solution value the most, such as in Regular expressions BCoates (talk) 05:13, 7 September 2008 (UTC)[reply]

regex

Does greedy regex follow these rules, matter for this sort of topic? If it matters, I'm thinking about pcre regex. —Preceding unsigned comment added by 81.155.84.169 (talk) 21:06, 18 July 2008 (UTC)[reply]

Greedy regexps are only sort of related to greedy algorithms - the match is always expanded as much as possible before applying the next term of the regexp, but greedy and nongreedy regexps describe different languages and solve different problems; it's not a local heuristic for estimating a solution to a problem. Dcoetzee 03:57, 9 November 2008 (UTC)[reply]

Greedy vs. Hill Climbing

There is also an article on Hill climbing algorithms. I can't tell the difference - is one more general than the other? If so, it seems like the relevant page should explain that. This comment is also posted on the discussion page there. Thanks. --Jdvelasc (talk) 19:06, 10 September 2009 (UTC)[reply]

If there is a distinction, I've mostly heard "hill climbing" in the context of traversing the solution space of a function (typically with gradient descent, but not always), while the "greedy approach" usually relates to problems that boil down to graph traversal. The latter can be formulated as a function, but it's hard to describe continuous functions in terms of a graph, so hill climbing is probably the more general term. If there is more to it, I am also curious. Maghnus (talk) 17:44, 26 September 2009 (UTC)[reply]