This work is licensed under a
Creative Commons License.
|
Thursday, October 07, 2004
NP-Completeness for a 9-Year Old
Posted by Lance
My nine-year old daughter had a homework problem with the following diagram.
She had no problem solving questions like: Beginning and ending at the entrance, describe the shortest route you can take that will allow you to see 4 different kinds of animals.
"You're doing computer science," I said.
"I don't see any computers," she responded.
"Computer science is problem solving like finding the shortest path."
"Then computer science is pretty easy."
"OK, is there a way to visit every animal exactly once?"
She found this question much more challenging.
7:18 PM
# 5 comments
-
Do you mean "shortest path that visits each animal exactly
once"? Otherwise it really isn't very hard...
-
You didn't specify if you could traverse the same path more than once.
-
Traversing this Zoo is very complex!
-
is the problem of shortest path using eucliadian distance is not polynomial? roads on the map you poiuned are almost straight so the problem must be close to euclidian
-
I'm not sure if Euclidean hamiltonian path is NP-hard, but Euclidean TSP remains NP-hard and has a polynomial time approximation scheme. See http://citeseer.ist.psu.edu/arora96polynomial.html
Links to this post:
Weblog Home
Archives
