An Application of the No Free Lunch Theorem

[LuckOfTheDraw]

Ok, so we have the No Free Lunch Theorem (NFLT). I can sort of understand this intuitively. However, while reading an article the other day in The New Yorker, I saw the following example:

"Consider a search for high ground on some unfamiliar, hilly terrain. You’re on foot and it’s a moonless night; you’ve got two hours to reach the highest place you can. How to proceed? One sensible search algorithm might say, “Walk uphill in the steepest possible direction; if no direction uphill is available, take a couple of steps to the left and try again.” This algorithm insures that you’re generally moving upward. Another search algorithm—a so-called blind search algorithm—might say, “Walk in a random direction.” This would sometimes take you uphill but sometimes down. Roughly, the N.F.L. theorems prove the surprising fact that, averaged over all possible terrains, no search algorithm is better than any other. In some landscapes, moving uphill gets you to higher ground in the allotted time, while in other landscapes moving randomly does, but on average neither outperforms the other."

This does not come across as intuitive for me. To me, it seems that if you choose a step up instead of a step down, on average, you would find higher ground. Though, it seems to be a pretty straightforward application of the NFLT. Any thoughts?

[madnak]

Well, if they tailored the terrain directly to the situation, and if the search algorithm could eventually reach the destination ("never ever go uphill" wouldn't work, obviously), then I guess it could work. For instance, if the algorithm is "go downhill and then continue in a straight line if you reach the bottom point" then that might be the ideal solution if you're on a small hill circled by a ditch circled by a rise that represents the highest point.

[madnak]

But I agree that "averaged over all possible terrains" doesn't really make sense at all. I think there's something fishy going on. How did they come up with their enumeration of terrain types? How did they evaluate each strategy for each terrain type? On what basis did they consider the frequency of the terrain type (or did they at all)? And how did they perform the "averaging?"

[madnak]

Sorry to post again here, but "over all possible problems" is very different from "over all terrain types found on Earth." If they're talking about theoretical "terrains," and the infinite set of them, that's a different story. It's still probably a good idea to head uphill if you're on Earth terrain. At any rate, it'll give you a better vantage point.

[MidGe]

[ QUOTE ]
I think there's something fishy going on.

[/ QUOTE ]

Indeed there is. If you starting point happens to be the highest, you will not know, unless you have covered every other possible point on the terrain, that the best solution was not to move.

Hope this help with the fish! [img]/images/graemlins/smile.gif[/img]

[madnak]

Doesn't that just mean "stay in one place" can be the optimal search algorithm? [img]/images/graemlins/grin.gif[/img]

[madnak]

Do you have a link to the article, btw? I think some information is probably missing.

[LuckOfTheDraw]

[ QUOTE ]
Do you have a link to the article, btw? I think some information is probably missing.

[/ QUOTE ]

I don't think there's much more there.

[MidGe]

[ QUOTE ]
Doesn't that just mean "stay in one place" can be the optimal search algorithm? [img]/images/graemlins/grin.gif[/img]

[/ QUOTE ]

Another way of saying it, is that for every possible search algorithm you can construct a terrain that is -EV. Therefore you can't design an algorithm better than any other.

[LuckOfTheDraw]

What if your algorithm is to take X steps from an initial position in every direction. Set a new initial position to the found high point. If no high point is found, increase X. Rinse and repeat.