I really like this post, it’s very informative about the kind of search algorithms that exist. I had one question though, in my experience as a child solving mazes with a crayon I stumbled upon the tactic of starting at the end and getting to the beginning. This worked really well for me, but it always confused me as to why it was easier. Does anyone have a hypothesis as to why this might be?
The mazes may have been constructed to be hard from the front. (Lesser hypotheses: If you switch to the back when you notice it’s hard from the front, on average it’s going to become easier. If you switch after having explored the maze a little from the front, you already know where to go.)
Also: Searching from the back in addition to searching from the front can be really helpful in reconstructing the overall path!
In computer science, we might call this “breadth-first search from both sides” or “bidirectional search” (image); the insight being that you keep searching until your two search trees have some point in common. This is nice because you explore fewer total paths—in a large maze, the number of paths you explore grows exponentially as you get farther away from the starting location.
The analog in general problem solving might be to look both backwards and forwards. If I want to e.g. be happily married with kids in 5 years, I should not only think about my possible actions today (“go on more dates”, “reconnect with old crushes”), but also backwards from my destination (“which marriages are happy”, “how to raise children”), and look for how the two can connect (“ah, Eve is an old friend from high school who shares this interest in child rearing”).
This is also a technique in math proofs. From XKCD:
“Handy exam trick: when you know the answer but not the correct derivation, derive blindly forward from the givens and backward from the answer, and join the chains once the equations start looking similar. Sometimes the graders don’t notice the seam.”
Except: sometimes, instead of tricking the grader, you actually just find the correct derivation!
I know someone who successfully used that “handy exam trick” in the International Mathematical Olympiad.
(Of course this isn’t relevant to the actual discussion, but it might amuse you as it amuses me. Further details that I find pleasing: 1. He took care to make sure that the “seam” lay between the end of one page of working and the start of the next. 2. The people marking the script claimed to have found an entirely different error which was not in fact an error, but of course the country’s team leaders didn’t send it back and complain because they knew that if they did the much more serious error in logic was likely to be noticed. For the avoidance of doubt, the person in question was not me.)
I really like this post, it’s very informative about the kind of search algorithms that exist. I had one question though, in my experience as a child solving mazes with a crayon I stumbled upon the tactic of starting at the end and getting to the beginning. This worked really well for me, but it always confused me as to why it was easier. Does anyone have a hypothesis as to why this might be?
The mazes may have been constructed to be hard from the front. (Lesser hypotheses: If you switch to the back when you notice it’s hard from the front, on average it’s going to become easier. If you switch after having explored the maze a little from the front, you already know where to go.)
Also: Searching from the back in addition to searching from the front can be really helpful in reconstructing the overall path!
In computer science, we might call this “breadth-first search from both sides” or “bidirectional search” (image); the insight being that you keep searching until your two search trees have some point in common. This is nice because you explore fewer total paths—in a large maze, the number of paths you explore grows exponentially as you get farther away from the starting location.
The analog in general problem solving might be to look both backwards and forwards. If I want to e.g. be happily married with kids in 5 years, I should not only think about my possible actions today (“go on more dates”, “reconnect with old crushes”), but also backwards from my destination (“which marriages are happy”, “how to raise children”), and look for how the two can connect (“ah, Eve is an old friend from high school who shares this interest in child rearing”).
This is also a technique in math proofs. From XKCD:
Except: sometimes, instead of tricking the grader, you actually just find the correct derivation!
I know someone who successfully used that “handy exam trick” in the International Mathematical Olympiad.
(Of course this isn’t relevant to the actual discussion, but it might amuse you as it amuses me. Further details that I find pleasing: 1. He took care to make sure that the “seam” lay between the end of one page of working and the start of the next. 2. The people marking the script claimed to have found an entirely different error which was not in fact an error, but of course the country’s team leaders didn’t send it back and complain because they knew that if they did the much more serious error in logic was likely to be noticed. For the avoidance of doubt, the person in question was not me.)