5 ms·

What he calls "Iterate and Repair" is basically a greedy algorithm. Greedy algorithms are great where they work, but there are also situations where they break

• richcollins 15y ago
  How is it a greedy algorithm? He didn't say anything about the "intuitive" decisions maximizing immediate gain at every decision point.
  • zeteo 15y ago
    I'm sure the users he describes can be trusted to make locally optimal choices.
    • purewater 15y ago
      Greedy algorithms run the same way every time given the same choices. Why? Because, if options are received in a deterministic order, it'll make the locally optimal choice. With iterate and repair, people are using an internal heuristic to make a choice and refining that over time. These are not necessarily the locally optimal choice.
      • zeteo 15y ago
        They won't run the same way if you start from a different node in the search graph, which is probably what the players are doing.
        • purewater 15y ago
          I was being nice before, but it's obvious that you don't know what a greedy algorithm is. Please don't make offensive comments like, "I guess the algorithms course is no longer required at MIT?!"
          • zeteo 15y ago
            A greedy algorithm is an algorithm that makes locally optimal choices. The classic example, if you've taken an algorithms course, is the travelling salesman problem with the nearest neighbor heuristic. This starts at an arbitrary node, and will usually generate different solutions based on the node that is chosen to start at. The very presence of the "internal heuristic" that you mention is usually enough to make the algorithm greedy. Otherwise, thanks for being nice, and try to take less offense at what people say on the Internet.
            • nocipher 15y ago
              It is not the presence of an internal heuristic that makes an algorithm greedy, it is the choosing of locally optimal solutions. For your claim to hold, you would need to demonstrate that people make locally optimal solutions, at least in the context of this problem. That is most likely a wrong assumption. Greedy algorithms usually do not find globally optimal solutions, yet the people solving these problems are finding -the- solution. That is enough to suggest that the heuristic people are using is much more complex than merely choosing local optimums.
            • juliennakache 15y ago
              It was interesting to read both of you guys. I can see a lot of ego on both sides... But that's a good thing :) No one is wrong or right. It just depends on what you believe users are doing. One thing is certain: users use "local search" techniques as opposed to "systematic" search. The salesman problem describes this: the algorithm operates using a single current node and moves only to neighbors of that node. However, depending on the "local search" algorithm used, those may be greedy or not: - "Hill Climbing" is greedy. The algorithm is affected by local maxima, ridges and plateaux. - "Simulated annealing" is not greedy. It uses "gradient descent" and does not always pick the "best" neighbors. I believe the heuristics used by the users: - are not very precise ("Well, it is better, right?") - may change over time ("Oh, look at this!") That's why, I think it is not a "greedy" algorithm with deterministic results, but it is NOT complete anyway (hence, the clear process). I can't wait for you guys to kick my butt :) ps: I'm a business major...
• aaroniba 15y ago
  Most greedy algorithms I've seen do not have a repair step.  But whether I call it "iterate-and-repair" or "greedy" doesn't change the message, does it?  Or are you saying that I shouldn't be surprised that iterate-and-repair works so well on this puzzle?
  • zeteo 15y ago
    What I'm saying is that you shouldn't draw such general conclusions from seeing a simple algorithm work in a particular case. Your problem-game turned out to be algorithmically simple. This probably makes it more appealing as a game. But most things in life will not be as simple, and this includes large coding projects. What you call the repair step I see as running the greedy algorithm again, from a different node in the search graph.
    • aaroniba 15y ago
      The conclusion I drew from this experience was that I should get over my fear of making mistakes. I could have been more clear on that in the post. There's probably some optimal level of fear-of-mistakes for any given project. Monorail made me realize my brain was tuned too far in the fear direction. I stand by that generalization.
      • zeteo 15y ago
        "It turns out to be easier and faster to iterate from an existing but wrong solution, than to deduce a correct solution from scratch. Even if you have to occassionally press the “clear” button to start over." This is what I was referring to. Yes, if you tackle coding projects that are challenging mostly by size and not by algorithmic difficulty, simply plowing ahead is the right attitude. But sometimes you will encounter real challenges, and for those you will need all the top-down design and logical tricks that you can muster. To the extent that my personal experience is relevant, for my PhD thesis I've designed and implemented a novel algorithm. I went through three non-functional versions before I realized that I actually needed to spell everything out on paper first, before writing a single line of code. After that, I was done in two weeks.
• sitkack 15y ago
  "Quid in nomine? Quod dicitur rosa Odorem suavitatis, ut non alio nomine. All you guys are trying to label, taxonimicate the "lay person's" strategy into your hierarchy. Humans are damn smart, and the cocksure MIT nerd got his ass handed to him.
  • dev1n 15y ago
    this is true for the most part. Humans have always been the "try it and if it kills somebody try it another way." i.e. we used to eat tobacco leaves. Now we smoke them. riddle me that.