Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof: All Blind-Memoryless search strategies are equivalent

  1. Oct 11, 2009 #1
    Hi All

    Is there a proof that all blind-memoryless search strategies are equivalent?

    By equivalent I mean that no blind-memoryless search strategy can outperform any other in terms of time to goal and domain coverage.

    It seems to me that this is intuitively true.

    How would I go about proving it?

    Thanks :-)
  2. jcsd
  3. Oct 11, 2009 #2
    You might want to look at the No Free Lunch theorems, which prove something stronger:

    The way the proof is done is something along the lines of showing that for any given algorithm you may choose, each search landscape that the algorithm turns out to do well on is balanced by a perverse search landscape (somewhere out there in the set of all possible landscapes) that looks like that optimal landscape locally but is actually tricking the algorithm into moving away from the good points.

    I think what you want to prove may actually follow from Wolpert and Macready's existing theorems here?
    Last edited: Oct 12, 2009
  4. Oct 12, 2009 #3
    Thanks very much ^^
    Thats exactly what I was looking for.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook